CODE FESTIVAL 2015 予選B D - マスと駒と色塗り/Squares, Pieces and Coloring

こどふぇす予選問題全完出来ないのはまずそう。

問題

code-festival-2015-qualb.contest.atcoder.jp

解法

kmjp さんのコードを参考にして書きました。
解説に書いてあった通り, set で黒マスの区間を管理しながら答えを求めていけば良いです。

S からスタートする C 個の点で, 黒マスに重なるところがあったとします。黒マスが区間 [a, b] にまたがっているとすると, とりあえず S 〜 a-1 までは進む点として確定します。その後, 黒マス区間の集合から [a, b] を消して [S, b] を追加します。
こんな感じのことを繰り返していけば良いです。一つの区間は, たかだか 1 回しか調べられないので, 区間を操作する回数は O(N) 回です。よって, このアルゴリズムで満点を取ることが出来ます。

一つ注意なのは, スタート地点として選ばれた地点 S がすでに黒マス区間 [a, b] に入っていた場合です。この場合は, まずスタート地点を a からにすることにします。で, [a, b] という区間を消したいのですが, ただ消すだけだと 区間 [a, b] が黒マスだったという情報がなくなってしまうので進まなければならない白マスの個数を b-a+1 だけ足し算します。

このようにすれば, やはりひとつの区間は 1 回しか調べられないのでハッピーです。

得た知見

• set で区間を管理するのは昔やった気がする

const ll INF = 1ll<<60;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    set<pair<ll, ll> > SS;
    SS.insert(make_pair(-1, -2));
    SS.insert(make_pair(2*INF, INF));
    while (N--) {
        ll S, C;
        cin >> S >> C;
        ll OS = S;
        {
            auto ss = SS.lower_bound(make_pair(S, 0));
            if (S >= ss->second) {
                C += ss->first - ss->second + 1;
                S = OS = ss->second;
                SS.erase(ss);
            }
        }
        while (C) {
            auto ss = SS.lower_bound(make_pair(S, 0));
            if (S+C-1 == ss->second - 1) {
                cout << S+C-1 << endl;
                pair<ll, ll> p(ss->first, OS);
                SS.erase(ss);
                SS.insert(p);
                break;
            } else if (S+C-1 < ss->second - 1) {
                cout << S+C-1 << endl;
                pair<ll, ll> p(S+C-1, OS);
                SS.insert(p);
                break;
            } else {
                C -= ss->second - S;
                S = ss->first+1;
                SS.erase(ss);
            }
        }
    }
    return 0;
}