競プロ典型90問 [1問目] - らんこむの数学部屋

こんばんは。数学部屋と言っておいて、競プロばかりやっている気もしますが、広義の数学ということでお許しください。

毎週末にAtCorderのコンテストに参加してはいるのですが、新参者の私は知識がなく、毎回一から考えている状態です。これはこれで面白いのですが、「競技」とついているのですからやはり高順位を目指していきたいものです。

ということで競プロ典型90問を解いていきたいと思います。

atcoder.jp

できれば1日1個のペースで進めていけるといいですね。あくまで自分の解法を書いていくので、本当に解説を求めている方は公式の解説を参照してくださいね。

さて、前置きはこのぐらいにして1問目です。

001 - Yokan Party（★4）

考えられる解法としては

切れ目を決めて、何cmのピースが存在するか確認する。
目標のスコアを決めて、その長さを満たしつつ $K$ 個の切れ目が入れられるか確認する。

ですかね。

のパターンで行くと、切れ目を決め方が $_n C_k$ 個、その切り方から最小ピースを探すのには $O(K)$ となります。切れ目の決め方だけでも最大で $_{100000} C_{50000} \risingdotseq 10^{30000}$ ほどになってしまいます。
のパターンでは、目標のスコアを決めるのに10⁹通り、その長さを満たしつつ $K$ 個の切れ目が入れられるかは $O(K)$ となります。まだこのままではTLEしてしまう計算量です。

目標のスコアを決めるのに10⁹通りではありますが、最大を求めればよいので上手く最大値を求めていけばよいです。この上手く見つけるための手法が二分法と呼ばれるものです。

自分は以下のソースコードで通しました。

#include <iostream>
#include <vector>

using namespace std;

bool can_split(int length, int num, vector<int>& piece) {

    int n = 0;
    int len = 0;
    for (int i = 0; i < piece.size(); ++i) {
        len += piece[i];
        if (len >= length) {
            ++n;
            len = 0;
            if (n == num) {
                for (int j = i + 1; j < piece.size(); ++j) {
                    len += piece[j];
                }
                if (len >= length) {
                    return true;
                }
                else {
                    return false;
                }
            }
        }
    }

    return false;

}

int main() {

    int K, N, L;
    cin >> N >> L;
    cin >> K;

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // 各ピースの長さ
    vector<int> piece(N + 1);
    piece[0] = A[0];
    for (int i = 1; i < N; ++i) {
        piece[i] = A[i] - A[i - 1];
    }
    piece[N] = L - A[N - 1];

    int length = L / (2 * K);
    int max = L / K + 1;
    int min = 1;
    while (true) {
        if (can_split(length, K, piece)) {
            min = length;
            length = (max + min + 1) / 2;
        }
        else {
            max = length - 1;
            length = (max + min) / 2;
        }
        if (max == min) {
            cout << min;
            return 0;
        }
    }

    return 0;

}

今見ると、変数名に min, max とかの予約語が使われていて悪いコードですね。あと、今回は L < 10⁹ なので問題になりませんが max + min がオーバーフローする可能性のある時は、 length = min + (max - min)/2 とするのが正しいですね。

二分法自体の原理自体は難しくないのですが、整数での二分法はオーバーフローや、最小、最大の決め方を気を付けないと無限ループに陥ることもあるので注意したいところです。

今日はここまで。2問目も既に解いてしまったのですが、また後日書こうと思います。