2023-03-29 ABC278 の E, F を解いた

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" });
}

今日のコミット。