POJ-1740 : A New Stone Game
問題概要
山がN個あって各山には石がいくつか置かれている。ふたりでゲームを行う。各プレイヤーは山を一つ選び、石を1個以上取り除く。また、その山に残っている任意個の石を他の山に移すことができる。この際移す山の対象はいくつあってもよい。最後の石をとった方が勝ちになる。勝つのが先手か後手か判定する問題。
解法
山の石の数を数えて、奇数回出現する数が存在するときのみ勝ちになる。証明はこの手問題の定石どおりに行う。
まず、偶数しかない状態からは必ず奇数が存在することにしか行けないことは比較的簡単に分かる。
奇数回出現する数が存在する時は、そのような数の中で最も大きい山を選び、その山を使って他の奇数回出現してるのをならしてやり、残りを捨てれば偶数しかない状態に遷移できる。
acceptされたコード
#include <cstdio> #include <cstring> using namespace std; const int MAX_N = 10; const int MAX_K = 100; int N; int xs[MAX_N]; int ks[MAX_K + 1]; bool init(){ scanf("%d", &N); for(int i=0; i<N; ++i){ scanf("%d", xs+i); } return N > 0; } bool solve(){ memset(ks, 0, sizeof(ks)); for(int i=0; i<N; ++i){ ks[xs[i]]++; } for(int i=1; i<=MAX_K; ++i){ if(ks[i]&1){ return true; } } return false; } int main(){ for(;init();){ printf("%d\n", solve() ? 1 : 0); } return 0; }