読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

CODE FESTIVAL 2015 予選A D - 壊れた電車

kenkooooさんのブログにSRM681 Div.1 Easy FleetFunding - ゆらのふなびとの類題として載っていたので。

問題

N両編成の電車をM人の整備士で点検する。i人の整備士は最初X_i両目の車両にいる。車両の点検には時間はかからないが、隣の車両に移動するには1分かかる。全ての車両を少なくとも1人の整備士が点検すれば点検は終了である。さて、点検を終了させるのにかかる最短の時間は何分か。

制約

 1 \leq N \leq 10^9

 1 \leq M \leq 10^5

(※X_iは既に昇順にソートされている)

解法

にぶたん×貪欲。 制約が大きいので、計算量に注意する。

まずにぶたんについて。この問題は単調性を持つ。t分で作業が終了するならt分以上でも終了するし、t分で作業が終了しないならt分以下でも終了しない。よってにぶたんがつかえる。にぶたんの計算量は O(\log N)

次に「t分で作業が終了するか」の判定について。実は時刻tを決めれば、各整備士について移動の仕方を貪欲に決めることができる。各整備士について、まだ掃除されていない最も左側のマス pを通り、かつ、自分が掃除し終わった後の pの値が最大になるようなるようなルートをとればよい。*1 pが自分の右側にあるときはひたすら右側に進めばよい。 pが自分の左側にあるときは、左に行ってから右に戻るルートと、右に行ってから左に戻るルートがあることに注意。(ひっかかりました)

にぶたんは O(\log N)、貪欲は各整備士について定数時間で判定するので O(M)。合わせて O(M \log N)となり間に合う。


  • 解答例: C++

にぶたんの上限はNではなく最悪1.5N(整備士が1人だけ真ん中にいるとき)であることに注意。(これもひっかかりました)

bool ok(ll t, int n, int m, vll x) {
    // まだ掃除されていない一番左側のマス
    ll p = 0;
    // 各整備士に対して、進めるだけ進める
    rep(i, m) {
        if (p < x[i]) {
            if (x[i] - p > t) {
                return false;
            }
            p = max(x[i] + (t - 2 * (x[i] - p)) + 1,
                        x[i] + (t - (x[i] - p)) / 2 + 1);
        } else {
            p = max(p, x[i] + t + 1);
        }
        if (p >= n) {
            return true;
        }
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> x(m);
    rep(i, m) {
        cin >> x[i];
        x[i]--;
    }

    if (n == m) {
        cout << 0 << endl;
        return 0;
    }

    ll l = 0;
    ll r = 3e9;
    while (r - l > 1) {
        ll mid = (r + l) / 2;
        if (ok(mid, n, m, x)) {
            r = mid;
        } else {
            l = mid;
        }
    }

    cout << r << endl;

    return 0;
}

所要時間: 118分(º﹃º)

にぶたん×貪欲、典型っぽいのでもっと速くとけるようになりたい。

*1:「かつ」の前半は後半に内包されるんですけど便宜上許してください