問題
長さ $N$ の数列 $a_1,\dots,a_N$ がある。2 人（先手・後手）が交互に、残っている数列の左端か右端のどちらか 1 つを取り、取った値を自分の得点に加える。全部取り終わったとき、先手の得点 − 後手の得点の値を、両者が最適に（先手は差を最大に、後手は差を最小に）行動したときについて求めよ。
入力形式
N
a_1 a_2 ... a_N制約
| # | 条件 |
|---|---|
| 1 | $1\le N\le 3000$ |
| 2 | $0\le a_i\le 10^9$ |
| 3 | 入力はすべて整数 |
入出力例
入力例1
4
3 9 1 2出力例1
7（先手が 2 を取ると、後手がどちらを取っても先手は次に 9 を取れ、先手 11・後手 4 で差は 7）
入力例2
3
4 4 4出力例2
4入力例3
1
7出力例3
7背景と出典
「両端から取るゲーム」は DP の入門でよく扱われる形で、LeetCode の "Predict the Winner" や、教科書的な「コイン列ゲーム」と同型と記憶している（本セッションでは確認していない）。
この問題で本当に確かめたいのは次の 2 点。(1) 手番ごとの得点を持つ全探索と、差だけを持つ漸化式が同じ値になること。(2) 「大きい端を取る貪欲」は反例が多く、入力例だけでは見抜けないこと（例 2 のような単純な入力では貪欲も正しい）。
ヒント（クリックで段階的に開示）
ヒント1（方向性）
区間 $[l,r]$ が残っているときの「手番の人が、残りで得られる得点 − 相手が得られる得点」を $f(l,r)$ とする。手番の人は左か右かを選ぶ。選んだ後は相手が手番になる。
ヒント2（アプローチ）
$f(l,r)=\max\bigl(a_l-f(l+1,r),\ a_r-f(l,r-1)\bigr)$。次の手番は相手なので、相手の $f$ を引く。これで先手・後手の区別が消える。$f(l,l)=a_l$。答えは $f(1,N)$。
ヒント3（誘導）
区間の長さ順に更新すれば 1 次元配列で足りる。長さ $\text{ln}$ の配列 dp[i]（区間 $[i,i+\text{ln}-1]$）を、長さ $\text{ln}-1$ の配列から作る。左端を取る場合は旧 dp[i+1]、右端を取る場合は旧 dp[i]。
---
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); a = list(map(int, data[1:1 + n]))
# dp[i] = 区間 [i, i+len-1] での (手番の人の得点 - 相手の得点) の最大値。長さ len を 1 ずつ伸ばす
dp = a[:] # len = 1
for ln in range(2, n + 1):
# 新しい dp[i] は区間 [i, i+ln-1]。左端を取る: a[i] - 旧dp[i+1]、右端を取る: a[i+ln-1] - 旧dp[i]
dp = [max(a[i] - dp[i + 1], a[i + ln - 1] - dp[i]) for i in range(n - ln + 1)]
print(dp[0])
main()
計算量: 時間 $O(N^2)$、空間 $O(N)$。実測（Python 3.14.7、M1 Mac）で $N=3000$、$a_i\le10^9$ のランダム入力が 0.61 s。
---
Step-by-Step 解説
先手の得点と後手の得点を別々に持つと状態が増える。必要なのは差だけで、手番の人から見て「自分 − 相手」を $f$ とすれば、相手の手番になった瞬間に符号が反転する（$-f$）。したがって手番の情報を状態に入れなくてよい。
$f(l,r)=\max(a_l-f(l+1,r),\ a_r-f(l,r-1))$、$f(l,l)=a_l$。$a_l\ge0$ なので空区間の $f$ は 0 でよいが、本解は長さ 1 を初期値にして空区間を参照しない。
長さ $\text{ln}$ の区間を $[i,i+\text{ln}-1]$ とすると、左端を取った後は $[i+1,i+\text{ln}-1]$、右端を取った後は $[i,i+\text{ln}-2]$。どちらも長さ $\text{ln}-1$ なので、旧配列の dp[i+1] と dp[i] に当たる。リスト内包表記で 1 度に新配列を作るので、上書きの順序は問題にならない。
位置の偶奇で見る。先手は「奇数位置の総和」と「偶数位置の総和」の大きい方の組を狙う。$N$ が偶数のとき、先手が最初に右端（偶数位置）か左端（奇数位置）を選べば、その後どちらの端が出てもそれは反対の偶奇になるので、先手は自分が選んだ偶奇の位置の石だけを取り続けられる。よって答えは 0 以上。これは検証ログで 208 件確認した（反例 0）。ただし得点差の値そのものは DP でしか出ない（この偶奇の議論は下限 0 しか言わない）。
大きい端を取ると、その次に相手が取れる端が大きくなることがある。局所的な得を、相手の次の手が上回る。$[3,9,1,2]$ では貪欲が 3 を取る（$3>2$）と、後手が 9 を取れて先手の得点が減る。
---
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| 差 $f(l,r)$ の漸化式（本解） | $O(N^2)$ | 採用 | 手番が消え、全探索と 400 件全件一致 |
| 手番ごとの得点を持つ全探索 | $O(2^N)$ | 検算用のみ | $N\le12$ でしか動かない。検算に使った |
| 「大きい端を取る」貪欲 | $O(N)$ | 不採用 | 400 件中 117 件で差が異なる |
| 先手・後手の得点を別々の 2 次元 DP | $O(N^2)$ か $O(N^2 S)$ | 不採用 | 状態が増えるだけで、差で足りる |
| $N$ が偶数なら「奇偶の総和の大きい方」を答える | $O(N)$ | 不採用 | 下限が 0 と言えるだけで、差の値そのものは違う（Step 4） |
前提が変わったら:
- $N\ge10^5$ のとき $O(N^2)$ は届かない。取る石の個数に制限がない一般形は知られた線形解が無い、と私は記憶しているが未確認。本問では扱わない
- 端から $k$ 個まで取れるなら、$f(l,r)$ の遷移が $k$ 通りになり $O(N^2k)$。本問の漸化式をそのまま増やす
- 得点が負になりうる（$a_i<0$）なら、Step 4 の偶奇の議論は成り立たない（符号が混ざる）。漸化式は同じで使える
---
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
相手の $f$ を足す（a[i] + dp[...]） | 手番が反転することを忘れる | a[i] - dp[...] |
| 大きい端を貪欲に取る | 入力例（例 2）では正しく見える | 漸化式（117/400 誤答） |
dp を同じ配列に上書きして更新する | 左端の遷移で dp[i+1] を、右端の遷移で dp[i] を使うのに順序を意識しない | 新しい配列を内包表記で作る |
$N=1$ のとき range(2, 2) が空で dp[0] が $a_1$ のまま | 初期値を忘れる | dp = a[:] で長さ 1 を初期化 |
次のステップ
発展1: 端から 1 個または 2 個取れるように拡張する（遷移が 4 通り）
- 発展2: 石を取る順序を出力する（
dpを 2 次元で保持して復元。$O(N^2)$ 空間） - 次回予告: 焦点帯外（M2・M3）の問題
検証ログ（本セッションで実行した数値）
- 全探索との照合（実測）: $N\le12$、$0\le a\le20$ の 400 件で、手番ごとの得点を持つ全探索とプログラムの出力が全件一致。$N$ が偶数の 208 件のうち、答えが負だったものは 0 件
- 誤った方法（実測）: 大きい端を貪欲に取る方法は 400 件中 117 件で答えが異なる
- 入力例（実測）: 例 1 は 7、例 2 は 4、例 3 は 7（出力例どおり）
- 実行時間（実測）: $N=3000$ で 0.61 s（答えは 24907276541）
- 扱っていない範囲: $N\ge10^5$ での解法、石を取る順序の復元、$a_i<0$ の場合、LeetCode の原典確認