　競技プログラミングを最近始めたPython初学者です。JOIのケーキの切り分け2の問題について質問があります。

　私のコードはサンプルでは正しい出力をしており、自分で考えた入力に対しても正しい出力が出ています。しかし、提出した結果、不正解(WA)となってしまいます。デバッグし1行ずつ確認してみたり、色々と調べてみたりしたのですが、原因が全くわかません。原因がわかる方がいらっしゃいましたら、教えていただけると幸いです。何卒よろしくお願いいたします。

問題

以下が問題のリンクです
[リンク] https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_b

コード

python
1import sys
2# 入力処理の高速化
3def input(): return sys.stdin.readline().rstrip()
4
5
6N = int(input())
7A = [int(input()) for _ in range(N)]
8
9#--------------- 考え方----------------#
10
11# 要するに残りの状態からJOIくんの最大値は決まっている → 「動的計画法」を用いる
12# dp[i][j] = 残り半開区間[i,j)から始めた時のJOIくんの取り分の最大値
13
14# 結局以下のようになる
15# JOIくんのターンの時
16# dp[i][j] = max(dp[i+1][j] + A[i],dp[i][j-1]+A[j])
17# IOIちゃんのターンから始まる時
18# dp[i][j] = dp[i+1][j] (A[i]>A[j])
19# dp[i][j] = dp[i][j-1] (A[i]<A[j])
20
21#----------------------------------------#
22
23# 円環なので配列をつなげとく
24A += A
25
26dp = [[0]*(2*N) for _ in range((N+1))]
27
28for w in range(1, N+1):  # 幅は1からNまで
29    for i in range(N):  # 区間のはじめは0からN-1まで
30        # Nと残り個数の偶奇が一致していたらJOIくんの番
31        j = i+w
32        if N % 2 == w % 2:
33            dp[i][j] = max(dp[i][j-1]+A[j-1], dp[i+1][j]+A[i])
34        else:
35            if A[i] < A[j-1]:
36                dp[i][j] = dp[i][j-1]
37            else:
38                dp[i][j] = dp[i+1][j]
39
40# 始点をすべての場合で考えてその最大値が答え
41ans = 0
42for i in range(N):
43    ans = max(ans, dp[i][i+N])
44
45print(ans)
46

行動規範の内容に同意します

回答1件

Python
1for i in range(N):
2    ans = max(ans, dp[i][i+N])
3    print(ans)

インデントはこの通りですか?
だとすればサンプルも間違った出力になると思いますが、コピペするときにでもずれたんでしょうか

Python
1for w in range(1, N+1):  # 幅は1からNまで
2    for i in range(N):  # 区間のはじめは0からN-1まで

このiを使ったループではdp[i]を更新してます。この中でdp[i + 1]の値を利用してますが i == N - 1のときdp[i + 1]はdp[N]となり、まったく更新されてない配列の値を読み取ることになります。

投稿2022/01/17 08:23

編集2022/01/17 12:11

yudedako67

総合スコア2047

OOO4423

2022/01/17 11:21 編集

すみません。インデント間違っていました。コピペの時にミスったみたいです。ご指摘ありがとうございます。正しくはprint(ans)にインデントは必要ないです。修正しておきます。このように修正すれば入力例に対する出力はあっていると思います。しかし、提出結果は不正解となります。

OOO4423

2022/01/17 13:27 編集

ご指摘ありがとうございます。 for 文付近を以下のように変更しました。 # dpは0からN-1行までしか考えない dp = [[0]*(2*N) for _ in range(N)] for w in range(1, N+1): # 幅は1からNまで for i in range(N): # 区間のはじめは0からN-1まで # Nと残り個数の偶奇が一致していたらJOIくんの番 j = i+w if N % 2 == w % 2: if i != N-1: dp[i][j] = max(dp[i][j-1]+A[j-1], dp[i+1][j]+A[i]) else: # i == N-1なら区間の始点をi+1からでなく0からと考える dp[i][j] = max(dp[i][j-1]+A[j-1], dp[0][j]+A[i]) else: if A[i] < A[j-1]: dp[i][j] = dp[i][j-1] else: if i != N-1: dp[i][j] = dp[i+1][j] else: # i == N-1なら区間の始点をi+1からでなく0からと考える dp[i][j] = dp[0][j] 見づらくて申し訳ありません。一部はACしますが、やはりまだWAです。他に原因があればご指摘していただけると幸いです。よろしくおねがいします。