ABC153-E Crested Ibis vs Monster 個数制限なしナップサック問題について雑にまとめる
どうもこんにちは。毎度おなじみ鳥居です。
今回も例によって例のごとく、プログラミング初心者がプログラミング手法について雑にまとめていこうと思います。駄文雑文ご容赦くだ(ry
https://atcoder.jp/contests/abc153/tasks/abc153_e
さて、いきなりですがトキさんがモンスターと戦っています。
モンスターのヒットポイントと攻撃の種類が与えられ、それぞれの攻撃方法について攻撃力と魔力の値が設けられています(同じ攻撃方法を何度も選んでよい)。トキさんがモンスターを倒すまでに必要な魔力の最小値はいくらになるでしょうか？という問題です。
そして結論から言えばこの問題は「個数制限なしナップサック問題」という有名問題をアレンジした問題だそうです。
この「個数制限なしナップサック問題」について簡単に説明すると、
「入れることができる重さの最大値が定まったナップサックに、重さと価値がそれぞれ決められている荷物を、同じものを二つ以上入れてもよいという条件で入れたときに価値の最大値を求めよ」
という問題です。この場合ですと、重さの最大値をモンスターのヒットポイント、荷物の重さと価値をそれぞれトキさんの攻撃力と魔力に対応させればよさそうですね。
さあ、この問題はどう解くべきでしょうか。
以前動的計画法について(雑に）まとめたエントリで、各々の荷物を入れるか入れないかで分けて解こうとすると計算量がとんでもないことになると説明しました。さらに今回は個々の入れれる荷物の量も無制限ですので、その量も鑑みるとさらに計算量が増えることになりそうです。
となると、動的計画法の出番になる予感がしてきます。具体的にはそれぞれの攻撃方法について、ヒットポイントの値を一つずつ増やしながら攻撃回数と攻撃力の数を掛けた値までdpテーブルを埋める方法が考えられそうです。
…なんですが、この方法でもまだ計算量が多くなりそうです。攻撃回数まで考えると三重ループになってしまいますからね…orz
どうしましょう。どうしましょうか。お手上げです。
こんなときは私たち競プロerにとってのバイブル、通称蟻本の助けを借りましょうか。
https://www.amazon.co.jp/dp/B00CY9256C/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1
この本の中で個数制限なしナップサック問題はこんな風に解けばよいと書いてあります(私自身の読解ミスがあるかもしれません。また、説明文中のiはi種類目までの荷物の選び方、jは重さの最大値、w[i]はi番目の荷物の重さを表していると思ってください）
「dp[i+1][j](iの種類を一つ増やしたときのdpテーブルの値)の計算においてk(>=1)個選ぶ場合は、dp[i+1][j-w[i]](すでに求めてある、iの種類を一つ増やして重さからw[i]を引いたときの値)の計算においてk-1個選んだ場合と同様であるため、dp[i+1][j]の漸化式におけるk>=1の部分の計算はすでにdp[i+1][j-w[i]]の計算時に行っている。よってその値に価値を足したものと、今現在の値を見比べて適している数でdpテーブルを埋めればよい」
…はい。自分で書いててわけが分からなくなりましたorz。まだまだ勉強が足りなさそうです(:_;)
とにかく(投げた)、このような計算方法でdpテーブルを埋め最終的に求められている解を出せばよさそうです。
いくつか注意しなければならないのが、ABC153-Eの問題では「モンスターの体力を決めたときの魔力の最小値」を求めるべき(魔力の値を決めたときのモンスターのヒットポイントの最大値を求めると計算量がオーバーしてしまう)ことと、答えはdp[H]<=dp[i]<dp[H+maxA_i]の間の最小値であること(dp[H]をmaxA_iまで更新する必要がある)でしょうかね。うん、やっぱり訳が分からなくなって(ry
以上で私の雑な説明は終わりです。ぶっちゃけ他の方の簡潔かつ丁寧な説明記事をご覧になられたほうがいいですね…orz
http://drken1215.hatenablog.com/entry/2020/01/26/225000
上にけんちょんさんという競プロ界隈では知らない人はいないであろうすごいお方が書いた今回の問題の解説のリンクを貼ったので、もしよろしければこちらを参照してください。(私の書いたものよりずっと分かりやすい説明が載ってますので…)
コメント