【Rust】ABC427感想（A~D）

AtCoder Beginner Contest 427

新調したMacBook Proの開発環境構築をしながらだったので、
正確に時間は測れませんでしたが、ABDの3完でした。
今回はA~Dの感想を記載します。
※D問題だけささやかですが解説を載せておきます。

A - ABC -> AC

部分文字列結合の問題ですが、Pythonであればprint(s[:n//2] + s[n//2+1:])と書けば済むところを、Rustでは所有権システムやStringをインデックスアクセスできない関係で長くなります。
参考までに、他の方の解答を見るとprintln!("{}{}")のように書くことで所有権の問題を回避している例もありました。

use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        s: Chars,
    }
    let n = s.len();
    println!("{}", s[..n/2].iter().collect::<String>() + &s[n/2+1..].iter().collect::<String>());
}

B - Sum of Digits Sequence

定義通りにコードを書けば通ります。
変数$\text{sum}$を用意して、$\sum_{j=0}^{i-1}{f(A_j)}$をメモしておくと少しだけ効率的になります。
B問題にしては難しく、少し頭を混乱させながら解きました。

use proconio::input;

fn main() {
    input! {
        n: usize,
    }

    fn f(v: usize) -> usize {
        let mut res = 0;
        let mut v = v;
        while v > 0 {
            res += v % 10;
            v /= 10;
        }
        res
    }

    let mut a = vec![0; n + 1];
    let mut sum = 0;
    a[0] = 1;
    for i in 1..=n {
        sum += f(a[i - 1]);
        a[i] = sum;
    }

    println!("{}", a[n]);
}

C - Bipartize

各頂点の塗り分けは$2^N$通りしかないため、塗り分けを全探索して、二部グラフの規則に矛盾するような辺を削除するという考え方で解くことができます。

私は辺の数$M$が$N(N-1)/2$以下ということを完全に見過ごしており、残して良い辺の組み合わせをbit全探索してdfs（深さ優先探索）による二部グラフ判定を行ってしまいました。
Rustが高速すぎて$O(2^M(N+M))$のこの解法でも実行時間制限に間に合いましたが、根本的にこの解法だと間違っているのか無限にWAを量産してしまいました。

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        e: [(usize, usize); m],
    }

    let mut ans = usize::MAX;
    for i in 0..=1 << n {
        let mut val = vec![0; n];
        for j in 0..n {
            val[j] = (i >> j) & 1;
        }

        let mut cnt = 0;
        for j in 0..m {
            let (u, v) = (e[j].0 - 1, e[j].1 - 1);
            if val[u] == val[v] {
                cnt += 1;
            }
        }
        ans = ans.min(cnt);
    }

    println!("{}", ans);
}

D - The Simple Game

こちらは典型的な二人零和有限確定完全情報ゲームの問題で、ある程度慣れた人ならDP（動的計画法）で簡単に解くことができます。

二人零和有限確定完全情報ゲームの基本的な考え方ですが、ある局面（状態）での勝ち負けを知るためには、その次の局面での勝ち負けを全て知る必要があります。
そして、「私」がなんらかの行動をして相手に手番を渡した時、相手がどのような手を選んでも「私」が勝つことのできるような局面が一つでもあれば、その局面に誘導することで「私」は勝つことができるということがわかります。

言葉で説明するとどうしてもわかりづらいですが、図を見ると一目瞭然だと思います。

▼二人零和有限確定完全情報ゲームの基本的な考え方ーその１

上の図では、$n$手目のAさんの手番からは$5$種類の局面に遷移することができますが、$n+1$手目のBさんの手番で一つだけAさんが勝てる局面が存在します。
よって、Aさんがn手目の手番でその局面に誘導することで勝利することができます。

一方で、以下の図では$n+1$手目のBさんの手番ではどの手を選んでもBさんに勝ち筋がある状況です。
このとき、Aさんが$n$手目の手番でどのような手を選んでも勝利することができません。

