ゲーム(高橋君に選択権があるとは言ってない)みたいな感じ。
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問題よりも実装が短いんですが…。