AtCoderに挑戦：AtCoder Beginner Contest 153

（はじめに）現在AtCoderで私の色は茶色です。現在は一つ上の緑色を目指して、レーティングが800を超えることを目標に挑戦しています。

本日は、“AtCoder Beginner Contest 153” に挑戦しました。

https://atcoder.jp/contests/abc153

先週は、散々な結果で、レーティングが下がってしまいましたので、気を取り直して、挑戦した結果は、、、

D問題まですらすら解けた！！
と思ったら、いつもより簡単だったみたいで、思ったほどレーティングはあがりませんでした。　

　さて、今回は解けそうで解けなかった E問題 について考えてみます。動的計画法(DP: Dynamic Programing)を使うんだろうとは思いましたが、どのように処理すれば良いのか分かりませんでした。

解説と他の方の解答を参考にすると、戦略としては、
1) dp[ i ] = モンスターの体力を i 減らすため消耗する魔力の最小値
の配列を作成して、
2) 上記配列 dp の指定された体力 H 以上となる部分から最小値を選ぶ
となるようです。

実際のコードは、

H, N = map(int, input().split())

AB = [list(map(int, input().split())) for i in range(N)]

maxA = max(a for a,b in AB)
#print(maxA)

dp = [0 for i in range(H+maxA)]

for i in range(1, H + maxA):
    dp[i] = min(dp[i - a] + b for a, b in AB)  # ※
    
print(min(dp[H:]))

となりますが、※の部分がエレガントすぎて、よく分かりませんでしたので、以下に考えてみます。
　
　まず、for ループは 1から指定された体力 H に 一度の攻撃で減らすことのできる最大値をAi を足した部分までまわしています。そして各値に対して、最小となる魔力を※部で計算していおり、その値は、配列ABのすべて見にいった上で決定していることが、for a, b in AB　と書かれていることからわかります。その中で、最大に分かりにくのが、dp[i – a] + b の部分です。入力例1を例にすると AB = [ [8, 3], [4, 2], [2, 1] ] となっているので、
i = 1 の場合を考えると、
　　a, b = 8, 3 のとき、 dp[1-8] + 3 = dp[-7] + 3 となります。
　　dp[-7] が何を意味しているかというと、dpは

dp = [0 for i in range(H+maxA)]

と定義していますので、dp[9+8-1] のdp[16]まであって、-7が指定されているので、最後尾から数えていくと、dp[10]を示している事になります。そんでもって、dp[10]の値はまだ何も計算していないので、初期値の 0となっています。よって dp[1-8] + 3 = dp[-7] + 3 = 0 + 3 = 3
　同様にa, b = 4, 2 のとき、 dp[1-4] + 2 = dp[-3] + 2 = dp[14] + 2 = 0 + 2 = 2となり、
　a, b = 2, 1 のとき、 dp[1-2] + 1 = dp[-1] + 1 = dp[16] + 1 = 0 + 1 = 1となります。
よってmin(3, 2, 1)　なので、dp[1] = 1 となります。確かに体力を1だけ減らす場合の最小コストは、一番コストの低い b = 1の a = 2の攻撃で良いわけです。しかしながら、dpの参照先dp[i-a] については未だに何をやっているか分かりません。おそらく i が小さく i – a が負の値をとる間は、分かりそうにありません。
　よって、細かい計算を端折りながら、進めていくと、
i = 2 の場合、dp[2 – 8], dp[2 – 4], dp[2 – 2] を参照して、dp[2] = 1
i = 3 の場合、dp[3 – 8], dp[3 – 4], dp[3 – 2] を参照して、dp[3] = 1
i = 4 の場合、dp[4 – 8], dp[4 – 4], dp[4 – 2] を参照して、dp[4] = 2
i = 5 の場合、dp[5 – 8], dp[5 – 4], dp[5 – 2] を参照して、dp[5] = 2
i = 6 の場合、dp[6 – 8], dp[6 – 4], dp[6 – 2] を参照して、dp[6] = 3
i = 7 の場合、dp[7 – 8], dp[7 – 4], dp[7 – 2] を参照して、dp[7] = 3
i = 8 の場合、dp[8 – 8], dp[8 – 4], dp[8 – 2] を参照して、dp[8] = 3
ようやくすべてのdp[ i – a ] が、次の i = 9 で、すでに計算した部分を参照しそうですので、詳しくみてみます、

i = 9 の場合、
dp[9 – 8] + 3 = dp[1] + 3 = 1 + 3 = 4、
dp[9 – 4] + 2 = dp[5] + 2 = 2 + 2 = 4、
dp[9 – 2] + 1 = dp[7] + 1 = 3 + 1 = 4、よってdp[9] = 4。。

ここまで書いてやっと分かりました。。
dp[ i ] の i は、i = i – A + A　であると！
そんでもって、i – A が負の値になる場合でも、dp の範囲をrange(H+maxA) でとっているので、いくらなんでも、ぐるっとまわって、すでに計算された値までいかずに、初期値の0を参照しにいくと！！

　考えながら書いてみたので、かなり雑多になっているかと思います。後日改めて、分かりやすいように整理してみたいと思います。。。