ABC278 : AtCoder Beginner Contest 278 の E, F を解いた。
- E - Grid Filling
https://atcoder.jp/contests/abc278/tasks/abc278_e
- 提出: https://atcoder.jp/contests/abc278/submissions/40149789
- 塗りつぶす範囲を動かしていき、その差分だけを更新すれば間に合う
- 考察は簡単なものの実装はハマりやすい
- F - Shiritori
https://atcoder.jp/contests/abc278/tasks/abc278_f
- 提出: https://atcoder.jp/contests/abc278/submissions/40150907
- 解説 AC
- S は最初の文字と最後の文字以外は不要なので捨てる
N <= 16
なので使用済みの添字を bit として持つ bitDP や bit 全探索ができる- すべて使用済みの状態から逆順に勝てるものを取っていき、初期状態で勝てる手があれば先手の勝ち
use proconio::{input, marker::Chars}; fn main() { input! { n: usize, s: [Chars; n], }; let fl = s .iter() .map(|s_i| { ( ((*s_i.first().unwrap()) as u8 - b'a') as usize, ((*s_i.last().unwrap()) as u8 - b'a') as usize, ) }) .collect::<Vec<(usize, usize)>>(); let mut dp = vec![vec![false; 26]; 1 << n]; for used in (0..(1 << n) - 1).rev() { for c in 0..26 { dp[used][c] = fl .iter() .copied() .enumerate() .filter(|(i, _)| (used & (1_usize << i)) == 0) .any(|(i, (f, l))| c == f && !dp[used ^ (1 << i)][l]); } } let ans = dp[0].iter().copied().any(|b| b); println!("{}", if ans { "First" } else { "Second" }); }
今日のコミット。