AtCoder AGC 029 D - Grid game (黄色, 800 点)

これは。。。C より先に確実にこれをとったのはよかった

• 問題へのリンク

問題概要 (意訳)

H × W の二次元グリッドがあって、各マスは通路か壁である。壁は N 個ある。最初は (1, 1) に駒がある。

毎ターン (x, y) にある駒は

• (x + 1, y) に進める、ここで (x + 1, y) が壁または場外であっても進める
• (x + 1, y + 1) に進める、ただし (x + 1, y + 1) が壁または場外の場合は進めない

のどちらかを行うことができる。駒を壁マスに進めるか、場外アウトさせるのに必要な最小ターン数を求めよ。

制約

• 1 <= H, W <= 2 × 10⁵
• 0 <= N <= 2 × 10⁵

考えたこと

求める最小ターン数に達しない場合は、x 座標を固定したときの駒の y 座標のとりうる値は、[1, t] みたいに連続した 1 つの区間で表せることが示せる。

なぜなら、もし駒の y 座標としてありうる値のなす区間が 2 つ以上に分断されてしまったとしたら、その最初に分断された時点でゲームを終了することができたはずだからである。

よって、x 座標をインクリメントするとともに、y 座標の区間の右端を常に更新していけばいい。

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

using pint = pair<int,int>;

int main() {
    int H, W, N;
    map<int, set<int> > ma;
    cin >> H >> W >> N;
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        ma[x].insert(y);
    }
    int res = H;
    int left = 1, right = 1;
    for (int x = 2; x <= H; ++x) {
        if (!ma.count(x))  right = min(right + 1, W);
        else {
            int first = *ma[x].begin();
            if (left <= first && first <= right) {
                res = min(res, x - 1);
                break;
            }
            if (first != right + 1) right = min(right + 1, W);
        }
    }
    cout << res << endl;
}