JOI難易度６ ケーキの切り分け２

問題原文

atcoder.jp

問題要旨

分された丸いケーキがある。時計回りに 番目のピースの大きさは である。
以下の操作を繰り返すことで、JOIくんとIOIちゃんでケーキを分け合う。

1. 最初に、JOIくんが好きな位置のピースを１つ取る。
2. IOIちゃんが両端のピースのうち少なくとも一方がすでに取られているようなものの中で、最も大きいピースを取る
3. JOIくんが両端のピースのうち少なくとも一方がすでに取られているようなものの中で、好きにピースを取る
4. 以後ピースがなくなるまで、2, 3 を繰り返す

JOIくんが最適にピースを取った時、取ったピースの大きさの総和はいくつになるか？
なお、各ピースの大きさはすべて異なる。

• 

解法

JOIくんがあるピースを取り、区間 [i, j] が残ったとする。そしてここから最適にピースを取っていった場合の最大値は、
区間 [i, j] が残っている時の、JOIくんが得られる取り分の最大値
という区間dpで求めることができる。

遷移は、

1. JOIくんのターンの場合
   区間の始まりから取るか、区間の終わりから取るかの最大値。
   再帰的に求める。

2. IOIちゃんのターンの場合
   A[i] と A[j] を比較して、大きい方をIOIちゃんが取ったものとしてJOIくんにターンを返す。

ようにする。
この dpを最初に取るピース１〜 Nについて求めるが、当然それぞれのループで埋めたテーブルは再利用できるので、３乗にはならずに間に合う。

実装

更新順で頭ぶっ壊れたのでメモ化再帰で。
今どちらのターンか考えても頭壊れたので関数に持たせて引き継ぐようにした。
我ながら汚い。本当に汚い。
Aを２倍にするとただの区間になるから書きやすいらしい。ただし定数倍は重くなる。

import sys
sys.setrecursionlimit(10 ** 9)
my_input = sys.stdin.readline

N = int(input())
A = [int(my_input()) for _ in range(N)]
# dp[i][j] := 区間[i, j]が残っている時のJOIくんの取り分の最大値（右回り）
dp = [[0] * N for _ in range(N)]


def dfs(i, j, picked):
    if dp[i][j] > 0:
        return dp[i][j]

    # 終了条件: 最後の１かけら（JOIくんが取るとは限らない）
    if i == j:
        if picked % 2 == 0:
            dp[i][j] = A[i]
            return A[i]
        else:
            return 0

    di, dj = (i + 1) % N, j - 1 if j - 1 >= 0 else N - 1
    if picked % 2 == 0:  # JOIくんの番
        ret = max(dfs(di, j, picked + 1) + A[i], dfs(i, dj, picked + 1) + A[j])
    else:  # IOIちゃんの番
        if A[i] > A[j]:
            ret = dfs(di, j, picked + 1)
        else:
            ret = dfs(i, dj, picked + 1)

    dp[i][j] = ret
    return ret


ans = 0
for x in range(N):
    s, e = (x + 1) % N, x - 1 if x - 1 >= 0 else N - 1
    r = dfs(s, e, 1) + A[x]
    ans = max(ans, r)
print(ans)

感想

なんで僕の区間dpはこれほど汚いのか。。。
いろんな問題解いてきて復習します。。。