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";
  }
};