概要
コード
def test3():
import sys
N, K = list(map(int, sys.stdin.readline().split()))
h = list(map(int, sys.stdin.readline().split()))
from itertools import tee
its = list(tee(range(1, K+1), N))
INF = 10**9
dp = [INF] * N
dp[0] = 0
myabs = abs
for i, hi in enumerate(h[1:], 1):
value = INF
for k in its[i]:
key = i - k
dpval = dp[key]
if dpval >= INF:
break
tmpv = myabs(hi - h[key]) + dpval
if tmpv < value:
value = tmpv
if value != INF:
dp[i] = value
print(dp[N-1])
test3()
- 頑張ったポイントは以下
- teeで予めループ用のiteratorを作っておく
- sys.stdin.readline()の方が、input()より速いらしい
- INFはギリギリの値(10**8だと通らない)
- 関数はローカル変数に紐付けしておく(myabs)
- minとか使わないで、if文
- Nでループしないで、h配列でループ
- 可能な限り、同じ計算を2回以上しないようにした
- 配列へんアクセスを最低限にした(set/getともに)
- ちなみにこれだけ頑張ると、1_03は何回かに1回は通る様になった。1_11はムリぽ。
感想
- 此のコードの改変に1日費やしたから、他の問題が結局やれなかった…
- pythonで挑戦する場合は、numpy使わないとどうにもならないみたい。
- 正直な所、1問目からわからず、地力の低さを改めて感じた。
- 次問からは、諦めてnumpyを使うことにします。