めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

L - Deque の解説

何の話かと言うと

atcoder.jp

この問題をネタにして、対戦ゲーム(マルコフ決定過程)のちょっとだけ応用的な考え方を説明します。

基本的な考え方については、まずは、こちらの記事をご確認ください。

enakai00.hatenablog.com

状態価値関数の一般的な定義

自分の手番の状態 s において、「これ以降に追加で取得できる得点の合計」を dp[s] として、これを状態価値関数と呼びます。

今回のゲームでは、X-Y をこのゲームの「総得点」として、太郎君は、X-Y を最大化する戦略、次郎君は X-Y を最小化する戦略を取ります。

話をわかりやすくするために、N % 2 == 0(Nは偶数)と仮定すると、最後の1要素は次郎君が取るので、A[i] を取るとすると、総得点には -A[i] が加わります。したがって、要素 A[i] だけが残った最終状態 s の状態価値関数は dp[s] = -A[i] となります。

おっと・・・ここで、状態 s の表記方法を決めておきましょう。このゲームでは、残った要素の先頭の番号 i と末尾の番号 j を用いて、ペア (i, j) によって、状態を表すことができます。この場合、状態価値関数は、2次元リストを用いて dp[i][j] と表すことができます。

とりあえず、1要素が残った状態については、次のように計算ができます。

for i in range(1, N+1):
  dp[i][i] = -A[i]

状態価値関数の遷移

そして、この1つ手前の太郎君の手番を考えると、考え得る状態は、(i, i+1) (i=1,2,...,N-1)となります。それぞれの状態について、dp[i][i+1] はどのように計算できるでしょうか・・・?

太郎君の立場では、i を取るか、i+1 を取るかを決める必要がありますが、仮に i を取ったとすると、まず、得点 A[i] が入り、その後は、先に計算した dp[i+1] が追加されます。つまり、ゲーム終了時までに(総得点X-Yに)追加される得点合計は、A[i] + dp[i+1][i+1] です。同様に、i+1 を取った場合は、A[i+1] + dp[i][i] です。太郎君は、総得点 X-Y が大きくなる方を選ぶはずなので、実際の値は、

dp[i][i+1] = max(A[i] + dp[i-1][i-1], 
                 A[i+1] + dp[i][i]) # --- (1)

と決まります。

ではでは、さらにこの1つ手前の次郎君の手番を考えると・・・・、もうだいたいのパターンが読めましたね。考え得る状態は、(i, i+2)(i=1,2,...,N-2)で、それぞれについての状態価値関数は、

dp[i][i+2] = min(-A[i] + dp[i+1][i+2],
                 -A[i+2] + dp[i][i+1]) # --- (2)

です。太郎君の手番と次郎君の手番で遷移ルールが異なるので、残った数列の幅 d を d = 1,2,..., N と変化させながら、d が偶数の場合と奇数の場合で、交互に、(1) と (2) のルールを適用していけばOKです。最後に計算される dp[1][N] が問題の答えとなります。

import sys

def main(f):
  N = int(f.readline())
  A = [None] + list(map(int, f.readline().split()))

  # N は偶数と仮定する
  dp = [[None] * (N+1) for _ in range(N+1)] # dp[i][j] : 残りが a_i ... a_j の時の状態価値関数、つまり、この後に X-Y に追加できる値
  for i in range(1, N+1): # 幅 d = 1 の場合
    dp[i][i] = -A[i]

  for d in range(2, N+1):
    for i in range(1, N-d+2):
      j = i + d - 1
      if d % 2 == 0:
        case_l = A[i] + dp[i+1][j]
        case_r = A[j] + dp[i][j-1]
        dp[i][j] = max(case_l, case_r)
      else:
        case_l = -A[i] + dp[i+1][j]
        case_r = -A[j] + dp[i][j-1]
        dp[i][j] = min(case_l, case_r)

  if N % 2 == 0:
    print(dp[1][N])
  else: # N が奇数だった場合は符号違いを答えればよい
    print(-dp[1][N])

main(sys.stdin)

これですべてのケースがパスできます。

atcoder.jp

ちょっとあっさりとした感じですが、一般に、自分のアクションによって状態が変化していくゲーム系の問題では、状態価値関数、つまり、「今の状態 s 以降に追加できる合計得点 dp[s]」を利用するのが定番のテクニックになります。

おまけ(より一般的な状態価値関数の定義)

ここでは、「自分の手番の状態 s において、これ以降に追加で取得できる得点の合計」を状態価値関数と定義しましたが、より一般には、

・自分の手番の状態 s において、これ以降に追加で取得できる得点の合計の最大値

が状態価値関数の定義となります。最後の「最大値」という言葉がミソです。この問題では「最善の手」を選択すると言う前提がありましたが、この定義であれば「最善の手」という概念を使う必要がありません。次に取る手によって、この後に取得できる合計得点はいろいろ変わりますが、その中でも最大の値を採用するという考え方です。

上記で説明した太郎君の立場での dp[i][i+1] の計算は、ちょうどこの定義に当てはまっています。二種類の手のそれぞれで計算して、それらの max を取っていますよね。(太郎君と次郎君で立場が変わりますが、次郎君からは、-dp[ ][ ] が状態価値関数と考えれば辻褄があります。)

もう一つおまけ(幅DPについて)

この問題では、ゲームが進むにつれて数列の幅が減っていくので、A[i] 〜 A[j] という特定の範囲の結果を dp[i][j] として、「範囲の幅」を増やしていく方向に遷移させていきました。このような方法を一般に「幅DP」と呼びます。(呼ばないかもしれませんが、私は個人的にそう呼んでいます。)

「一列にならんだ何かを処理する系」の問題で、うまく利用できることが時々あるので、こういう手法があるんだー、という事をちょっと覚えておくとよいでしょう。