解いた問題

2/05/2012

SRM450 Div1 Easy

250
その場面で注目している山の石の個数が複数であれば、その山に最初に手を付けられるプレイヤーが "石を全て取る" or "1つだけ残す" の選択をすることで、次の山に手を付けるプレイヤーを決定できる。
つまり、全ての山の石が複数なら、先手必勝になる。
しかし、石の数が1つの場合はどうしてもプレイヤーがいれ変わる。
なので、最初に複数個の石からなる山に手を付けたプレイヤーの必勝。
山の石が1だけの場合は例外で、山の個数を見て判断する。
class OrderedNim {
public:
  string winner(vector <int> L)
  {
    if (count(L.begin(), L.end(), 1) == L.size()) {
      return L.size() % 2 ? "Alice" : "Bob";
    }
    int cnt = 1;
    for (int i = 0; i < L.size(); ++i) {
      if (L[i] != 1) break;
      ++cnt;
    }   
   
    return cnt % 2 ? "Alice" : "Bob";
  }
};

0 件のコメント :

コメントを投稿