Ecasdqina's MEMO

Ecasdqina's MEMO.

メモ帳.

ABC060-D Simple Knapsack 解説

問題

D - Simple Knapsack

解説

問題名からナップザックDPをまず思いつきますが, 制約を見ると w_i\le 10^9かつ v_i\le 10^7だということが分かります, よって普通にやるとMLEかつTLEとなってしまいます.

ところが制約をよく見ると w_1\le w_i\le w_1+3という奇妙なものがあります, これを変形すると 0\le w_i-w_1\le 3となり, 重さが4種類のみであることがわかります.
この考察に加え, 個数の制約が100と小さいことを考えると O(N^4)の全探索で行けそうだと分かります.

さて, ここまで来れればあとは同じ重さの物をどういう順序でとればいいかということになりますが, これは単純に価値でsortしたものを貪欲に取ればよいです.
また, 価値と重さの取得をO(1)でするために各重さで累積和を取ればTLEを回避できます, オーバーフローに注意して実装しましょう.

コード

Submission #1675923 - AtCoder Beginner Contest 060

感想

見たことがあるからといって解法が同じだとは限らない.