A - Frog 1

A - Frog 1


AtCoder is a programming contest site for anyone from beginne


atcoder.jp

本日は動的計画法というものを学ぶべく、色々な記事を読んでおりましたが、全然理解出来なくて絶望しておりました。しかし、そんな僕にもようやくA-Frog1という、多分おそらく動的計画法のチュートリアル的な問題をACすることが出来ました。

動的計画法に関しては、問題を答えを導くために一つ一つ配列などの情報を更新していって、更新していった配列から答えを取り出すものという、漠然とした認識しか僕にはありませんが、もっと上手に説明できるようになったら、そのときはこちらの方に記録させていただきます。

とりあえず恒例のコード紹介

import sys

N = int(input())
ashibaList = list(map(int, input().split()))
if N <= 1:
 print(0)
 exit()

INF = 10**20
dp = [INF for _ in range(N)]
dp[0] = 0
dp[1] = abs(ashibaList[1] - ashibaList[0])
for i in range(2, N):
 for j in range(1,3):
   score = abs(ashibaList[i] - ashibaList[i-j]) + dp[i-j]
   if dp[i] > score:
     dp[i] = score
     
print(dp[N-1])

まず、今回の問題はカエルが主役となっています。カエルさんが複数の足場をジャンプしていって、最後の足場（ゴール）に辿り着くというかわいらしい問題です。
それぞれの足場には、高さの情報が設けられています。前にいた足場とジャンプした先の足場の高さの差がスコアとなり、ジャンプするたびにそのスコアが加算されていく感じですね。カエルは一つ先の足場または二つ先の足場にジャンプすることができ、ゴールにたどり着いた時に最小となるスコアを出力する問題です。

今回のコードの流れとしては、以下のようになります。

1. 足場の数と複数の足場の高さをリストに格納
2.足場の数が１のときはスタート地点がゴール地点なのでスコア加算は行われないため、0を出力
3. dpという名の配列に足場の数だけ10**20をいれて初期化
4. dp[1]はループ処理で回すのがめんどそうなので先に処理
5.足場３番目からは、１つ前の足場との差分を計算し、1つ前のスコアを加算した値を既に格納されている値と比較し、計算した値の方が小さければdp配列を更新
6.二つ前の足場も5と同様にする
7. 5と6を足場の数-2だけ繰り返す
8. dpの最後のインデックスに格納された値を出力する

といった感じです。dpという変数名に関してですが、動的計画法の英語訳「dynamic programming」の略なんじゃないかなと勝手に解釈しています。動的計画法では、適宜配列の値を更新していって答えを導いていくので、その配列の変数名としてdpがよくつかわれている印象です。

それでは細かく見ていきます。

import sys

N = int(input())
ashibaList = list(map(int, input().split()))
if N <= 1:
 print(0)
 exit()

最初にsysモジュールをインポートしています。これはプログラムを途中で終了するためのexit()関数を使いたいからです。
その次に、N変数に足場の数、ashibaListに複数の足場の高さ情報が格納されます。
ashibaList = [10, 30, 20, 40]みたいな感じです。それぞれの数字が足場の高さになります。
その次に足場の数が一つだけのときは、if文を用いて"0"と出力した後exit()でプログラムを終了しています。足場の数が一つということは、ashibaList= [20]みたいな感じで、スタート地点の足場がゴールでもあるため、ゴールの足場の高さとスタートの足場の高さの差は必ず０となるためです。

INF = 10**20
dp = [INF for _ in range(N)]
dp[0] = 0
dp[1] = abs(ashibaList[1] - ashibaList[0])
for i in range(2, N):
 for j in range(1,3):
   score = abs(ashibaList[i] - ashibaList[i-j]) + dp[i-j]
   if dp[i] > score:
     dp[i] = score
     
print(dp[N-1])

いよいよここからが動的計画法となります。うまく出来ているか分かりませんがねw

今回の問題は、今いる足場と前いた足場の高さの差をスコアとし、そのスコアをより小さくするような感じでゴールにたどり着きたいです。なので、値を更新するときは、既にdpに格納されている暫定のスコアと新たに計算した値を比較して、計算した値の方が小さければdpをその値で更新したいです。
なので、最初は限りなく大きい数を足場の数だけdpに入れて初期化しています。INFの値は入力例には出てこないぐらいの大きい値だったら多分なんでもいいです。

更新作業の後はスタート地点となる足場１のスコアを格納するため、dp[0]に0を入れています。この0という値は足場１と足場１の高さの差です。もちろん0になりますね。

次にdp[1]、つまり足場２のスコアが格納された場所に、足場２と足場１の高さの差の絶対値を入れています。

その次のfor文では足場３以降のスコアを計算しています。for文が二つ連なっていて分かりづらいですね。
例えば、足場３に注目すると、足場３とその手前の足場２の差の絶対値を足場２のスコアに加算して、足場３の仮のスコアとしています。このスコアがdp[2]に格納している足場３のスコアと比較して小さくなる場合は、このスコアを新たな足場３のスコアとしてdp[2]に格納します。この場合はdp[2]にはINFが入っており間違いなく計算したスコアの方が小さくなるので、dp[2]は更新されます。
また一段飛ばしで足場１からも足場３に飛んでくることが出来るため、先ほどと同様に、足場３と足場１の差の絶対値に足場１のスコアを加算して仮のスコアとします。このスコアがdp[2]のスコアよりも小さければ更新します。
dp[2]には先ほど入れた足場２から足場３へ来た時のスコアが格納されているため、実質、足場２→足場３のスコアと足場１→足場３のスコアの比較となりますね。

それらの作業を一番最後の足場まで計算することで、dpの最後の要素には、スタートからゴールまでの最少スコアが入っているという感じです。

そして、最後のprint文でdp[N-1]の値を出力して終わりです。

今回は一応ACをとれたのですが、僕の動的計画法の認識はまだまだ甘く正直コードが上手く書けているかも分からないので、詳しい人がいましたら僕のコードの欠点や改善点等コメントしていただけると嬉しいです。

以上、最後に知識を乞食して締めとします。