操作回数についての考察

回転テーブルを回す操作を \(k\) 回行った場合、料理 \(p_i\) は人 \((i+k) \bmod N\) の目の前に移動してきます。ここで、\(k\) を \(N\) で割った余りが等しい場合は \((i+k) \bmod N\) の値も等しくなるため、\(k\) は \(0\) 以上 \(N-1\) の整数に限って良いです。

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

操作を \(k\) 回行った場合に喜ぶ人数を \(c_k\) とします。すると、答えは \(c_0,c_1,\ldots,c_{N-1}\) のうち最大の値です。よって、実際に操作を\(k=0,1,\ldots,N-1\) 回行った場合に対して喜ぶ人数を数えれば答えを求めることは出来ますが、各 \(k\) に対して \(N\) 人の人がそれぞれ喜ぶかどうかを調べると \(\mathrm{O}(N^2)\) となり、実行時間制限に間に合いません。

\(\mathrm {O}(N)\) への改善

料理 \(i\) が初め人 \(j\) の目の前にあるとします。この時、料理 \(i\) を人 \((i-1)\bmod N\)、人 \(i\)、人 \((i+1)\bmod N\) の目の前に移動させるのに必要な操作回数はそれぞれ \((i-1-j) \bmod N\) 回、\((i-j)\bmod N\) 回、\((i+1-j) \bmod N\) 回です。よって、人 \(i=0,1,\ldots,N-1\) に対して \(c_{(i-1-j) \bmod N}, c_{(i-j) \bmod N}, c_{(i+1-j) \bmod N}\) をそれぞれ \(1\) ずつ増やす処理を行えば \(\mathrm{O}(N)\) で \(c_0,c_1,\ldots,c_{N-1}\) を求めることが出来ます。
なお、人 \(0\)、人 \(1\)、\(\ldots\)、人 \(N-1\) の順で処理をしようとすると料理 \(i\) が初め誰の目の前にあるのかを求めるための前計算が必要になりますが、人 \(p_0\)、人 \(p_1\)、\(\ldots\)、人 \(p_{N-1}\) の順に処理をすれば問題ありません。(実装例でもそのようにしています。)

実装例

#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<int> cnt(N,0);
	
	for(int i=0;i<N;i++){
		for(int j=0;j<3;j++){
			cnt[(p[i]-1-i+j+N)%N]++;
		}
	}
	
	int ans = 0;
	for(int i=0;i<N;i++)ans = max(ans,cnt[i]);
	
	cout<<ans<<endl;
	
	return 0;
}