7K12 blog

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

ARC017 C - 無駄なものが嫌いな人

f:id:tkr987:20210721151857p:plain

  • N=32 は半分全列挙

f:id:tkr987:20210721160559p:plain

https://atcoder.jp/contests/arc017/submissions/24169529

ナップサック問題っぽい文章なのでナップサックDPではないと予想する(ぇ そもそも X が  10^9 なので DP で処理するのは無理と分かる。
ここで N が 32 しかないことから半分全列挙したくなる気分になる( 2^{16} = 65536 なので)。 N 個の品物を半分ずつビット全探索しながら W 合計を map などでカウントしたものを S と T とすると S[i] × T[X-i] の合計が答えになる。計算量は  O(2^{N/2} \log 2^{N/2})

感想: 半分に分けるときに片方ceilしわすれて無限時間かかった