Official

C - Different Neighbor Editorial by cn449


各点 \(i\) について、点 \(i\) を含み区間内の点がすべて点 \(i\) と同じ色であるような最大の区間を求めればよいです。

すなわち、点 \(L_i, L_i + 1, \ldots, i, \ldots, R_i - 1, R_i\) は点 \(i\) と 同じ色であり、\(L_i \neq 1\) ならば点 \(L_i - 1\) と点 \(i\) の色は異なり、\(R_i \neq N\) ならば点 \(R_i + 1\) と点 \(i\) の色は異なるような \(L_i, R_i\) を計算できれば答えを求めることができます。

各 \(i\) について愚直に \(L_i, R_i\) を計算すると最悪 \(\Theta(N^2)\) 時間となってしまいますが、\(i \geq 2\) のとき \(C_i = C_{i - 1}\) ならば \(L_i = L_{i -1}\)、\(C_i \neq C_{i - 1}\) ならば \(L_i = i\) であることを利用すれば \(O(N)\) 時間で \(L_i\) たちを列挙することができます。\(R_i\) についても同様です。

実装例

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> c(n);
	rep(i, n) cin >> c[i];
	vector<int> L(n, -1), R(n, n);
	rep(i, n) {
		if (i > 0 && c[i] == c[i - 1]) L[i] = L[i - 1];
		else L[i] = i;
	}
	for (int i = n - 1; i >= 0; i--) {
		if (i < n - 1 && c[i] == c[i + 1]) R[i] = R[i + 1];
		else R[i] = i;
	}
	rep(i, n) {
		int d = n;
		if (L[i] != 0) d = min(d, i - L[i] + 1);
		if (R[i] != n - 1) d = min(d, R[i] + 1 - i);
		cout << d << " \n"[i == n - 1];
	}
}