AtCoder Beginner Contest 268 E問題 Chinese Restaurant (Three-Star Version)

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

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

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

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

操作後, 人 $i$ について, 不満度を以下を満たすような非負整数 $k$ の最小値と定義する.

人 $(i-k) \pmod{N}$ または人 $(i+k) \pmod{N}$ の前に料理 $i$ がある.

$N$ 人の不満度の総和の最小値を求めよ.

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

制約

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

解法

$F_i(t)$ で $t$ 回操作した場合における人 $i$ の不満度と定義する. このとき, $N$ 回操作すると一周するので, $F_i$ は $N$ 周期関数である.

次のような関数 $f_i$ を考える. $q$ を $p$ の逆並び替えとして, $T_i:=(i-q_i) \pmod{N}$ とする. すると, $M:=\left \lfloor \dfrac{N}{2} \right \rfloor$ とすると, 次のように $F_i$ が変化する.

が偶数のとき
- $u=0,1,2, \dots, M$ に対して, $f_i(T_i+u)=u$
- $u=M+1, M+2, \dots, N$ に対して, $f_i(T_i+u)=2M-u$
が奇数のとき
- $u=0,1,2, \dots, M$ に対して, $f_i(T_i+u)=u$
- $u=M+1, M+2, \dots, N$ に対して, $f_i(T_i+u)=2M+1-u$

このとき, $f_i$ は2つの区間における $u$ に関する1次式で表されていることに着目する. つまり, $f_i(t)$ は $t$ に関する1次式でもある. 従って, $f_i$ の2階差分をとると次のようになる.

が偶数のとき
- $t=T_i+1$ のときの2階差分は $1$
- $t=T_i+M+1$ のときの2階差分は $-2$
- $t=T_i+N+1$ のときの2階差分は $1$
- 上記以外の $t$ における2階差分は $0$
が奇数のとき
- $t=T_i+1$ のときの2階差分は $1$
- $t=T_i+M+1$ のときの2階差分は $-1$
- $t=T_i+M+2$ のときの2階差分は $-1$
- $t=T_i+N+1$ のときの2階差分は $1$
- 上記以外の $t$ における2階差分は $0$

※ $N$ が小さい場合, 上で述べた2階差分の情報がある $t$ に対して複数でてくる場合がある. このような場合はそれらに書いてある2階差分の総和をとる.

このとき, 実は $\displaystyle F_i(t)=\sum_{\substack{s \in \mathbb{Z} \\ s \pmod{N}=t \pmod{N}}} f_i(s)$ である. そして, $f_i$ は連続する $N$ 個の整数以外では全て $0$ である. よって, $F_i(t)$ は $T_i \leq s \lt T_i+N, t \pmod{N}=s \pmod{N}$ となる整数 $s$ を用いて $F_i(t)=f_i(s)$ となる.

各 $f_i$ の2階差分がゼロでは無い所が高々 $4$ 点であるから, Imos法を利用することによって, $f_1(t)+\dots+f_N(t)$ を求めることができ, $F_i$ と $f_i$ の関係性を用いることにより, $F_1(t)+\dots+F_N(t)$ も求めることができる.