SRM450 div1 easy
ルールを変えたNimでAliceとBobのどちらが必勝かを判定する問題
ルール:
石が1個以上ある山がいくつかある。
プレイヤーは毎回、一つの山から石を1個以上とる。
山は順番に並んでおり、1個以上石が存在する山のうち一番左の山からしか石をとることはできない。
最後に山をとったものが勝ち
解法
ある状態のとき、そのときの取る手番の人が勝つか負けるかは決まっている。
取る山に石が1個だけのとき、手番の人は必ずその1個を取る。
取る山に石が1個より多いとき、手番の人は、石を山に1個だけのこすorすべて取る、を選択できる。
よって自分の手番のとき山に石が1個より多くあれば、次の山のときに自分の番にするか相手の番にするかを自由に決めることができるので必勝である。
よってAliceとBobのどちらが勝つかは最初の連続した1が何個あるかの偶奇で判定できる。
#include <cstdio> #include <string> #include <vector> #include <algorithm> using namespace std; class OrderedNim{ public: string winner(vector <int> layout){ int one = 0; for(int i = 0; i < layout.size(); i++){ if(layout[i] == 1) one++; else break; } if(layout.size() == one) one++; return (one % 2 == 0) ? "Alice" : "Bob"; } };