すごく面白かった!
問題概要
個の袋があって、それぞれには
- 激辛バナナが 本
- 美味しいバナナが 本
がある。先手と後手が以下のことを交互に行う。
- 激辛バナナを 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; }