BoB003-F: Limited Edition

2 secs 1024 MB
kyaneko999's icon kyaneko999

解説

一見すると,以下のような動的計画法(DP)で問題を解くことができそうです.

  • dp[i][v]dp[i][v]ii 番目までのプラモデルについて合計金額が vv に等しいような購入の仕方は存在するか(存在するならば 11,そうでなければ 00
  • dp[i1][v]=1dp[i-1][v]=1 ならば,dp[i][v+Ai]=dp[i][v+1.01×Ai]=1dp[i][v+A_i]=dp[i][v+\lfloor 1.01\times A_i \rfloor]=1

この方針では,vv は最大で N×max1.01×AiN\times\max\lfloor1.01\times A_i\rfloor まで考える必要があるため,計算量は O(N2maxAi)O(N^2\max A_i) となり制限時間に間に合いません.

ここで,通常版と限定版を選んだ場合の金額の差にのみ注目することで,上記のDPを以下のように改良します.

  • dp[i][v]dp[i][v]ii 番目までのプラモデルについて合計金額が A1+A2+Ai+vA_1+A_2\cdots+A_i+v に等しいような購入の仕方は存在するか
  • dp[i1][v]=1dp[i-1][v]=1 ならば,dp[i][v]=dp[i][v+0.01×Ai]=1dp[i][v]=dp[i][v+\lfloor 0.01\times A_i \rfloor]=1

こうすることで,vv は最大で N×max0.01×AiN\times\max\lfloor0.01\times A_i\rfloor まで考えれば十分です,
合計金額が KK と等しくなるような購入の仕方が存在するかどうかは,S=A1+A2++ANS=A_1+A_2+\cdots+A_N として dp[N][KS]dp[N][K-S] から判定を行うことができます.
KSK-S の値が DP テーブルからはみ出してしまう場合には例外処理が必要ですが,答えは常に No になります.
計算量は O(N2maxAi)O(N^2\max A_i) から変わりませんが,定数倍が約 1100\frac{1}{100} になったことで問題を解くことができます.

なお,元の方針の DP でも,C++ の std::bitset を用いて高速化すれば問題を解くことができます.

解答例(Python)