この手の問題死ぬほど苦手。1800diffなのに分からなかった…
問題概要
石を積んだ山が $N$ 個ある。
$i$ 個目の山に石が $A_i$ 個積んである。
プレイヤーは交互に山を $1$ つ選んでそこから石を $1$ つ取るが、前のプレイヤーと同じ山から石を取ってはならない(最初の先手だけはどこから石をとってもよい)
先手と後手どちらが勝つか?
$1 \le N \le 100$
$1 \le A_i \le 100$
山ごとのパリティを考えたのがドブだった…
このゲームのカギは「過半数」と「完全マッチング」。
(i) 過半数の石を持つ山がある場合
先手必勝。先手が最多数の石を持つ山から石をとってしまえば、手番が回ってくればそこから取るのを繰り返せば勝てる。
(ii) 過半数の石を持つ山が無い場合
(ii)-1 石の総数が偶数の場合
後手必勝。石の総数が偶数かつ過半数の石を持つ山がないので、相異なる山にある石同士で完全マッチングが成立し、先手の行動に合わせて後手は適切な山から石を取れる。
(ii)-2 石の総数が奇数の場合
先手必勝。先手は最初適当な山から石を取り(どうやっても「石の総数が偶数かつ過半数の石を持つ山がない」状況に出来る)、その後、後手の着手に対して(先手後手が入れ替わった状況で)先述の完全マッチングに従い石を取っていけばよい。
ゲームってなんか解けないと悲しくなりませんか?苦手です…
