Easyは解けたもののチャレンジミスとかしてグダグダだった。
https://community.topcoder.com/stat?c=problem_statement&pm=14426
問題
N個の意思を2人で交互に取り合うゲームを行う。
先手は正整数の集合A,後手は正整数の集合Bに含まれるいずれかの数の分石を取る。
石を取れなくなったら負けである。
互いに最適手を取る場合、勝者はどちらか。
解法
Nの上限が大きいのでNim+Grundy数に持ち込んでも間に合わない。
A,Bの要素が小さいので、一度Nが小さい範囲でNがどの値の時にどちらが勝つかシミュレートしてみよう。
ある程度以上大きくなると、勝者が周期性を持つことがわかる。
あとは周期性を用いてNを小さくすればよい。
以下のコードは、実際にA,Bを総当たりで試すと周期が高々1~10なので、それらのLCMである8*9*5*7で周期性があることを仮定している。
class PartisanGame { public: string getWinner(int n, vector <int> a, vector <int> b) { const int D=10000; int F[D+2]={},G[D+2]={}; for(int i=1;i<=D;i++) { FORR(r,a) if(i>=r && G[i-r]==0) F[i]=1; FORR(r,b) if(i>=r && F[i-r]==0) G[i]=1; } if(n>D) n = 8*9*5*7+(n-8*9*5*7)%(8*9*5*7); return (F[n]?"Alice":"Bob"); } }
まとめ
実装は軽いのに、なんで300ptなんだろう。
法則見つけるのに時間がかかるから?