はじめに

「JOI 2015 本選 2 - ケーキの切り分け 2」の python (pypy)解答。

python だと TLE しますが、pypy ならばそれなりに実行時間が短いコードです。

方針

区間 DP で解く。
区間の持ち方は [l, r) としました。

次に円環の区間の持ち方に対応します。
円環の区間の持ち方の考え方の例として、N 個に切り分けたときを考えます。
この時のピースは 、0 index で番号を振ると、ピースの番号は

0, 1, 2, ... N - 1, 0(N), 1(N + 1), 2(N + 2),...

となるので、N で割った余りを取得すれば、ピースに N 以上の数値を割り振った場合も問題なくピースを処理できる。

次に DP の初期化について考えます。
ケーキの分割数 N が奇数の時と偶数の時で場合分けして考えると、

まず N が偶数の時、最後にケーキを採るのは IOI なので 0 で初期化した DP テーブルは更新しない。

次に、N が奇数の時、最後に JOI が取得するピースは、残っている 1 ピースに決定できるので、区間[n, n + 1) つまり 番号 n のピースが残っているとき JOI は番号 n のピースを取得する。
したがって、

dp[n][n+1] = ピース n の面積

で更新する。

後はこの DP テーブルを更新すればよい。
更新順序は、残っているケーキが少ない状態から 1 つずつ増やしていき、全部のケーキを選択したら終了。

更新規則は、

1. JOI のターンでは、 dp[l][r]が最大化するようにケーキを選択する
2. IOI のターンでは、IOI がケーキの大きい方をとる。たとえば、もし区間の右のケーキが大きいならば、dp[l][r] = dp[l][r - 1] となる。

感想

区間 DP が理解できていないと感じたので解きなおしました。
この問題を解くのは 2 回目です。

2 回目なので、後で読んで理解できる解説を残すことにしました。

どうせならば、1 度目よりも読みやすく、早いコードを目指しました。

コード

https://github.com/AmanouToona/atcoder_Intermediate/blob/master/47_2.py