今回は初めてEasyの目途が全くつかず、かなり適当な解を提出して案の上チャレンジで落とされた。
幸い、ラスト数分でMediumが通せたのでひどいことにはならなかったが…。
http://community.topcoder.com/stat?c=problem_statement&pm=12496
問題
自然数Cが与えられ、２人でゲームを行う。
各人自分のターンでは、1とC以外の約数を選び、それをCから引く。
1とC以外の約数が無ければ負け。
両者が最適な行動をとる場合、Cに対する勝者を答える。
本番、これはnimかもしくは選択肢がない状態に持ち込めれば勝ちだと思った。
数が素数Pになると負けなので、そうすると自分が2*Pを取ってPを引けば良いなと思ってたけど、2*Pになるには3*Pまたは2*(P+1)で相手が2*Pにしてくれないといけないんだよなーとか考えたり。
ここで、地道に全パターン列挙するのは多分ないんだろうなと思った。
列挙すると、素数に対しても１足したり引いたりしつつ何度も素因数分解する必要があるので、C<=10^18という範囲では間に合わない。
結局、「2×素数なら勝ち」みたいな適当解を出してミス。
周りの解を見ると、初期値Cが２の奇数乗または奇数なら後手の勝ち、それ以外は先手の勝ちとなるようだ。
ここでの最適手は、相手に選択肢を与えないこと。
奇数に対しては、それが素数なら負けだし、そうでないなら約数は奇数なのでターン後は偶数になる。
偶数の場合は常に選択肢が存在する。ただ、それが２の奇数乗の時だけは互いに値を半分にしていく手を繰り返すと負ける。
class TheNumberGameDivOne { public: string find(long long n) { int i; for(i=1;i<=63;i+=2) if((1LL<<i) == n) return "Brus"; if(n%2==1) return "Brus"; return "John"; } }
まとめ
本番全然方針が立たず。Easyでこれとは…。
Forumや直後のチャットを見ると、「証明はできないけど途中まで列挙したらそうだったからそうした」と言った回答が目立った。
実際これみんな自信もって回答したのかな…？
以下の２つを頭に入れとくべきってのが今回の反省。
- nimが使えない場合は「相手に選択肢を与えない手が勝ち」パターンを考える
- 小さな数で試して傾向を見る
近いものとして、GCJ2010 R1A-Cを思い出した。
これも「相手に選択肢を与えない手が勝ち」だったね。
https://code.google.com/codejam/contest/544101/dashboard#s=p2
