SRM450 Div2 250,500
250
文字が変わる所の回数を数えるだけ。
500
i番目がAliceだったときどちらが勝つかを保持するdp[i]を考える。n=layout.size()。
(n-1)番目でAliceなら全部取ってAliceの勝ち。
(n-2)番目でAliceの場合、layout[n-2]==1なら取らないといけないのでBobの勝ち、layout[n-2]>1ならdp[i+1]がAliceなら1個だけ残して全部取ればAliceの勝ち、dp[i+1]がBobなら全部取ればAliceの勝ち、、、
ということで、layout[i]==1の時はdp[i]={dp[i+1]の逆の人}で、layout[i]>1の時はdp[i]=Aliceというのを逆からdpした。
class OrderedNim { public: string winner(vector <int> layout) { if(layout.size()==1) return "Alice"; int ret[51]; rep(i,51) ret[i]=0; for(int i=layout.size()-2; i>=0; i--) if(layout[i]==1) ret[i] = 1-ret[i+1]; if(ret[0]==0) return "Alice"; else return "Bob"; } };