Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

Grundy数を計算する問題「茶碗と豆」

www.rustforbeginners.com

では、Grundy数を計算するとなぜNimに帰着出来るのか話したけど、今回は実際の問題に落とす。

あるゲームの勝敗を計算する時、大事なのは、「独立したゲームに分割して各々についてGrundy数を個別に計算する」ということだ。こうすると、Nimの形に帰着出来る。(Nimでは石の山が独立したゲームである)

以下の問題を使って実例を解く。

C - 茶碗と豆

問題

N個の茶碗があり、番号2以降には数字Ciが書いてあり、豆がAi入っている。ゲームは、番号2以降の茶碗を一つ選び、豆を一つ取り出し、Ci左以内の茶碗に移動させる。全豆が茶碗1に集まっていたら負けである。

ここではNは102までの部分点を解くことにする。満点は105。Aは109

考え方

各豆について独立のゲームであると考えることが出来る。各豆は、その時にいる茶碗のCの値によって行き先が制限される。これは、とり方がトリッキーはNimの石山のようなものであると考えることが出来る。

従って、ある豆がある茶碗にある時のGrundy数を計算することにする。これは、茶碗1のGrundy数を0として、1つずつ左から計算していくことが出来る。

最終的に、各茶碗のGrundy数が計算出来たら、各豆をNimの石山と見てxorをとる。しかし豆の総数は部分点でも1011個あるから愚直には無理である。これに対しては、偶奇を計算すればトータルでO(N)となる。

実装

Grundy数の計算は定義どおりやっているが、N=105の満点解法はこれでは間に合わない。(高速化の方法は汎用性がありそうですが、解答を読んでも理解不能でした)

fn solve() {
    input! {
        N: usize,
        CA: [(usize,usize); N-1],
    }
    let mut grundy = vec![0; N];
    for i in 1..N {
        let (c,_) = CA[i-1];
        // grundy[i]を計算する
        // N=100なら間に合う
        let mut h = HashMap::new();
        for j in (i-c)..(i) {
            // dbg!(j);
            let g = grundy[j];
            *h.entry(g).or_insert(0) += 1;
        }
        // dbg!(&h);
        let mut new_g = 0;
        loop {
            if !h.contains_key(&new_g) {
                break;
            }
            new_g += 1;
        }
        grundy[i] = new_g;
    }
    // dbg!(&grundy);

    let mut grundyN = 0;
    for i in 1..N {
        let (_,a) = CA[i-1];
        if a%2 == 1 {
            grundyN ^= grundy[i];
        }
    }

    if grundyN == 0 {
        println!("Second");
    } else {
        println!("First");
    }
}