Kazun の競プロ記録

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

AtCoder Beginner Contest 281 C問題 Circular Playlist

AtCoder ABC281 ABC C問題 300 pts

問題

提出解答

問題の概要

$N$ 曲からなるプレイリストがあり, 曲 $1,2,3, \dots, N$ と名付けられている. 曲 $i$ の長さは $A_i$ 秒である.

プレイリストを曲 $1,2, \dots, N,1,2, \dots, N,1,2, \dots$ の順に流して行った場合, 開始から $T$ 秒後はどの曲の何秒時点か?

ただし, 曲の切り替えにかかる時間は無視できるとし, 開始から $T$ 秒後に曲が切り替わることはないケースのみ与えられる.

制約

$1 \leq N \leq 10^5$
$1 \leq T \leq 10^{18}$
$1 \leq A_i \leq 10^9$
開始から $T$ 秒後には曲が切り替わらない.

解法

$A_{{\rm sum}}:=A_1+\dots+A_N$ とする. このとき, 開始から $t$ 秒後と $(t+A_{{\rm sum}})$ 秒後での曲の場所は同じである.

このことから, $T$ を $A_{{\rm sum}}$ で割った余りを $R$ としたとき, $R$ 秒後の場所を答えれば良いことがわかる.

$R$ は余りであるから, プレイリストを完全に1周する前に $R$ 秒の地点が訪れる.

$j$ を $S_j:=A_1+\dots+A_{j-1} \lt R$ を満たす最大の整数としたとき, 解答は曲 $j$ の $(R-S_j)$ 秒地点である.

なお, $j$ を求める時には $S_1, \dots, S_N$ が $A$ の累積和になっていることから, $O(N)$ 時間で求めることができる.