BOJ 28355 - 무한 수열

BOJ 28355 - 무한 수열

Solution 1

내가 푼 방법인데, $\displaystyle \sum_{i=kn+1}^{(k+1)n} A_{(i-1) ~ \% ~ n + 1}-n \cdot kn-\dfrac{n(n+1)}{2}$ 라는 $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를 쳐주면 된다.