AGC 029 D - Grid game

問題

beta.atcoder.jp

解法

まず先手が能動的にパスを選択することはありえない。なので、後手は先手の進行方向に障害物を置きさえすれば良い。

両プレーヤーが能動的にパスを選択せずにxターンが終了した時の位置を (x, y) とする。このとき、後手は適当にパスを挟むことでxターンが終了したときの位置を (x,1)〜(x,y) から選ぶことが出来る。つまり、xターン終了時に (x+1, 1) 〜 (x+1, y) のどこかに障害物があるならば x+1 ターン目で先手はパスせざるを得なくなる。

コード

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { reader: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();
    let n: usize = sc.read();

    let mut map = BTreeMap::new();
    for _ in 0..n {
        let x: usize = sc.read();
        let y: usize = sc.read();
        map.entry(x).or_insert(BTreeSet::new()).insert(y);
    }

    let mut y = 1;
    for x in 1..(h + 1) {
        if let Some(set) = map.get(&(x + 1)) {
            if set.range(..(y + 1)).next().is_some() {
                println!("{}", x);
                return;
            }
            if !set.contains(&(y + 1)) {
                y += 1;
            }
        } else {
            y += 1;
        }
    }
    println!("{}", h);
}

pub struct Scanner<R> {
    reader: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}