かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

JOI2014本選 B - IOI饅頭（IOI Manju）

競技プログラミング 解説 JOI DP高速化 動的計画法

問題はこちら

問題概要

価格{P_i}の{1\le M\le 10^4}個の饅頭, 入る饅頭の個数{C_j}で価格{E_j}の{1\le N\le 500}個の箱が与えられるので箱をいくつか買って饅頭を詰めて売るときの利益の最大値を求めよ.

思考の流れ

詰める饅頭は高いものから.
饅頭を{i}個詰められる箱の選び方で最小の値段のものを選べばいい.

{\downarrow}

ナップサック問題っぽいので{dp[i][j]}を「{i}番目の箱まで見た時に, 饅頭を{j}個詰められる箱の選び方での最小の値段」とおいてDPを行えばよさそう.
更新式は

{dp[i][j] = \min(dp[i][j+1],dp[i-1][j-C_i]+E_i)} となる. jの大きい方から更新していけば「{i}番目の箱まで見た」という条件が必要なくなるので空間計算量を削減できる.
結局,{dp[j]}を「饅頭を{j}個詰められる箱の選び方での最小の値段」とおいて

{dp[j] = \min(dp[i][j+1],dp[j-C_i]+E_i)}

このままだと時間計算量は{O(N^2\max C+M\log M)}なので間に合わない

{\downarrow}

「饅頭を{j}個詰められる」としてしまうと{0\le j\le N\max C}だが, 詰める饅頭の数は{M}個以下なので{0\le j\le M}となる. {dp[M]}の更新式だけ変える必要があるので注意.
時間計算量は{O(NM+M\log M)}となり, 十分高速.

提出プログラム

https://atcoder.jp/contests/joi2014ho/submissions/11915138

感想

解法はすぐ浮かんだが2つ目の矢印を無視して提出してしまってTLE, その後AC. DP高速化ってわけでもないが条件から計算量を削減できないか考えた方がいいと感じた.