▼二人零和有限確定完全情報ゲームの基本的な考え方ーその２

少し乱暴な言い方ですが、Aさんの勝ち負けをtrue/falseに置き換えると、ある局面の勝敗は、次に遷移可能な全局面での勝ち負け(true/false)の論理和と等しいと捉えても良いと思います。

以上が二人零和有限確定完全情報ゲームの基本的な性質です。
この性質に基づいて後退解析を行い、「手番がAliceであり、駒が頂点$1$に存在し、残り$2K$回動く必要がある」局面での勝者を求めましょう。

局面の全体集合は「手番 $\lbrace \text{Alice},\text{Bob} \rbrace \times$ 駒の位置 $\lbrace 1, \cdots, N \rbrace \times$ 残り手番数 $\lbrace 0, \cdots, 2K \rbrace$」の直積で表されます（AliceとBobが交互に$K$回駒を動かす必要があるので$2K$です）。

したがって、$\text{dp}$配列を以下のように定義します。
$$\text{dp}_{i,j,k}:=手番iで、駒が頂点jに存在し、残り手番数がk回の状態での勝者$$

先ほどの二人零和有限確定完全情報ゲームの説明で述べたように、ある局面の勝敗を求めるためにはその次に遷移可能な全局面での勝ち負けを求める必要があります。
言い換えれば、残り手番数$k$の局面での勝敗を求めるためには残り手番数$k-1$の全局面での勝敗が必要です。
よって、残り手番数$0 \cdots 2K$での$\text{dp}$の値をこの順に求めていくという発想が必要で、これが後退解析と呼ばれるものになります。

残り手番数が$0$のときは移動しない（できない）ので、駒の位置と与えられた文字列$S$を見て、AならばAliceの勝ち、BならばBobの勝ち、のように一つずつ判定します。これで$\text{dp}_{*,*,0}$が求められました。以降は残り手番数を一つずつ増やしていって、$\text{dp}$配列を順に埋めていきます。

最終的に欲しいのは$\text{dp}_{\text{Alice}, 1, 2K}$なので、これを出力して終了です。
全体計算量は$O((N+M)K)$となり、十分高速にこの問題を解くことができました。

use itertools::Itertools;
use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        t: usize,
    }

    let mut ans = vec![];
    for _ in 0..t {
        input! {
            n: usize,
            m: usize,
            k: usize,
            s: Chars,
            e: [(usize, usize); m],
        }

        let mut g = vec![vec![]; n];
        for i in 0..m {
            g[e[i].0 - 1].push(e[i].1 - 1);
        }

        let mut dp = vec![vec![vec![0; 2 * k + 1]; n]; 2];
        for u in 0..n {
            dp[0][u][0] = if s[u] == 'A' { 0 } else { 1 };
            dp[1][u][0] = if s[u] == 'B' { 1 } else { 0 };
        }

        for cnt in 0..2 * k {
            for player in 0..2 {
                for u in 0..n {
                    dp[player][u][cnt + 1] = player ^ 1;
                    for v in &g[u] {
                        if dp[player ^ 1][*v][cnt] == player {
                            dp[player][u][cnt + 1] = player;
                        }
                    }
                }
            }
        }
        
        if dp[0][0][2 * k] == 0 {
            ans.push("Alice");
        } else {
            ans.push("Bob");
        }
    }
    println!("{}", ans.iter().join("\n"));
}

補足として、上記コードでは手番$(\text{Alice},\text{Bob})=(0,1)$、勝敗$(\text{Alice}勝利,\text{Bob勝利})=(0,1)$のようにビットフラグで対応づけし、ビット論理和の要領で解きました。

まとめ

C問題が解けずに自信をなくしかけましたが、D問題はサクッと解けてなんとか自信を保ちました。
新調したMacBook Proですが、爆速すぎてとっても快適に競プロができています。
時間も確保できつつあるので、少しずつ競プロのリハビリを頑張りたいです。