Educational DP Contest / DP まとめコンテストの「B - Frog 2」をPythonで

概要

  • 久しぶりに、プロコンをやろうと思って、https://atcoder.jp/contests/dpPythonでやってみた。
  • 二問目に挑戦してみたが、TLEで全然通らない。
  • 謎のnumpyを使わない縛りで挑戦していたが、これ以上は無理だと判断したので、供養目的で、ここに載せておく。

コード

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を使うことにします。