問題概要
N 個の石の山があって、i 番の山には number[ i ] 個の石が含まれる。この石たちを使ったターン制の二人ゲームをする。各ターンは次の手順からなる。
- 2 つ以上の石を含む山を一つ選び、X とする
- X の石を全て取り、空でない二つの部分に分け、それぞれを A, B とする
- 空でなく、X ではない二つの山 Y, Z を選び、A を Y に、B を Z にそれぞれ全て加える
自分のターンで有効な操作が無くなったプレイヤーは敗北となる。
山の情報が与えられる。それぞれのプレイヤーが最善を尽くすとき、先攻のプレイヤーが得る結果を求めよ。
解法
あるターンで操作可能かどうかは二つのパラメータ、「 2 つ以上の石を含む山の数」「全体の山の数」に依存します。全体の山の数についてはほぼ自明で、ターン毎に 1 ずつ減少していきます。他方、2 つ以上の石を含む山の数はどう変化するでしょうか? あるターンで選ばれた Y, Z は次のターンで必ず 2 つ以上の石を含んでいるので、あるターンで操作が可能だった(そして該当プレイヤーによって操作された)とすれば、次のターンに X として選べる山は必ず一つ以上存在します。従って、最初のターンに操作が可能であれば、操作が不可能になるのは Y, Z を選べなくなったとき(=全体の山の数が 2 以下になったとき)に限られます。先程書いたように山の数の減少はターン毎に 1 なので、この条件が成立するのがどちらのプレイヤーのターンであるかは、初期の山の数の奇偶だけで決まることになります。
一回以上操作があった場合は山の数の奇偶で勝敗が決まるので、最初のターンで操作が可能か否かを求められれば問題を解けます。最初のターンで操作が可能であるためには、初期状態で X, Y, Z を選べればよいので、山が 3 つ以上存在し( X, Y, Z は相異なる)、かつ 2 つ以上の石を含むものが存在する(X に関する制約) を同時に満たせばよい、ということになります。
まとめると、先攻が勝つ場合というのは、初期状態で山が 3 つ以上存在し、その内 1 つ以上は 2 つ以上の石を含み、且つ全体の山の数が奇数であるとき、と言えます。
コード
#define ALL( c ) (c).begin(), (c).end() class SplitStoneGame { public: string winOrLose( vector <int> number ) { const int N = number.size(); const int num = count_if( ALL( number ), bind( less<int>(), 1, _1 ) ); return num && 3 <= N && N % 2 ? "WIN" : "LOSE"; } };