yukicoder No.973 余興

問題

N個のシュークリームが一列に並べてあり、左からi番目のシュークリームはa_iキロカロリーである。
AさんとBさんは、Aさんから始めて交互に以下のいずれかの操作を繰り返す。

• 左側にあるシュークリームを含む、位置が連続した1個以上のシュークリームを食べる
• 右側にあるシュークリームを含む、位置が連続した1個以上のシュークリームを食べる

ただし、一度に食べられるシュークリームの合計カロリーはXキロカロリー以下にしなければならない。

最後にシュークリームを食べた人が負けとする場合、どちらも勝利を目的に最適行動をした場合、どちらが勝者になるか判定せよ。

制約

• 1 <= N <= 5000
• 1 <= X <= 10^9
• 1 <= a_i <= X

解法

単純には、
dp[i][j] := 残っているシュークリームの左端がi番、右端がj番の時、この状態で取る人が勝てるか？
というものを考えると、dp[1][N]が答えになる。
しかし、これは、遷移がO(N)かかりうるため、全体ではO(N^3)で間に合わない。

ここで、dp表の形を考える。

(画像はN=5の場合)

このdp表を埋める場合の遷移は、

「右からいくつかシュークリームを食べる」場合は、マスの左側にあるマスで負マスがあれば、そこに遷移することで、相手に負けさせることができる。
「左からいくつかシュークリームを食べる」場合は、マスの下側にあるマスで負マスがあれば、そこに遷移することで、相手に負けさせることができる。
(遷移できる範囲はXによって決まっているので、各位置での遷移範囲はO(N^2)で前計算しておく。)

ここで、対角の赤矢印方向に順番に求めていけば、あるマスを考えるとき、左側または下側のマスはすでに計算済みとなる。

ここで、左側、下側に対して勝/負を1/0で表現した累積和をもつように一緒に計算していけば、O(1)で負マスがあるかどうかを判定できる。

これで全体をO(N^2)で計算できる。
また、累積和でなくてもBITなどでO(logN)で計算してもよい。