torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, SRM 619, Division 1, Level 1 : SplitStoneGame

問題概要

 N 個の石の山があって、i 番の山には number[ i ] 個の石が含まれる。この石たちを使ったターン制の二人ゲームをする。各ターンは次の手順からなる。

  1. 2 つ以上の石を含む山を一つ選び、X とする
  2. X の石を全て取り、空でない二つの部分に分け、それぞれを A, B とする
  3. 空でなく、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";
	}
};