Kazun の競プロ記録

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

AtCoder Beginner Contest 268 C問題 Chinese Restaurant

AtCoder ABC268 ABC C問題 300 pts

問題

提出解答

問題の概要

円卓の周りを人 $0$ , 人 $1$ , $\cdots$ , 人 $(N-1)$ がこの順に反時計回りに等間隔に座っている. 各人 $i$ の前には料理 $p_i$ がある.

次の操作を $0$ 回以上できる.

円卓を $1/N$ だけ反時計回りに回す. これによって, 人 $i$ の前にあった料理は人 $(i+1) \pmod{N}$ に移動する.

人 $i$ について, 料理 $i$ が人 $(i-1) \pmod{N}, i, (i+1) \pmod{N}$ のいずれの前にあれば喜ぶ.

喜ぶ人数の最大値を求めよ.

制約

$3 \leq N \leq 2 \times 10^5$
$(p_0, p_1 \dots, p_{N-1})$ は $(0,1, \dots, N-1)$ の並び替え.

解法

$N$ 回操作すると一周するので, 操作回数は $0$ 以上 $N$ 未満としてよい.

人 $i$ の前に料理 $i$ がくるようにするための操作回数を $k_i$ とする. このとき, 人 $i$ が喜ぶための操作回数は $(k_i-1) \pmod{N}, k_i, (k_i+1) \pmod{N}$ の3個である. なお, $q=(q_0, \dots, q_{N-1}) を [tex: p$ の逆順列, つまり $q_{p_i}}=i$ を満たすような順列とすると, $k_i=(i-q_i) \pmod{N}$ である.

よって,各操作回数で何人が喜ぶかを記録しておくことにより, 各人につき3個の記録で済むので, 全体で $O(N)$ 時間で計算できる.