質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.60%

python3で[errror]list index out of rangeが解決できない

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,115

score 53

atcoder Educational DP Contest B-Frog2をpython3で解いているのですが、

Traceback (most recent call last):
  File ".\atcoder.py", line 20, in <module>
    chmin(dp[i+j], dp[i]+abs(dp[i]-h[i+j]))

IndexError: list index out of range


というエラーがでます。単純なミスだと思うのですが全くわからないまま時間が過ぎてしまったのでどなたか教えていただけると幸いです。コードは以下になります。Qiitaの解説を参考にしています。

import math
import sys
import os
f = open('input.txt', 'r')
sys.stdin = f

def chmin(a, b):
    if a > b:
        a = b
        return a

n, k = map(int, (input().split()))
h = list(input().split())
h = [int(i) for i in h]
dp = [100000]*n
dp[0] = 0
for i in range(0, n):
    for j in range(1, k+1):
        if i+j <= n:
            chmin(dp[i+j], dp[i]+abs(dp[i]-h[i+j]))
print(dp[n-1])
5 3
10 30 40 50 20
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+2

ご質問の件は、tachikomaさんが回答済なので別件についてです。

  1.   chmin()関数でdp[]の内容を更新したいのだと思いますが、この関数に渡されているa, bはdp[]そのものではなく値のコピーです。なので、a = b と書いてもdp[]の内容を変更することはできません。dp[]を直接更新するようなコードを書く必要があります。

  2.   chmin()に渡すbを計算する部分ですが、ここで必要なのは
    i番目の足場までのコスト + (i番目の足場からi+j番目の足場に移るためのコスト) なので
    dp[i] + abs(dp[i] - h[i+j]) ではなく dp[i] + abs(h[i] - h[i+j]) だと思います。

  3.   dpのリストを 100000 で初期化していますが、以下のようにK=1で足場がデコボコで正しい答えが100000を越えるケースでは正しく計算できなくなります。float('inf')とか10**10など、もっと大きな値で初期化する必要があると思います。

100000 1
1 10000 1 10000 1 10000, 1, ...

1-3を反映させたコードは以下の通りです。

def chmin(i, j):
    a, b = dp[i+j], dp[i]+abs(h[i]-h[i+j])
    if a > b:
        dp[i+j] = b


n, k = map(int, (input().split()))
h = list(input().split())
h = [int(i) for i in h]
dp = [10**10]*n
dp[0] = 0
for i in range(0, n):
    for j in range(1, k+1):
        if i+j < n:
            chmin(i, j)
print(dp[n-1])

ただし、上記のコードをPython3 (3.4.3)で提出すると制限時間オーバー(TLE)になります。
chminを別関数にせずにfor jループ内に埋め込むなど、処理時間を速くするための工夫が必要です。
(もしくは、提出言語としてPyPy3を選択するとACになるかもしれません)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/22 15:17

    丁寧にありがとうございます。なんか反映されないなと思って関数をやめたところでした。。。なぜかpythonだとINFないと思い込んでいたので助かりました!ありがとうございます。ご存知でしたら教えていただきたいのですが、質問本文「Qiitaの解説」のリンク先では、c++ですが上のようなchmin()関数で動いています。c++では引数そのものを関数で扱える(変更できる)が、pythonでは値のコピーになってしまうということでしょうか。

    キャンセル

  • 2019/03/22 18:00

    とりあえずは「pythonでは配列(リスト)の要素を関数に渡しても、呼び出した先の関数で元々の配列を変更することはできない」と覚えておけば良いと思います。←この説明は厳密には正しくないので、気になるようであればpythonの本を読んでみるか「python 参照渡し リスト」あたりのキーワードで検索してみてください。

    キャンセル

checkベストアンサー

+1

i+j <= ni+j < nじゃないとまずそうですね。Pythonのインデックスは0-baseなので、長さnのリスト等に対して有効なインデックスは[0, n-1]なんです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/22 15:10

    ありがとうございます!エラー解決しました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.60%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る