Official
C - Different Neighbor Editorial
by
C - Different Neighbor Editorial
by
cn449
Editorial for printing
各点 \(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];
}
}
posted:
last update: