JOI 2015 本選 2 – ケーキの切り分け 2

はじめに

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度目よりも読みやすく、早いコードを目指しました。

コード

atcoder_Intermediate/47_2.py at master · AmanouToona/atcoder_Intermediate
Contribute to AmanouToona/atcoder_Intermediate development by creating an account on GitHub.

コメント

タイトルとURLをコピーしました