yukicoder #361: 門松ゲーム2

すごい今更ですけど門松シリーズの解説に於いて門松列の定義は省略してます許してください。

問題

No.361 門松ゲーム2 - yukicoder
kado君とmatsu君が交互に竹をを満たす門松に分割していくゲームを行う。これ以上竹を分割できなかったほうが負である。
初期状態の竹の長さLとDが与えられた時に両者が最適にプレイしたらどちらが勝つか答えよ

考えたこと

どう考えてもgrundy数です。
grundy数について復習すると、長さLの竹を(a,b,c)に分割した時、(a,b,c)の状態のgrundy数はgrundy[a]^grundy[b]^grundy[c]である。
grundy[L]は、分割できるすべての状態に対するgrundy数の集合 {grundy[a]^grundy[b]^grundy[c] (a+b+c=L, max(a,b,c)-min(a,b,c)<=b, a,b,cは門松列) }に含まれない最小の0以上整数。

コード

pythonで500^3くらいの実装したら（そもそも実装おかしかったんだけど）TLE返してきたのでC++にチェンジ。

int main(){
   int L,D;
   cin >> L >> D;
   vector<int> grundy(L+1,0);
   for( int i = 6; i <=L; i++ ){
      set<int> grundies;
      for( int x=1; x<=L; x++ ){
         for( int y=x+1; y<=L; y++ ){
            int z = i-x-y;
            if( z <= y ) continue;
            if( z-x >D ) continue;
            //cout << i<<"->"<<x<<","<<y<<","<<z<<endl;
            grundies.insert(grundy[x]^grundy[y]^grundy[z]);
         }
      }
      for( int g = 0 ; g < 500; g++ ){
         if( grundies.find(g)==grundies.end() ){
            grundy[i]=g;
            break;
         }
      }
      
   }
   if( grundy[L] == 0){
      cout << "matsu"<<endl;
   }
   else{
      cout <<"kado"<<endl;
   }
   return 0;        
}

後で試してみたところ、頑張ればpythonでも通りました。
pythonで通すためには、
分割範囲の上限・下限をちゃんと求める（ループ内でif文判定をしない)ことと、
分割後のgrundy数の集合の取り方を工夫する必要がある（少なくともsetとか重複付きリストとかじゃ最大ケースでTLEだった)。
既存のpython3で提出していたrpy3cppさんのコード#87862 No.361 門松ゲーム2 - yukicoderを確認にしたところ、grundy数の上限値は高々Lであるので、
長さLのbool行列Bを作っておいて、分割後のgrundy数に対応する場所をTrue埋めしてenumerate(B)を回すのが賢い方法。
言われてみれば確かにsetとか使う必要無いなあ。

L,D=map(int,raw_input().split())

ans=[0 for i in range(L+1)]
for i in range(6,L+1):
    grundies=[False for j in range(L)]
    for j in range(max((i-2*D)/3,1),(i+2)/3+1):
        for k in range(max(j+1,i-2*j-D),(i-j+1)/2):
            l=i-j-k
            num=ans[j]^ans[k]^ans[l]
            grundies[num]=True
    for a,used in enumerate(grundies):
        if not used:
            ans[i]=a
            break
if ans[L]==0:
    print "matsu"
else:
    print "kado"