AtCoderBeginnerContest270 D 問題 400 点 「Stones」

問題リンク

問題概要

制約

解法

貪欲にやっていくことがなんとなく悪いことはわかる。自分ができるだけ取りつつ，相手にはできるだけ取らせないようにしなければならないので，このような問題には貪欲法を用いることはできない。凡例は解説にあるので確認すること。
ここで，DP を以下のように定義する。

$dp[i]$: 石が$i$個あったときの先手が得られる石の最大値

このように定義すると，後手の計算も実は同時にできることがわかる。先手が$A_j$個石を取ったときの後手は最大で$dp[i-A_j]$個の石を獲得できることになる。

したがって，更新式は以下のようになる \(dp[i] = max(dp[i], i - dp[i-A_j]\) ここで，$i$は現在の石の個数，$dp[i-A_j]$は後手が得られる石の数の最大値となる。これを石が 0~N 個あった場合を昇順に計算することで，石が N 個あったときの先手が得られる石の最大値$dp[N]$を求めることができる。

計算量は，DP テーブルの更新に$\mathcal{O}(N)$,最大値を求めるのに$\mathcal{O}(1)$なので，全体の計算量は$\mathcal{O}(N)$で求めることができる。

お気持ち

AC コード

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
dp = [0] * (N + 1)
for i in range(1, N + 1):
    for a in A:
        if i - a >= 0:
            # dp[i-a]:i 個の石があって，
            # 先手がi個取ったときに後手が取れる石の数
            dp[i] = max(dp[i], i - dp[i - a])
print(dp[N])