B-Frog 2

B - Frog 2

本日はこちらです。前回の記事でやった問題の進化版ですね。
一応前回のnoteのリンクも貼っておきます。

前回やった問題では、カエルさんは１個先の足場と２個先の足場に飛ぶことが出来ていました。カエルさんの１ステップの可動域は２個先まででしたが、今回の問題ではそれが定まっていません。
つまり、入力ごとにカエルさんの跳躍力が高かったり低かったりするのです。あるカエルさんは１個先までしか飛べず、また別のカエルさんは１０個先まで飛べてしまうみたいな感じですね。

いつもどおりコード紹介いっちゃいます。

import sys
N, K = map(int, input().split())
ashibaList = list(map(int, input().split()))
INF = 10**20
dp = [INF for _ in range(N)]
dp[0] = 0

if N <= 1:
 print(dp[0])
 exit()

jumpLimit = 0
for i in range(1, N):
 if i < K:
   jumpLimit = i
   #print(jumpLimit)
 else:
   jumpLimit = K
 for j in range(jumpLimit):
   #print("j= " + str(j) + ", i="+str(i))
   score = abs(ashibaList[i]- ashibaList[i-j-1]) + dp[i-j-1]
   if dp[i] > score:
     dp[i] = score
print(dp[N-1])

おおまかな内容は前回と変わらないので早速細かく見ていきます。

import sys
N, K = map(int, input().split())
ashibaList = list(map(int, input().split()))
INF = 10**20
dp = [INF for _ in range(N)]
dp[0] = 0

if N <= 1:
 print(dp[0])
 exit()

見た感じ前回のコードとあまり変わりませんね。
しかし、今回の問題の入力は、前回の問題の入力よりも一つ増えており、カエルさんが何個先まで飛べるかを表す数(K)が、足場の数を表す数字(N)と同じ行にきています。なので、map関数で入力を受け取っています。便利な関数ですね。前回と同様にdpを足場の数だけ大きな数字で初期化し、dp[0]に０、足場が一つだけなら0を出力。

jumpLimit = 0
for i in range(1, N):
 if i < K:
   jumpLimit = i
   #print(jumpLimit)
 else:
   jumpLimit = K
 for j in range(jumpLimit):
   #print("j= " + str(j) + ", i="+str(i))
   score = abs(ashibaList[i]- ashibaList[i-j-1]) + dp[i-j-1]
   if dp[i] > score:
     dp[i] = score
print(dp[N-1])

前回とコード量はほとんど変わっていないのですが、ここで何気に苦労しました。

前回は２個先の足場までしか飛べないカエルしかいなかったので、ある足場から見て一つ手前の足場と二つ手前の足場でスコアを計算すればよかったため、for j in range(2)として２回ループをするだけで良かったのです。
前回は２回ループができないashibaList[1](スタートから見て２個目の足場)に関してはfor文に入る前に処理していましたね。しかし、今回はそれが出来ません。カエルさんの跳躍力が定まっていないため、何回ループをすればいいか分からないのです。
jumpLimitはその定まっていないループ数を決定するための変数です。
jumpLimitの値を決めるためにif文で分岐していますがこれに関しては具体例を使って説明したいと思います。

例えば、２段先まで飛べるカエルがいるとします。このときK=2となりますね。for i in range(1,N):で、一番最初の i には 1 が入りますね。このとき、ashibaList[i]=スタートから２番目の足場の高さとなりますね。２番目の足場なので、この足場の前には一つだけ足場があるということになります。スタート地点となる足場ですね。手前に一つだけしか足場がないということは、２番目の足場に辿り着くための道筋は、足場1から足場2の一通りしかないですね。なので、足場２のスコアの候補は一つだけしかないです。このとき、for j in range(jumpLimit): の繰り返し数は一回だけでいいので、jumpLimitが１になるようにしたいわけです。i = 1 でもあるので、jumpLimit = i　としています。
そして、次のループ i = 2 のときです。このとき、スタートから３番目の足場を見ていますね。ここでi= 2、K=2となっているため、if i < K の条件を満たせずelse文の方に分岐します。そしてjumpLimit = K つまりjumpLimit= 2となりますね。そして、このカエルに関しては可動域が２なのでこれ以降のループは全てelse文を通り、for j in range(jumpLimit):　は２回ループが限度となりますね。
なので足場３のときは、足場２→足場３、足場１→足場３のスコアをチェックしdp更新、足場４のときは、足場２→足場４、足場３→足場４のスコアをチェックという流れになります。いい感じですね。

カエルが３段先まで飛べる場合も同様に足場３まではjumpLimitの回数が１ずつ上昇していき、足場４以降になるとi = 3、K=3よりi < K の条件を満たせず、else文のjumpLimit＝Kとなり、jumpLimitの数は３に収束します。なのでループ回数も３に落ち着きます。

それ以降は大体前回と同じなので割愛します。

今回長々と例を挙げながら書いた部分の実装にメチャクソ時間がかかりました。頭のいい人は一瞬で導けそうなものなのですが、自分はどうにもダメです。早くコーディングする能力を身に着けたいのですが、考えることにこんなに時間を割いているようでは目標まではまだまだ遠そうです(泣)