AGC029 D - Grid game

ゲーム(高橋君に選択権があるとは言ってない)みたいな感じ。
https://atcoder.jp/contests/agc029/tasks/agc029_d

問題

H行W列のマス目の上に障害物がN個とコマが1個(1,1)に置かれている。x行y列の位置を(x,y)と表記する。
高橋君と青木君がマス目の上でゲームをする。
高橋君が先手で、以下の行動を交互にする。

  • コマの位置が(x,y)のとき、高橋君は(x+1,y)に、青木君は(x,y+1)にコマを移動させる。あるいはコマを動かさない。

二人が連続してコマを動かさないことを選択したときにゲームは終わる。高橋君は自分が行う行動の回数を最大化することを、青木君は自分が行う行動の回数を最小化することを目標に動く。二人が最適に行動する時、高橋君の行動回数を求めよ。

  • 1 <= H, W <= 2 * 10^5
  • 0 <= N <= 2 * 10^5
  • 障害物は(1, 1)にはない

解法

高橋君は、自分が止まった瞬間青木君に止まられてゲームが終了してしまう。つまり、高橋君はできるならずっと動き続けないといけない。
青木君は高橋君を障害物に早くぶつけることを考えればいい。最小化すべきなのは高橋君の行動回数(<=> 高橋君がぶつかる障害物のx座標)なのだから、それを求めるためには、貪欲にy軸方向に進んでいって、通った場所からx軸の+側にある直近の障害物のx座標の最小値を求めればいい。
以上を高速にするためには、1からWまでのy座標ごとに、そこにある障害物のx座標を昇順にして配列などに持っておけばいい。

実装上の注意点

  • (x,y)という記号から暗黙に高橋君が右にコマを動かすと思いがちだが、そうではない

- それに付随して、縦横の間違いに気を付ける

  • ループを終了させるタイミングに気をつける(W回ではなくH回)

提出: Submission #3830128 - AtCoder Grand Contest 029 (Rust)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($format:expr) => (write!(out,$format).unwrap());
        ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
    }
    input! {
        h: usize,
        w: usize,
        n: usize,
        xy: [(usize1, usize1); n],
    }
    let mut occur = vec![Vec::new(); w];
    for (x, y) in xy {
        occur[y].push(x);
    }
    for i in 0 .. w { occur[i].sort(); }
    let mut cx = 0;
    let mut cy = 0;
    let mem = |x, y: usize| occur[y].binary_search(&x).is_ok();
    let mut ans = h;
    for _ in 0 .. h {
        let idx = occur[cy].binary_search(&cx).unwrap_err();
        ans = min(ans, if idx >= occur[cy].len() { h } else { occur[cy][idx] });
        if cx >= h - 1 || mem(cx + 1, cy) {
            break;
        }
        cx += 1;
        if cy < w - 1 && !mem(cx, cy + 1) { cy += 1; }
    }
    puts!("{}\n", ans);
}

まとめ

C問題よりも実装が短いんですが…。