けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

すごく面白かった!

問題へのリンク

問題概要

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

  • 激辛バナナが  H_{i}
  • 美味しいバナナが  B_{i}

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

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

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

制約

  •  1 \le N \le 10^{5}

考えたこと

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

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

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

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

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

f:id:drken1215:20200229224959p:plain

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

f:id:drken1215:20200229225342p:plain

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

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

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

#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;
}