概要

この問題は、2人のプレイヤーが互いに最適な行動をとるゲームの最終的なスコアを求める問題です。 カードが常に「連続する部分的な区間」として残る性質を利用し、区間DP（動的計画法）を用いて解くことができます。

考察

ゲームの性質とアプローチ

2人のプレイヤーが自身の目的に対して最適に行動するゲーム（二人零和有限確定完全情報ゲーム）では、「最終状態（ゲーム終了時）から逆算して、お互いが最善を尽くした場合にどうなるか」を考える後ろ向き推論（ミニマックス法）が有効です。

また、カードを取り除く操作は常に「左端」または「右端」からしか行われません。そのため、ゲームのいかなる途中経過においても、残っているカードは必ず元の配列の連続する部分区間になります。

したがって、ゲームの状態を「左から \(i\) 番目から \(j\) 番目までのカードが残っている状態」として定義し、この状態からゲーム終了までに得られるスコアを管理する区間DPを考えます。

手番の判定

ゲームの残りカードの枚数を \(len\) とします。 ゲーム開始時のカードの総数は \(N\) なので、これまでに取り除かれたカードの枚数は \(N - len\) 枚です。 先手（高橋君）から交互にカードを1枚ずつ取り除くため、これまでに取り除かれた枚数によって、現在の手番がどちらかを判定できます。

• \((N - len) \pmod 2 == 0\) のとき：高橋君の手番
  • 高橋君はスコアを最大化したいので、遷移先のうち値が大きくなる方を選択します (\(\max\))。
• \((N - len) \pmod 2 \neq 0\) のとき：青木君の手番
  • 青木君はスコアを最小化したいので、遷移先のうち値が小さくなる方を選択します (\(\min\))。

メモリの最適化（1次元DPへの削減）

愚直に2次元配列 dp[l][r]（区間 \([l, r]\) が残っているときのスコア）を保持すると、空間計算量が \(O(N^2)\) となります。\(N = 3000\) のとき、メモリ制限に引っかかる可能性があります。

しかし、長さ \(len\) の状態を計算するためには、長さ \(len - 1\) の状態のみが分かれば十分です。そのため、区間の長さが短い順（\(1\) から \(N\) まで）に配列を更新していくことで、保持するデータを1次元配列 dp のみ（空間計算量 \(O(N)\)）に削減できます。

---

アルゴリズム

1. 初期化:
   • length = 1 のとき、残っているカードは1枚だけです。このときのスコアはカードに書かれた数値そのものなので、DP配列を dp = A と初期化します。
2. 遷移:
   • length を \(2\) から \(N\) まで \(1\) ずつ増やしながら、DP配列を更新していきます。
   • 長さ length の区間 \([i, i + \text{length} - 1]\) から遷移できる状態は、以下の2つです。
     • 左端を取り除いた場合：長さ length - 1 の区間 \([i + 1, i + \text{length} - 1]\) に移行する。
     • 右端を取り除いた場合：長さ length - 1 の区間 \([i, i + \text{length} - 2]\) に移行する。
   • 現在の手番に応じて、以下のように次の状態を決定します。
     • 高橋君の手番：\(\max(\text{左端を除いた結果}, \text{右端を除いた結果})\)
     • 青木君の手番：\(\min(\text{左端を除いた結果}, \text{右端を除いた結果})\)
3. 答えの出力:
   • length = N まで更新が終わると、dp には長さ \(N\) の区間（すなわちカードがすべて残っている初期状態）のスコアが格納されます。このときの dp[0] が求める答えです。

---

計算量

• 時間計算量: \(O(N^2)\)
  • 外側のループ（区間の長さ \(len\)）が \(N\) 回、内側のループ（各区間の開始位置 \(i\)）が最大 \(N\) 回回るため、全体の計算量は \(O(N^2)\) となります。\(N = 3000\) のとき、ループ内の処理回数は約 \(4.5 \times 10^6\) 回となり、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • サイズ \(N\) の1次元配列を1つ保持するだけなので、メモリ使用量は極めて小さく抑えられます。

---

実装のポイント

• zip 関数を用いたスマートな遷移:

  • dp の各要素は、長さ length - 1 の区間の結果を表しています。
  • zip(dp, dp[1:]) とすることで、隣り合う2つの区間（「右端を取り除いた結果」と「左端を取り除いた結果」）のペアを簡単に作成し、次の長さ length の結果をまとめて計算できます。

• Pythonにおける高速化:

  • Pythonでは、組み込みの max(x, y) や min(x, y) 関数をループ内で大量に呼び出すと関数呼び出しのオーバーヘッドで遅くなります。

  • コード内では、x if x > y else y のように三項演算子を用いることで、実行速度を高速化しています。

    ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    A = [int(x) for x in data[1:]]
    
    dp = A
    for length in range(2, N + 1):
        if (N - length) % 2 == 0:
            dp = [x if x > y else y for x, y in zip(dp, dp[1:])]
        else:
            dp = [x if x < y else y for x, y in zip(dp, dp[1:])]
            
    print(dp[0])

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。