Atcoder DP - L : Deque
問題 : https://atcoder.jp/contests/dp/tasks/dp_l
結論
dp[left][right] := 区間Points[left, right)を渡された先手のスコア
def getInt():
return int(input())
def getIntsArray():
return [int(x) for x in input().split()]
N = getInt()
Points = getIntsArray()
INF = float("inf")
dp = [[0 if left >= right else -INF for right in range(N + 1)] for left in range(N + 1)]
for length in range(1, N + 1):
# 0 <= left <= N - lenght
for left in range(N - length + 1):
right = left + length
if left + 1 <= N - 1:
dp[left][right] = max(dp[left][right], Points[left] - dp[left + 1][right])
if right - 1 <= N:
dp[left][right] = max(
dp[left][right], Points[right - 1] - dp[left][right - 1]
)
print(dp[0][N])
思考順序
愚直な実装
愚直に実装してみましょう。タイトルにあるようにdeque構造から取り出して評価していきます。
def solve(n, points):
dq = deque(points)
scores = []
while dq:
left = dq[0]
right = dq[-1]
if left < right:
scores.append(dq.pop())
else:
scores.append(dq.popleft())
# このあとにscoresを先手後手に分ける
ここで手が止まりました。
left = rightであるときの処理が再帰的になるからです。
left = rightのとき、どちらをとってもよいということにはなりません。
ex) (1,2,3,1)というポイントの並びのとき
最初のプレイヤーは相手に3を取らせないために左の1を取るべきです。
つまり、内側の要素の大小比較をしなくてはいけません。計算量もさることながら、処理が面倒なのでやめましょう。
並びで先手のスコアは決まってる
ここで注目するのは、並びで先手のスコアが一意に決定することです。
例えば(1,2,3)であれば2ですし、(2,3,1)ならば0です。
これがわかっていると、(1,2,3,1)で最初にどちらを取るかは簡単です。後手のスコアが悪くなる(2,3,1)になるようにとればよいのです。
dp[left][right] := ポイント配列のうち、区間[left, right)を渡された先手のスコア
と定義して動的計画法を考えます。
漸化式
遷移は簡単です。
左から取るか、右から取るかです。
dp配列は先手のスコアを示しているので、取ったポイントから、残りの配列で後手が取るスコアを引いてやればよいとなります。
dp[left][right] = max(points[left] - dp[left+1][right], points[right-1] - dp[left][right-1])
ボトムアップで処理をする
では、どこからdpテーブルを埋めていくべきでしょうか？
注目するのは区間の長さです。区間が短いところからスコアの計算ができます。
あとは左端のleftをループさせます。rightはleftとlengthで表現できます。
for length in range(1, N + 1):
# 0 <= left <= N - lenght
for left in range(N - length + 1):
right = left + length
leftの範囲
leftにかかる制限は
- 0 ≤ left ≤ N-1
- 1 ≤ right ≤ N
です。これを整理すると0 ≤ left ≤ N - lengthとなります。
初期化
ここが一番苦労しました。
このテーブルではleft ≥ rightとなる区間は空の区間になってしまうため、スコアを0として扱えばよいですね。
結局求めたいのは以下のようなテーブルです。
[0, 10, 70, 20, 10]
[0, 0, 80, 10, 20]
[0, 0, 0, 90, 60]
[0, 0, 0, 0, 30]
[0, 0, 0, 0, 0]
対角線を挟んで上側だけ-infで初期化します
dp = [[0 if left >= right else -INF for right in range(N + 1)] for left in range(N + 1)]