Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 270 E問題 Apple Baskets on Circle

AtCoder ABC270 ABC E問題 500 pts

問題

提出解答

問題の概要

$N$ 個のかごが円状に置かれている. $i=1,2, \dots, N$ に対して, かご $i$ の右隣にはかご $(i+1)$ が置かれている. なお, かご $(N+1)$ はかご $1$ とみなす.

最初, かご $i$ には $A_i$ 個のりんごがある.

高橋君は最初, かご $1$ の前にいる. ここから, 合計で $K$ 個のりんごを食べるまで以下の行動を繰り返す.

目の前にあるかごにりんごがあればそこにあるりんごを1個食べる.
りんごを食べた, 食べなかった関係なく, 右隣のかごの前に移動する.

繰り返しの行動終了後における各かごにあるりんごの個数を求めよ.

制約

$1 \leq N \leq 10^5$
$0 \leq K \leq 10^{12}$
$1 \leq A_i \leq 10^{12}$
$\displaystyle \sum_{i=1}^N A_i \leq K$

解法

非負整数 $T$ に対して, $C(T)$ を以下で定める.

$T$ 回目のかご $N$ からかご $1$ への移動が終了した瞬間における高橋君がこれまでに食べたりんごの数. ただし, $T=0$ のときは $C(T)=0$ とする.

このとき, $C(T)$ について, 制約から以下のことがわかる.

(1) $C(T)$ は広義単調増加である.
(2) 十分大きい整数 $T$ に対して, $C(T) \geq K$ である.
(3) $C(T) \lt K$ ならば, $C(0) \lt C(1) \lt \dots \lt C(T) \lt C(T+1)$ である.

ここで, $\widetilde{T}$ を $C(T) \leq K$ を満たす最大の非負整数と定めると, 高橋君は行動を完了するまでに, 完全に $\widetilde{T}$ 周することがわかる. ここから残りの行動について, 残り $(K-C(\widetilde{T}))$ 個のりんごを食べることになるが, $\widetilde{T}$ の定め方から, $N$ 回以内の行動で終了する. よって, 愚直なシミュレーションにおいてこのパートを $O(N)$ 時間で求めることができる.

よって, 次の問題を解決できれば良い.

$\widetilde{T}$ の求め方. つまり, $C(T) \leq K$ を満たす最大の非負整数 $T$ の求め方.
$C(T)$ の求め方.

まず, $C(T)$ の求め方については次の式によって $O(N)$ 時間で求めることができる.

$\displaystyle C(T)=\sum_{i=1}^N \min (A_i, T)$

$\widetilde{T}$ の求め方について, 上で述べた性質 (1) より $C(T)$ は単調増加である. よって, 二分探索によって $C( \bullet)$ を1回で $O(N)$ 時間で求められることから, $\widetilde{T}$ を $0,K$ はそれぞれ下界, 上界になることから, $O(N \log K)$ 時間で求めることができた.

以上から $O(N \log K)$ 時間で解答を求めることができた.