7K12 blog

猫でも分かるアルゴリズム解説

CPSCO2019 Session1 C - Coins

f:id:tkr987:20200726204201p:plain

https://atcoder.jp/contests/cpsco2019-s1/submissions/15470682

  • Kが小さいのでK種類の商品を全探索する
  • 大きい硬貨から貪欲に支払いを構成する

f:id:tkr987:20200726214314p:plain

Nが32なので 2^N全探索はできないが、Kが最大6なので _N C_K個の全探索は出来そうという気持ちになる。小さい硬貨で支払うと使う枚数が増えてしまうため、大きい硬貨から貪欲に支払金額を構成する。K個の A_i合計を全列挙するために、蟻本p144に載っているアルゴリズムを使って _N C_Kのビットテーブルを作る。全体計算量は O(_N C_K)