典型問題をちょっと変えただけなのになかなか手こずった話
典型的なナップサック問題をちょいっとひねった問題。具体的には、制約が異なる。普段通りのdp配列にidx,weightで二次元配列を作るだけだと上手くいかないよって問題。
以下問題
https://atcoder.jp/contests/dp/tasks/dp_e0
何が難しかったか
dpテーブルが異なること
制約が異なることでいつも作っているdpテーブルが作れないこと。さらに厳密に言うと漸化式が異なることが問題であった。典型ナップサック問題の考え方を理解していたが上手く解けなかった。dpテーブルに格納する内容が直感と反していたこと
今回の問題ではidx、valueの二次元配列を作成する。ナップサック問題で重要視される要素はidx、weight、valueの三種類のため残ったweightを格納することになる。ここでweightの最小値か最大値かどちらを入れれば正常に動くか理解していなかった点である。
解決方法
典型ナップサック問題は配列の値に最大の価値を格納しそれを出力する。今回の漸化式で必要になる考え方も同様であるが、今回はその価値に対する重さを最小化することが目標となる。イメージとしては典型ナップサック問題ではナップサックの容量を変化させていくのに対して、この問題では価値を変更させていくのである。そして最後に全ての要素の最小値を見つけたところから探索しなければいけない点も問題を複雑化しているように感じた。
まとめ
- dpテーブルの配列番号に何を振るかをまず考えることが大事
- 漸化式を作成したら、そのブロックはどのような値が入るか意識する
- 最終的な値は$O(1)$で出ない可能性もあること