BoB003-F: Limited Edition

2 secs 1024 MB
kyaneko999

解説


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

  • 番目までのプラモデルについて合計金額が に等しいような購入の仕方は存在するか(存在するならば ,そうでなければ
  • ならば,

この方針では, は最大で まで考える必要があるため,計算量は となり制限時間に間に合いません.

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

  • 番目までのプラモデルについて合計金額が に等しいような購入の仕方は存在するか
  • ならば,

こうすることで, は最大で まで考えれば十分です,
合計金額が と等しくなるような購入の仕方が存在するかどうかは, として から判定を行うことができます.
の値が DP テーブルからはみ出してしまう場合には例外処理が必要ですが,答えは常に No になります.
計算量は から変わりませんが,定数倍が約 になったことで問題を解くことができます.

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

解答例(Python)