White Pawn [AtCoder Beginner Contest 203（Sponsored by Panasonic） E]

https://atcoder.jp/contests/abc203/tasks/abc203_e

解説

https://atcoder.jp/contests/abc203/submissions/23075564

計算を差分だけになるように気を付けながらポーンの場所を残しつつ、シミュレーションしていく問題。

ans := とあるx座標において、白のポーンがいる可能性のあるy座標の集合

これを差分計算しながらシミュレーションする。
最初はans = {N}の状態からx=0としてスタートする。
ここからx=1,2,3,...と駒を進めていくイメージでやる。

黒のポーンが次のx座標にない場合

黒のポーンがとあるx座標に全くない場合は、白のポーンが(x,y)にいる場合、(x,y)->(x+1,y)にしかならない。
これをansとして考えてみると全く変わらないことが分かる。
つまり、この場合は何もしないことでシミュレーションを終える。

黒のポーンがある場合

この場合は「全ての黒のポーンに対して操作を検討する」ことでシミュレーション計算を差分だけに抑える。
ここで全てのいる可能性のある白のポーンの全ての場所について操作を検討すると、計算量が爆発してしまうので注意。

とある黒のポーンについて、操作によっては、その場所に白のポーンが移動してくる可能性がある。
これは黒のポーンが(x,y)にあれば、白のポーンが(x-1,y-1)か(x-1,y+1)にある場合である。
ansで考えると、y-1かy+1が含まれる場合である。
C++であればansをsetで持っていればこれはcountメソッドを使って簡単に判定することができる。
条件を満たすなら次の状態で追加できるように別途メモっておこう。
（ここで直接追加してしまうとイテレーションしている関係であとの判定でバグる）

ここで判定に使われなかったansの白のポーンがいる可能性のある場所については、周りに黒のポーンが無いので、単なる(x,y)->(x+1,y)の操作となり、
先ほどと同様にansで何も操作しないことで実現できるので何もしない。

注意点として(x,y)に黒のポーンがある場合は白のポーンが移動できないので、
(x-1,y-1)か(x-1,y+1)に白のポーンがいる可能性がなく、(x,y)に黒のポーンがある場合は答えの候補として削除するようにしておこう。

実装

xを1,2,3とやると10⁹通りで間に合わないので、ポーンがあるx座標のみ扱うようにmapで黒のポーンをまとめている。

int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    map<int, vector<int>> pawns;
    rep(i, 0, M) {
        int X, Y; cin >> X >> Y;
        pawns[X].push_back(Y);
    }

    set<int> ans;
    ans.insert(N);

    fore(p, pawns) {
        set<int> ng;
        set<int> ok;
        fore(y, p.second) {
            if (ans.count(y - 1)) ok.insert(y);
            else if (ans.count(y + 1)) ok.insert(y);
            else ng.insert(y);
        }
        fore(i, ng) ans.erase(i);
        fore(i, ok) if (0 <= i && i <= 2 * N) ans.insert(i);
    }

    cout << ans.size() << endl;
}