Kazun の競プロ記録

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

AtCoder Beginner Contest 261 D問題 Flipping and Bonus

AtCoder ABC ABC261 D問題 400 pts

問題

提出解答

問題の概要

$N$ 回のコイントスを行う. また, $0$ で初期化されているカウンタを持っている.

$i$ 回目のコインの表裏によって, 以下を行う.

表の場合, $X_i$ 円貰い, カウンタを $1$ 増やす.
裏の場合, カウンタを $0$ にする.

ここで, $j=1,2, \dots, M$ に対して, 次のボーナスがある.

カウンタが $C_j$ になる度に $Y_j$ 円追加で貰える.

最大で何円貰えるか?

制約

$1 \leq M \leq N \leq 5000$
$1 \leq X_i \leq 10^9$
$1 \leq C_j \leq N$
$1 \leq Y_j \leq 10^9$
$C_1, \dots, C_M$ は全て異なる.

解法

$B_k~(1 \leq k \leq N)$ をカウンタが $k$ になった時に貰えるボーナス金とする. つまり,

$B_k=\begin{cases} Y_j & (\exists j~{\rm s.t.}~C_j=k) \\ 0 & ({\rm otherwise}) \end{cases}$

である.

動的計画法で解く. $0 \leq i \leq N, 0 \leq j \leq i$ に対して, ${\rm DP}[i,j]$ を以下で定義する.

${\rm DP}[i,j]$ を $i$ 回目のコイントスの後, カウンタが $j$ であるような表裏の結果の中で貰えるお金の最大値

とする.

ベースケースは $i=0$ のときの ${\rm DP}[0,0]=0$ である.

更新式について, $i \geq 1$ とする.

$j=1,2, \dots, i$ のとき, カウンタが $0$ でないということは, $(i-1)$ 回目のコイントス終了後のカウンタが $(j-1)$ であり, $i$ 回目のコイントスの結果が表でなくてはならない. 従って, 以下のように更新される.

${\rm DP}[i,j]={\rm DP}[i-1,j-1]+X_i+B_j$

$j=0$ のとき, $(i-1)$ 回目までの結果に関係なく, $i$ 回目のコイントスの結果は裏でなくてはならない. これは $(i-1)$ 回目のコイントス終了後のカウンタの値による場合分けを考えることにより, 以下のようになる.

$\displaystyle {\rm DP}[i,0]=\max_{k=0,1, \dots, i-1} {\rm DP}[i-1,k]$

このとき, 求めるべき最終解答は $\displaystyle \max_{j=0,1, \dots, N} {\rm DP}[N,j]$ である.

この動的計画法により, 時間計算量 $O(N^2)$ 時間で計算できた.