フォルシアゆるふわ競プロオンサイト #3 D - Banana Game locked

すごく面白かった！

問題へのリンク

問題概要

個の袋があって、それぞれには

• 激辛バナナが 本
• 美味しいバナナが 本

がある。先手と後手が以下のことを交互に行う。

• 激辛バナナを 0 本または 1 本取り出す
• 美味しいバナナを好きな本数だけ取り出す
• ただし、激辛バナナと美味しいバナナとを合計して 1 本以上取り出さなければならない

先に操作を行えなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか？

制約

• 

考えたこと

いかにも Grundy (Nim)！！！！！
やるべきことは明らかで、それぞれの袋の Grundy 数を求めればよい。Grundy 数は DP で求められるが、 もの状態空間は扱えない。よって、きっと何かしら規則があるはず。それを見出すために、手かコンピュータで実験をしよう。

こういうとき、手で実験するか、コンピュータで実験するかはいつも迷う。まずは手で簡単に実験してみて、その範囲で求められればそれでよくて、糸口がつかみきれなかったらコンピュータでの実験に踏み切るのがちょうどよさそう。

Grundy 数を手で求めるとこんな感じ。たとえば赤マスの値を求めるためには、赤マスから 1 手で行ける場所である黄色マスについての Grundy 数を並べてあげて

0, 1, 2, 3, 4, 5, 7

これを 0 から順に見ていって、最初に途切れる数値が答えとなる。つまり赤マスの値は 6 になる。

この表を埋めると、右上の方は になっていることがわかる。そして左下の方の値は交互に入れ替わっている様子がみてとれる。具体的には、下図の赤ラインより上 (赤ライン含む) においては となっていて、それより下については「2 つ上の値と等しい」という感じになっている。

具体的には、以下のようになる

long long Grundy(long long H, long long B) {
    if (H <= B + 1) return H + B;
    if ((H - B) % 2 == 0) return B * 2;
    else return B * 2 + 1;
}

以上をまとめて、コードはこんな感じで通った。計算量は 。

#include <bits/stdc++.h>
using namespace std;

long long Grundy(long long H, long long B) {
    if (H <= B + 1) return H + B;
    if ((H - B) % 2 == 0) return B * 2;
    else return B * 2 + 1;
}

int main() {
    int N; cin >> N;
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        long long H, B;
        cin >> H >> B;
        res ^= Grundy(H, B);
    }
    if (res) cout << "matsu" << endl;
    else cout << "prd" << endl;
}