\(\mathrm{O}(N^2)\) 解法

C問題と同様に操作回数を \(0\) 回以上 \(N-1\) 回以下とします。また、操作を \(k\) 回行った場合の不満度の総和を \(v_k\) とします。ここで、答えは \(v_0,v_1,\ldots,v_{N-1}\) のうち最小の値です。 よって、操作回数が \(0,1,\ldots,N-1\) の場合それぞれについて \(N\) 人の不満度の総和を計算する形で \(v_0,v_1,\ldots,v_{N-1}\) を求めれば、\(\mathrm{O}(N^2)\) で答えが求められます。これを高速化します。

いもす法の利用

いもす法を応用することですべての操作回数について不満度の総和を高速に求めることが出来ます。
料理 \(i\) を人 \(i\) の目の前に移動させるのに必要な操作回数を \(t\) 回とします。すると、不満度の様子は以下のように記述できます。

• 操作回数が \(t\) の場合の人 \(i\) の不満度は \(0\)、\((t+1) \bmod N\) の場合は \(1\)、\((t+2) \bmod N\) の場合は \(2\)、\(\ldots\)、\((t+\lfloor \frac{N}{2} \rfloor) \bmod N\) の場合は \(\lfloor \frac{N}{2} \rfloor\) となる
• 操作回数が \((t-1) \bmod N\) の場合の人 \(i\) の不満度は \(1\)、\((t-2) \bmod N\) の場合は \(2\)、\(\ldots\)、\((t-\lceil \frac{N}{2} \rceil) \bmod N\) の場合は \(\lceil \frac{N}{2} \rceil\) となる

このことを考えると、操作回数を \(x\) とした時の人 \(i\) の不満度は、前者では \(t\) から \(x\) の間で、後者では \(x\) から \(t\) の間で \(N-1\) と \(0\) の間をまたがない限り\(x\) の一次式として表せます。具体的には、前者では \(x-t\)、後者では \(-x+t\) となります。
一旦 \(N-1\) と \(0\) の間をまたぐ可能性を棚上げして高速化の方法を示します。一次式の和は次数ごとに係数を独立に足し合わせることで計算できるため、\(1\) 次の項と \(0\) 次の項でそれぞれいもす法を行えば \(x=0,1,\ldots,N-1\) に対して操作を \(x\) 回行った場合の不満度の総和を表す一次式を \(\mathrm{O}(N)\) で求められ、それに \(x\) の値を代入することで不満度の総和を求めることが出来ます。

\(N-1\) と \(0\) の間をまたぐ場合の対処

棚上げしていた\(N-1\) と \(0\) の間をまたぐ場合の対処法を \(2\) つ示します。

対処法1 : \(3\) つの一次式を考える

人 \(i\) の不満度の記述のうち前者において \(N-1\) と \(0\) の間をまたぐとします。この時、記述は以下のように書き直せます。

• 操作回数が \(t\) の場合の人 \(i\) の不満度は \(0\)、\((t+1) \bmod N\) の場合は \(1\)、\((t+2) \bmod N\) の場合は \(2\)、\(\ldots\)、\(N-1\) の場合は \(N-1-t \) となる
• 操作回数が \(0\) の場合の人 \(i\) の不満度は \(N-t\)、\(1\) の場合は \(N+1-t\)、\(\ldots\)、\((t+\lfloor \frac{N}{2} \rfloor) \bmod N\) の場合は\(N + ((t+\lfloor \frac{N}{2} \rfloor) \bmod N) -t\) となる
• 操作回数が \((t-1) \bmod N\) の場合の人 \(i\) の不満度は \(1\)、\((t-2) \bmod N\) の場合は \(2\)、\(\ldots\)、\((t-\lceil \frac{N}{2} \rceil) \bmod N\) の場合は \(\lceil \frac{N}{2} \rceil\) となる

\(2\) 番目の記述に対して一次式 \(x+N-t\) を考えることで、先程と同様にいもす法を行うことが出来ます。
また、\(N-1\) と \(0\) をまたぐのが後者の場合も同様に考えれられます。

対処法2 : \(x\) の範囲を \(0\) 以上 \(2N-1\) 以下に拡張する

先ほどまでは \(x\) が操作回数にそのまま対応するものとしていたため演算の際には \(\bmod\ N\) を付し、 \(0\) 以上 \(N-1\) 以下の値を取るものとしてきました。しかし、その結果 \(N-1 \) から \(1\) 増やした結果が \(0\) となり、不都合が生じています。これを解決するためには、\(N-1\) から \(1\) 増やした結果が \(N\) となるようにすればよいです。
具体的には、\(x\) の範囲を \(0\) 以上 \(2N-1\) 以下に拡張した状態でいもす法による計算を行い、操作回数が \(0\) の場合は \(x=0\) と \(x=N\) に対する計算結果の和、\(1\) の場合は \(x=1\) と \(x=N+1\) に対する計算結果の和、\(\ldots\)、\(N-1\) の場合は \(x=N-1\) と \(x=2N-1\) に対する計算結果の和とすれば良いです。これによって \(x\) が \(\bmod \ N\) で等しい場合を同一視できるため、立式のタイミングで \(x\) の値を \(\bmod\ N\) とすることをやめ、一次式をそのまま使うことが出来ます。
なお、実装例ではこちらの対処法を採用しています。

実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N;
	cin>>N;
	
	vector<int> p(N);
	
	for(int i=0;i<N;i++)cin>>p[i];
	
	vector<long long> iv(N*2),ix(N*2);
	
	for(int i=0;i<N;i++){
		int j = (p[i]-i+N)%N;
		iv[j] -= j;
		iv[j+N/2+1] += j;
		ix[j] += 1;
		ix[j+N/2+1] -= 1;
		iv[N+j-(N-1)/2] += N+j;
		iv[N+j] -= N+j;
		ix[N+j-(N-1)/2] -= 1;
		ix[N+j] += 1;
	}
	
	for(int i=0;i<N*2-1;i++){
		iv[i+1] += iv[i];
		ix[i+1] += ix[i];
	}
	
	long long ans = 1000000000000000000;
	for(int i=0;i<N;i++){
		ans = min(ans,iv[i] + ix[i]*i + iv[i+N] + ix[i+N]*(i+N));
	}
	
	cout<<ans<<endl;
	
	return 0;
}