[学習記録]AtCoder EDP K-Stones[Go]

問題

N 個の正整数からなる集合 A={a1​,a2​,…,aN​} があります。 太郎君と次郎君が次のゲームで勝負します。

最初に、K 個の石からなる山を用意します。 二人は次の操作を交互に行います。 先手は太郎君です。

• A の元 x をひとつ選び、山からちょうどx 個の石を取り去る。

先に操作を行えなくなった人が負けです。 二人が最適に行動すると仮定したとき、どちらが勝つかを判定してください。

解法

 i 個の石で、j 番目まで使って勝負するDPを考える
太郎君がとれる行動は、

1. 石を全てとり、勝ちが確定

2. 操作を行えず、負けが確定

3. 石をいくつかとり、相手に手番を渡す

の３つになっている。

１．ちょうど取れた時点で勝ち確定するのでbreak
２．全て確認するまでわからないので、continue
　　→　操作を行えない場合には win := falseが入る

// i個の石で、j 番目まで使って勝負
// 1が勝っていたらdp = true
for i := 1; i <= k; i++ {
	win := false
	for j := 0; j < n; j++ {
		x := sli[j]

		//  1. ちょうどとったら勝ち
		if i-x == 0 {
			win = true
			break
		}

		// 2. 取る量が多く操作できない
		if i < x {
			continue
		} 
　　　　　　　
　 　　　// 3. 相手に渡す
	}
	dp[i] = win
}

相手に手番を渡した場合、
「相手が石の残数 i - xからスタートした時の勝利結果」
に依存しする。
相手が勝ち > 自分が石 xをとると自分がまける
相手が負け > 自分が石x をとると自分がまける
よって、DPに格納された値の逆をセットすればいい。

// 相手に手番をわたした場合
win = !dp[i-x] || win

答えは石K個使った時の値になる。

コード（AC)

func run() {
	n, k := readInt(), readInt()

	sli := readSli(n)
	dp := make([]bool, k+1)


	// i個の石で、j 番目まで使って勝負
	// 1が勝っていたらdp = true
	for i := 1; i <= k; i++ {
		win := false
		for j := 0; j < n; j++ {
			x := sli[j]

			// ちょうどとったら勝ち
			if i-x == 0 {
				win = true
				break
			}

			// 取る量が多く操作できない
			if i < x {
				continue
			}

			// 相手に手番をわたした場合
			//   > DPに格納されている値と逆の値になる
			win = !dp[i-x] || win
		}
		dp[i] = win
	}

	ans := dp[k]
	if ans {
		fmt.Println("First")
	} else {
		fmt.Println("Second")
	}
}