このコンテストの作問チームにいたが、この問題は実装しなかったので今更実装した。(は?)
A - Taro vs. Jiro
問題
2人が、頂点に赤青の色が塗られた有向グラフの上にコマを置いてゲームをする。各プレイヤーは1ターンに1度、コマを置かれた頂点に隣接する頂点のどれかに動かす。Kターン後にコマが置かれた頂点の色が青なら先手の勝ち、赤なら後手の勝ち。各頂点について、そこからゲームを開始した時、どちらが勝つか判定せよ。
- 2 <= (頂点数) <= 10^5
- 1 <= (辺数) <= 10^5
- 1 <= K <= 10^18
- 与えられるグラフは単純で連結
解法
K>=3の場合、いずれのプレイヤーも、直前の相手の動きを打ち消すことができる。よって、K手での勝敗は(K-2)手での勝敗に一致する。
K=1のときとK=2のときに判定できればよい。
K=1のとき、初期地点をvとしたとき、vに隣接する頂点に青が一つでも存在する時、およびときに限り先手は勝てる。K=2のとき、初期地点をvとしたとき、vに隣接する頂点に(1手で赤に行ける頂点)が一つも存在しないとき、およびそのときに先手は勝てる。
実装上の注意点
- K=2のとき、単に2手で行ける場所を全列挙してしまうとO(N^2)時間かかるので、DPなどをする必要がある。
- 今回は意図的に除外されているが、K=0のケースがコーナーケースなので、入力としてあり得るかどうかは絶対確認する!
提出: Submission #3867920 - 第5回 ドワンゴからの挑戦状 本選 (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! { n: usize, m: usize, k: i64, s: chars, ab: [(usize1, usize1); m], } let mut g = vec![Vec::new(); n]; for (a, b) in ab { g[a].push(b); g[b].push(a); } let mut taro = vec![false; n]; if k % 2 == 1 { for v in 0 .. n { for &w in g[v].iter() { if s[w] == 'B' { taro[v] = true; } } } } else { let mut dp = vec![[false; 2]; n]; for v in 0 .. n { for &w in g[v].iter() { if s[w] == 'R' { dp[v][0] = true; } } } for v in 0 .. n { for &w in g[v].iter() { if !dp[w][0] { dp[v][1] = true; } } } for i in 0 .. n { taro[i] = dp[i][1]; } } for ans in taro { puts!("{}\n", if ans { "First" } else { "Second" }); } }
まとめ
この問題は本戦参加者全員が解けるくらいの難易度を目指して作られた。ほとんどの人に解かれたようでよかった。(解いていない赤コーダーは初手CかDに突っ込んだはずなのでカウントしない。)
