[学習記録]AtCoder EDP L-Deque[Go]

問題

太郎君と次郎君が次のゲームで勝負します。

最初に、数列 a=(a1​,a2​,…,aN​) が与えられます。 a が空になるまで、二人は次の操作を交互に行います。 先手は太郎君です。

• a の先頭要素または末尾要素を取り除く。 取り除いた要素を x とすると、操作を行った人は x 点を得る。

ゲーム終了時の太郎君の総得点を X、次郎君の総得点を Y とします。 太郎君は X−Y を最大化しようとし、次郎君は X−Y を最小化しようとします。

二人が最適に行動すると仮定したとき、X−Y を求めてください。

解法

問題を見て、DPの添字として持てそうなものは、残っている要素のインデックスがある。
残っている要素のインデックスが l , r   の時、どっちを取ったほうが得かを全ての  l ,  r  について計算すれば答えになる。
そのため、 残りが  l ,  r   のときの点差をDPに記録していく。
同じ状態を計算しないようにメモを取っておく

func run() interface{} {
	n := readInt()

	sli = readSli(n)

	dp = make([][]int, n+1)
	memo = make([][]bool, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
		memo[i] = make([]bool, n+1)
	}

	// l, rのインデックスを添字もつDPを考える
	ans := calculate(0, n-1)
	return ans
}

「太郎君は X−Y を最大化しようとし、次郎君は X−Y を最小化しようとします。」
これを言い換えると、
「どちらのプレイヤーも（自分の得点 - 相手の得点）を最大化しようとする」
となる
次郎君の場合、 X-Yの最小化 
　＝　-Y + X の最小化
　＝　- (Y - X) の最小化
　＝　(Y - X）の最大化
　＝　（自分の得点 - 相手の得点）の最大化

そうするとどちらのプレイヤーも同じ操作をすることになり、再帰的に簡潔に書けるようになる。

func calculate(l, r int) int {
    // memoにあったらそれを返す
	if memo[l][r] {
		return dp[l][r]
	}
	memo[l][r] = true

    l, rが同じ = 最後の一つ
	if l == r {
		dp[l][r] = sli[l]
		return sli[l]
	}

    // 左右それぞれを取った場合を計算
	l_score := calculate(l+1, r)
	r_score := calculate(l, r-1)

    // それぞれを比較し、大きいほうを返す
	dp[l][r] = Max(sli[l]-l_score, sli[r]-r_score)
	return dp[l][r]
}

コード（AC)

func run() interface{} {
	n := readInt()

	sli = readSli(n)

	dp = make([][]int, n+1)
	memo = make([][]bool, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
		memo[i] = make([]bool, n+1)
	}

	// l, rのインデックスを添字もつDPを考える
	ans := calculate(0, n-1)
	return ans
}

// return sum of score
func calculate(l, r int) int {
	if memo[l][r] {
		return dp[l][r]
	}
	memo[l][r] = true

	if l == r {
		dp[l][r] = sli[l]
		return sli[l]
	}

	l_score := calculate(l+1, r)
	r_score := calculate(l, r-1)
	dp[l][r] = Max(sli[l]-l_score, sli[r]-r_score)
	return dp[l][r]
}