ABC145-E All-you-can-eat
概要
ナップサック問題を解く。一つだけカバンに入れず持ち歩ける。個数は3000個まで、価値、重さはそれぞれ[1, 3000]、入れられる最大の重さは[1, 3000]。最大の価値は？
ACするまで
1. ナップサックだね。
2. オーバー判定を書いておいた。投げる
3. WAWAWAWAWAWAWA...
4. 終了10分前に気づく、これは普通のナップサックで成り立つ商品の選ぶ順番の可換性が成り立たない。
5. 焦りの中の考察でコンテスト時間TLE。
6. 周りを見ると3種類の解法があった。それぞれ実装してAC。
考察
この問題は、僕の知ってる限り3種類のアプローチができる。(解説は2つ)それぞれ典型といえるアプローチであり、抑えるべき。解けないのが一層悔しい問題ともいえる。
解法1 両側からDP(公式解法1)
この問題の本質は、1種類の料理だけ抜いてT-1までの時間で得られる最大の満足度を計算して、その1種類は時間オーバーで注文したとしておいしさだけ加算して時間は加算しないで得られる最大のおいしさである。
どれを最後に時間オーバーさせて食べるのは、全探索すればよい。(この時時間オーバーを実はしない組み合わせは誕生する可能性があるが、答えの対象は時間オーバーする方としないほうの両方であるため)そうすると、いかに効率よく1種類の料理を抜いた状態でのおいしさを求めることに尽きる。
愚直にやると、料理を1種類毎回抜いてDPをを掛けて計算することになり、全体では
となる。
その時、次のリンクの二番のテクをうまく使うと、に収まる。
いくつかの要素を抜くDP No Needから考える - Senの競技プログラミング備忘録
実装時は添え字に注意し、細心に実装すること。
解法2 貪欲法をプラスしたDP(公式解法2)
さて、ここで食べる料理の一覧が定まってるとします。いい感じの順番で食べれば時間内に食べ終わるかどうかはどう判定するでしょう？
このサブ問題を考えると割と自明に、
所要時間が短い料理から順に食べる
とわかる。証明としては、一番後ろの料理にかかる時間が無視されるので、一番食べるのに時間がかかる料理を後ろにもっていくことで所要時間を最短にすることができる。
さて、これはどんな料理の選び方をするときでも共通するので、ひとまずかかる時間が昇順になるように料理をソートする。
そこからこう考えることができる。
いい感じに[0, i]まで選んだあと、最後に時間に計上しない i+1 品目の満足度を加算したものの最大値。
こうすることで、解法1では両側からDPをしたが、これは左端からのDPを一つするだけで問題がない。DPをしつつ、今の料理の時間をノーカンした時の最大の満足度を更新し続ければよい。
具体的な実装としてはACソースコードを参照：
Submission #8491799 - AtCoder Beginner Contest 145
簡単にまとめると、物を選ぶなどの時に、貪欲に決まるような性質を持ってる時は、これをうまく利用できる場合がある。今回はコーディングの煩雑度が下がる。
解法3 フラグ持ちながらDP
これは少ないなにかしらの状態が(された/されてない)のを区分しつつDPする場合の典型テクである。このテクで実装する場合、元の状態を考慮しないDPからの拡張が容易であることが多い。
今回の問題としては、最終的に選んだ料理の集合における順番は入れ替えてはならない、という特性を持ってる。なぜならば、どれを最後に注文するのが分からないからだ。
しかし、この状態を次のように言い換えられる。
一旦最後に頼む料理さえ決まれば、それ以外の料理の集合に対してはナップサック問題となる。(これはほかの2つの解法の根幹ともなる情報)
つまり、
普通のナップサックに、「最後に注文する料理を既に選択したかどうか」というフラグを付けた状態。
これは、上で述べたフラグ付きDPの適用可能状態と一致する。
よって、これを実装すればよい。具体的な実装はソースコードを参照。
ACソースコード：
Submission #8491104 - AtCoder Beginner Contest 145
一言
典型の宝庫。悔し泣きしながら書いた。
