Rustコトハジメ

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

Nimを題材にした問題

Nimとは

石の山がN個あり、それぞれAiの石が積んであります。

ここからお互いに石を取り除いていくのですが、

  1. 一回の手番で一つの山からしか取れない
  2. 一つの山からならいくつでも取ることが出来る

がルールです。相手が先に引けなくなったら負けとして、お互い最善を尽くした場合は先手後手のどっちが勝ちますか?

考え方

全部の山の石数のxorをとると、0からは非0にしかならず、非0から0にする手が必ず見つかります。つまり、このゲームの状態数は2つに帰着出来ます。(Grundy数というのが関連してるらしいです)

なぜか?

  • 0から非0にしかならない: 0というのは全ビットの1の数が偶数ということです。ある数を引く場合、それはどのビットもたかだか1つしかないため、結果として奇数のビットが生まれてしまう。
  • 非0から0に出来る: 一番たくさん山が積んであるやつから石を抜くことを考えます。この時、その石数は、xorの最上位ビットを立てています。だから、その最上位ビットを落とす + それ以下のビットも落とすような石のとり方をして相殺すれば、xorを0にすることが出来ます。

だから、相手にxor=0を渡すようにすればいいです。こうするとピンポンのように状態を交互に行き来するのが最善手ということになり、xor=非0なら先手が勝ちます。(初手で0にしてやったら、あとは必ず非0が返ってくるから以下同様)

もし、「最後に引くことになったら負け」という勝敗判定にすると、このロジックは成り立ちません。例えば、山が1つだけしかなくて、そこに2つしか石がない場合、xorは2(非0)ですが、先手が勝ちます。仮に1つしかない場合これもxorは1(非0)ですが今度は先手が負けます。これは、xorの0と非0を行き来することが最善手でなくなってることを意味しています。

例題

どちらも、問題の中から石の山をひねり出します。

Yukicoder No.2 素因数ゲーム

No.2 素因数ゲーム - yukicoder

素因数分解をして、素数の数ごとの石の山を作ってNimをします。

    let pfs = prime_factors(N);
    let mut xor = 0;
    for v in pfs.values() {
        xor ^= v;
    }
    if xor > 0 {
        println!("Alice");
    } else {
        println!("Bob");
    }

ARC013-C 笑いをとれるかな

C - 笑いをとれるかな?

豆腐から石の山をひねり出します。

豆腐の中のハバネロの存在範囲がわかりますから、そこに触れたら負けという石の山を作ります。1つの豆腐から6方向分とれることになります。

    let mut ans = 0;
    for tofu in tofus {
        let mut min_x = 1<<40;
        let mut min_y = 1<<40;
        let mut min_z = 1<<40;
        let mut max_x = 0;
        let mut max_y = 0;
        let mut max_z = 0;
        for haba in tofu.habas {
            min_x = min(min_x, haba.0);
            min_y = min(min_y, haba.1);
            min_z = min(min_z, haba.2);
            max_x = max(max_x, haba.0);
            max_y = max(max_y, haba.1);
            max_z = max(max_z, haba.2);
        }
        ans ^= min_x ^ min_y ^ min_z ^ (tofu.x-1-max_x) ^ (tofu.y-1-max_y) ^ (tofu.z-1-max_z);
    }
    if ans == 0 {
        println!("LOSE");
    } else {
        println!("WIN");
    }

考察

Nim自体がシンプルなので、基本的にはどうやってNimに帰着させるかが問われる問題が多くなるような気がします。

帰着出来てしまえば、実装自体は間違えようがなくおいしいため、Nimなのであれば必ず気づきたいです。ただ、勝敗条件には注意したいです。