AOJ 2250 - Operator

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2250

解法

二分探索やるだけじゃーんとなってサンプルチェックして違うことが判明するやつ。見事に引っかかってしまった。

良い性質がないか観察してみると、少なくとも可能かどうかの人数を効率よく見つけることはかなり難しい気がする。
ということは、人数を決め打ちしてシュミレートするしかないから、シュミレート部分を高速化するしかない。

というわけで考えたところ、O(N^2T) から落ちない。なんだこれ。
フラグが立っている先頭位置を高速に求められる bitset を持っていれば、定数倍で通せるなーとは思った。そういう問題なのかなーという気もしたけど、割と愚直にシミュレートしてもまあまあ早い気がした（？）のでそれで書く。

まず1秒毎すすめていく単純なシミュレートを考える。
時刻 t で電話に出られる人間の判定は t mod (l[i] + k[i]) <= l[i] となる i が分かれば良い。
オペレーターはいま出られる人数を普通に持っておいて、電話に出たら復活する位置にその数をインクリメントする。毎秒その時刻でよみがえる人を足し戻す。

電話に出る客が見つかったら、そいつを取り除いてやる。
まだ対応してない客の管理は list を使うと log がつかなくていい気がした。
削除が O(1) でできるから。set でもできるけど遅いし。bool の vector で毎回 O(n) チェックしても実は早いのかもしれない。
list を使うと客が減っていくに連れて探索が減るから若干早いことが期待できそうだなと思ってそうした。

これで O(N^2T) に多少の定数倍改善が入って何故か通った。なんもわからん。
実行時間は 0.3sec 程度。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, t;
    while(cin >> n >> t, n) {
        vector<int> m(n), l(n), k(n);
        for(int i = 0; i < n; ++i) {
            cin >> m[i] >> l[i] >> k[i];
        }

        auto check = [&] (int num) {
            vector<int> restore(t + 1);
            list<int> ls;
            for(int i = 0; i < n; ++i) ls.push_back(i);
            int remain = num;
            for(int i = 0; i <= t; ++i) {
                remain += restore[i];
                auto it = ls.begin();
                while(remain > 0 && it != ls.end()) {
                    const int idx = *it;
                    if(i % (l[idx] + k[idx]) <= l[idx]) {
                        --remain;
                        if(i + m[idx] > t) return false;
                        restore[i + m[idx]] += 1;
                        it = ls.erase(it);
                    } else {
                        ++it;
                    }
                }
            }
            return ls.empty();
        };
        for(int i = 1; i <= n; ++i) {
            if(check(i)) {
                cout << i << endl;
                break;
            }
        }
    }
}

感想

公式解答見たら O(N^3 log) で定数倍早いから通るとかいってて笑った。
ICPC とはいっても、今でもこんな問題出せるのかは怪しい気がする。
list を使ったのは久々だなあ。