ABC219 参加記録 - geam1113’s diary

コンテスト中AC:A〜C

戦績が良くなかったので、コンテスト後に解けたDだけ書きます。

購入したお弁当の個数の情報と、その時のたこ焼き及びたい焼きの個数の情報が欲しいので、以下のDPを考えます。

$dp[i][j][k]:=$ $i$ 種類目までのお弁当のうち $j$ 個のお弁当を購入して $k$ 個のたこ焼きを手に入れた場合のたい焼きの個数の最大値

たこ焼きの個数は、最大でも90000個手に入りますが、 $X$ の制約上300個までを考慮すればよいので、301個以上手に入る場合は300個手に入ったことにしても問題ありません。

初期値は、 $dp[0][0][0]=0$ です。次に、 $dp[i][j][k]$ からの状態遷移を考えます。

$i+1$ 番目のお弁当を購入しない場合、状態に変化はありません。よって、

$dp[i+1][j][k]=dp[i][j][k]$

$i+1$ 番目のお弁当を購入する場合、お弁当の個数は1個増えて、たこ焼きの個数は $A_{i+1}$ 個増えます。よって、

$dp[i+1][j+1][k+A_{i+1}]=max(dp[i+1][j+1][k+A_{i+1}],\ dp[i][j][k]+B_{i+1})$

但し、 $dp[i][j][k]$ が状態として存在する時のみ遷移可能であり、また、 $k+A_{i+1} \geq 301$ の時は $300$ とすることに留意します。

答えは $1 \leq j \leq N,\ X \leq k \leq 300$ について、 $dp[N][j][k] \geq Y$ が成り立つような最小の $j$ です。

計算量は、 $i,j,k\leq 300$ なので、最大でも $10^7$ 程度となります。