BOJ 28355 - 무한 수열
Solution 1
내가 푼 방법인데, i=kn+1∑(k+1)nA(i−1) % n+1−n⋅kn−2n(n+1) 라는 n 길이의 싸이클이 언제 음수가 될 것인가? 를 이분탐색으로 찾아 몇가지 케이스를 검사해서 통과할 수 있다.
대략 어떤 주기의 suffix중 Max와 몇개의 싸이클을 건너뛰고(0개일 수도 있다.) 그 다음 싸이클에서 prefix 중 Max를 더해서 최댓값을 찾았다.
void solve() {
int n;
cin >> n;
vi a(n);
fv(a);
int cycle_minus = n * (n + 1) / 2;
int sum = acc(a);
auto cycle_sum = [&](int i) {
int ret = sum - cycle_minus;
ret -= n * (n * i);
return ret;
};
auto cycle_range_sum = [&](int l, int r) -> int {
if (l > r) return 0ll;
int len = r - l + 1;
int ret = len * sum;
r = n * (r + 1);
l = n * l + 1;
// 1 2 3 4 5 6
ret -= (r - l + 1) * (r + l) / 2;
return ret;
};
vi b = a;
for (int i = 0; i < n; i++) b[i] -= i + 1;
int mn = 0, ans = 0;
for (int i = 0, s = 0; i < n; i++) {
s += b[i];
maxa(ans, s - mn);
mina(mn, s);
}
int prefix_mx = 0;
for (int i = n - 1, s = 0; i >= 0; i--) {
s += b[i];
maxa(prefix_mx, s);
}
int mx_positive_cycle = -1;
{
int l = 0, r = 1e15, ret = -1;
while (l <= r) {
int m = (l + r) >> 1;
if (cycle_sum(m) > 0) ret = m, l = m + 1;
else r = m - 1;
}
mx_positive_cycle = ret;
}
if (mx_positive_cycle <= 0) {
int suffix_mx = 0;
for (int i = 0, s = 0, o = n + 1; i < n; i++, o++) {
s += a[i] - o;
maxa(suffix_mx, s);
}
maxa(ans, suffix_mx + prefix_mx);
} else {
for (int i = 0; i < 2; i++) {
int tmp = prefix_mx;
tmp += cycle_range_sum(1, mx_positive_cycle - 1);
int suffix_mx = 0;
for (int i = 0, s = 0, o = mx_positive_cycle * n + 1; i < n; i++, o++) {
s += a[i] - o;
maxa(suffix_mx, s);
}
tmp += suffix_mx;
maxa(ans, tmp);
mx_positive_cycle++;
}
}
cout << ans;
}
Solution 2 - Editorial
N 주기의 어떤 부분을 한칸 오른쪽으로 옮기면 그 값에서 N이 줄어든 합이 된다.
이제 이 구간이 음수가 되지 않는 첫 구간을 찾아주자.
이를 [p, p+N) 이라 하자.
에디토리얼 에서 몇가지 관찰을 이용해 시작점은 항상 [1,N] 이고 끝점은 항상 [p,p+N−1] 이고 p<2N 인 예외케이스도 같이 처리해주면 된다.
이렇게 만들어진 수열에서 카데인 알고리즘 DP를 쳐주면 된다.
Comments