Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 270 D問題 Stones

AtCoder ABC270 ABC D問題 400 pts

問題

提出解答

問題の概要

高橋君と青木君が次のようなゲームを行った.

$N$ 個の石からなる山が1つある.
山に石がある限り, 高橋君から交互に以下の行動を行う.
- その時点で山にある石の数を $M$ とする. $A_i \leq M$ となる整数 $i$ を選び, 山から $A_i$ 個の石を取り除き, $A_i$ 点と獲得する.

2人とも獲得する得点を最大化するように行動した場合における高橋君が獲得する得点を求めよ.

制約

$1 \leq N \leq 10^4$
$1 \leq K \leq 100$
$1=A_1 \lt A_2 \lt \dots \lt A_K \leq N$

解法

動的計画法で解くことにする. $x=0,1,2, \dots, N$ に対して, ${\rm DP}[x]$ を

山に石が $x$ 個ある状況で自分のターンが回ってきたときに, そこから更に獲得する (自分の得点) - (相手の得点) *1

と定義する.

ベースケースは $x=0$ の場合でこの場合, ゲームが直ちに終了するので, ${\rm DP}[0]=0$ である.

更新式について, $A_i$ 個の石を取り除いたとする. このとき, 残りの石の数は $(x-A_i)$ 個となるが, 次に着手するのは相手である. よって, ${\rm DP}$ の定義から, ${\rm DP}[x]$ は

$\displaystyle {\rm DP}[x]=\max_{\substack{1 \leq i \leq N \\ A_i \leq x}} \left(A_i-{\rm DP}[x-A_i] \right)$

である.

ゲーム終了後, 高橋君, 青木君が獲得する得点を $X,Y$ とすると, 高橋君が先攻であったから, $X-Y={\rm DP}[N]$ が成り立つ. また, ゲームのルールから $X+Y=N$ も成り立つ. これにより, 求めるべき答えは

$X=\dfrac{N+{\rm DP}[N]}{2}$

であることがわかった.

*1:全体の得点に関する引き算ではない