競プロ初中級者100問

JOI2015本選B ケーキの切り分け２

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_b

この問題は動的計画法を用いて解くことができます。

方針

基本的に公式の解説通りです。区間DPと呼ばれる実装を行います。データが円環担っているため、データを2回並べることで一次元のデータとして扱います。

コード

maspyさんのコードをコメントを入れながら読ませていただきました。

最後のターンから考えていきます。最終的にJOIくんが得るスコアをdpとして格納していきます。dpはターン別に用意せずに使い回すのでサイズはNとなります。

最後から数えてnターン目にはn個のピースが残っています。そのパターンはiを変数としてA[i:i+n]で表せます。これに対させて、最終的にJOIくんが得るスコアをdp[i]に格納していきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int64)

# 順に二回並べることで円環を区間につぶしたまま作業できる
A = np.concatenate([A,A])

# dp: 残りのピースがn個（A[i:i+n]）だったとして、最終的にJOI君が得るスコア
# 小さいnから逐次的に更新していく（一次元配列を使い回す）
dp = np.zeros(N,np.int64)
for n in range(1,N+1):
    dp = np.append(dp,dp[0]) # dpも円環
    player = (N - n) & 1 # 最後のターンから考えるので、Nが偶数なら最後はIOI、奇数なら最後はJOI
    if player == 0:
        # JOI君
        left = dp[1:N+1] + A[:N]
        right = dp[:N] + A[n-1:N+n-1]
        dp = np.maximum(left,right)
    else:
        # IOIちゃん
        dp = np.where(A[:N] > A[n-1:N+n-1], dp[1:N+1], dp[:N])

answer = dp.max()
print(answer)

記事情報

  • 投稿日：2020年5月16日
  • 最終更新日：2020年5月16日