DPまとめコンテスト K - Stones

K - Stones

概要

数列を用いて、二人が次のようなゲームを行う。

• 最初は石が個ある
• 自分の手番には、数列の中から1つの数を選び、その数だけ石を減らす。ただし、残りの石の個数より多いような数列の数を選んではいけない

最初に操作できなくなった方を負けとする。どちらが勝つかを判定せよ。

制約

、は狭義単調増加

方針

:残りの石が個のとき、先手が勝つかどうか　とする。
DPの遷移としては下記の通り。

• 石が0個の時は先手の負け
• 石が残り]個の時に先手必敗とすると、石が残り個のときに先手が]を選択すると先手が勝てるため、石が残り個の時は先手必勝

（配列の小さい方から先手必敗のケースを順に見てゆき、そのケースの1手前が先手必勝になるイメージ）

解答

Submission #3969759 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n, k;
	cin >> n >> k;
 
	int a[n];
	rep(i, n) cin >> a[i];
 
	bool dp[k+1];
	// dp[i]:石が残りi個のとき、先手が勝てるか
	rep(i, k+1) dp[i] = false;
 
	for(int i = 1; i <= k; i++){
		for(int j = 0; j < n; j++){
			if(i >= a[j]){
				dp[i] |= !dp[i-a[j]];
			}
		}
	}
 
	cout << (dp[k] ? "First" : "Second") << endl;
}