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

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

新規登録して質問してみよう
ただいま回答率
87.20%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

解決済

競技プログラミングのエラー

appl
appl

総合スコア11

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

1回答

0リアクション

0クリップ

154閲覧

投稿2022/07/31 08:40

前提

https://atcoder.jp/contests/abc261/tasks/abc261_d
コインを振って人生ゲームのようなものをする設定の問題で、最新の動きと今までの動きが推移すると考えて動的計画法でコードを書いてみました。するとサンプルではうまくいくのにTLEやWAが出てしまいます。

実現したいこと

正しいアルゴリズムを使っているのに出てしまうTLEの原因やWAの原因を指摘していただけるとありがたいです。

発生している問題・エラーメッセージ

WA,TLE

該当のソースコード

pypy3

# -*- coding: utf-8 -*- #https://atcoder.jp/contests/abc261/tasks/abc261_d import sys input=sys.stdin.readline n,m=map(int,input().split()) #深さ優先探索がおそらく有効、、? #わかんないけど2bit探索してみる。計算がキツかったら後で考える #まてまてどう考えてもおかしいN=5000だぞ #あ動的計画法か xlist=list(map(int,input().split())) bonus=dict(zip(range(n+1),[0 for i in range(n+1)]))#それぞれの到達ボーナスを格納 for i in range(m): c,y=map(int,input().split()) bonus[c]=y dp=[[0]+[-100 for i in range(n)]]#ij成分はi(0-n)回目のコイントス後にカウンタがjである場合のお金の最大値。どんどん追加していく。最初はコイントス前 for i in range(1,n+1):#i(1-n)回後のコイントスの後に手に入る金額の最大値を各の場所について考える dp.append([-100 for i in range(n+1)]) for j in range(1,i+1):#i回目でカウンタがj(1-i)となる場合 dp[i][j]=dp[i-1][j-1]+xlist[i-1]+bonus[j] #カウンタがi回目で0となる場合 dp[i][0]=max(dp[i-1]) print(dp) print(max(dp[n]))

試したこと

ここに問題に対して試したことを記載してください。

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

以下のような質問にはリアクションをつけましょう

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

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

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

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

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

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

適切な質問に修正を依頼しましょう。

2022/07/31 14:36

こちらの質問が他のユーザーから「問題・課題が含まれていない質問」という指摘を受けました。

まだ回答がついていません

会員登録して回答してみよう

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

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

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

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。