7K12 blog

猫でも分かるアルゴリズム解説

第14回日本情報オリンピック 本選 B - ケーキの切り分け2 (Cake 2)

f:id:tkr987:20200713231126p:plain

f:id:tkr987:20200713231136p:plain

https://atcoder.jp/contests/joi2015ho/submissions/15037441

https://atcoder.jp/contests/joi2015ho/submissions/15727225

  • 循環バッファはサイズを余分に持つと実装がシンプルになる
  • 区間DPは逆順に処理しても同値というテクニックが使える場合がある
  • 初期値は if (N % 2 != 0) rep(i, 0, 2 * N) dp[i][i] = A[i];
  • 繰り返しは rep(range, 1, N) rep(l, 0, 2 * N)
  • 更新は if (count % 2 != 0) dp[l][r] = max({ dp[l][r - 1] + A[r], dp[l + 1][r] + A[l] });
  • 出力は rep(l, 0, N) ans = max(ans, dp[l][l + N - 1]);
  • 区間DPで2Nまで用意したら区間左端を2Nまで動かして更新すること
  • 出力も区間左側を2Nまで動かしてmaxを取ること
  • 追記 半開区間の実装も提出した

f:id:tkr987:20200713233409p:plain

組み合わせが非常に多いのでメモ化したい、つまり区間DPをする。既にケーキを取った区間を[l, r]とすると、[l+1, r]状態からcake[l]を取るか、[l, r-1]状態からcake[r]を取るか、2通りの遷移が考えられる。「無になるまでケーキを取る」と「無からケーキを構築する」は最終結果を考えれば同値となるので、後者の方針で実装する。dp[l][r] := 閉区間[l,r]からJOIが取ったケーキの最大値 とすると

ケーキを構築するのがJOIのとき

if (count % 2 != 0) dp[l][r] = max({ dp[l][r - 1] + A[r], dp[l + 1][r] + A[l] });

ケーキを構築するのがIOIのとき

if (A[l] < A[r]) dp[l][r] = dp[l][r - 1];

else dp[l][r] = dp[l + 1][r];

初手の構築がJOIかIOIかケーキ全体のサイズで決まる。あとは2の剰余で上記を交互に処理していけば求まる。なお、循環バッファは2倍のサイズにすると実装がシンプルになる。計算量は O(N^2)になる。