Div.2 #915 D - Cyclic MEX

실제 contest중에는 풀지 못한, 난이도 높은 문제였다.

Upsolving 을 진행하며, 정리한 내용을 공유하고자 한다.

문제

https://codeforces.com/contest/1905/problem/D

• n<100만
• n^2 으로는 절대 풀 수 없는 문제이다.

핵심 아이디어

1. 반드시 맨 앞 원소가, 맨 뒤로 간다.

중요한 통찰을 얻을 수 있는 단서 중 하나는, a[0]이 맨 뒤로 간다는 것이다.

이 사실을 응용해보자

2. MEX값은, 범위가 넓어지면 넓어질수록 무조건 증가하는, 단조증가 형태를 띈다.

단조증가 성질 또한, 무궁무진한 활용 가능성을 갖추고 있다.

그리디한 접근 혹은, 파라매트릭 서치에도 응용이 가능하니, 기억하고 있도록 하자.

3. 값이 순열로 주어진다.

중요한 통찰을 얻을 수 있는 마지막 단서는, 값이 순열로 주어진다는 것이다.

b[i] 를 1부터 i까지 범위의 mex값이라고 해보자.

mex값은 기본적으로 해당 값이 사라지면, 그보다 큰 값들이 모두 사라진 값으로 치환된다.

따라서

• a[0]보다 큰 b[i]값은 a[0]이 된다.
• a[0]보다 작은 b[i]는 변화를 갖지 않는다.

또한, a[0]과 같은 다른 인덱스에 존재하는 수는 없다.

그 과정에서 b[i]의 맨 뒤에 있던 n이 a[0] 이 되고, b[n-1] = n이 된다.

→ 따라서, 이전 해를 다음 해에 이용해보자.

MEX 계산법

정확히 뭘 구해야 하는 거지?

우리는 첫 번째 칸부터, mex값을 차근차근 계산하여, b[i]를 완성해야 한다.

따라서, 다음과 같은 과정을 통해, b[i]를 완성할 수 있다.

근데, 우리가 맨 앞의 원소를 제거하려면, mex의 순서 정보가 중요하다.

맨 앞 원소가 사라짐으로써, 어떠한 mex가 사라지는지를 알아야, cost의 변화량을 계산할 수 있다.

하지만, mex는 범위가 커질수록 증가하는 단조증가 형태를 띈다.

따라서

• 존재하는 가장 낮은 mex의 값을 하나 제거하기만 해도, 맨 앞 원소를 제거한 효과를 만들 수 있고,
• 존재하는 가장 큰 mex의 값은, 가장 넓은 범위의 mex값을 의미한다고 할 수 있다.

따라서, 우리는 주어진 mex값을 다음과 같이 “압축”할 수 있다.

시간복잡도 계산이 까다로운 문제였다.

그래서 이게 잘 동작할까? 예상을 한번 해보자.

• 반드시 pop은 최대 2n번만 일어난다.
  1. a 보다 큰 값은 a가 된다
  2. 그 값은 압축되서 저장됨 - 이후로는 1번만 동작
  3. 값이 변하는 순간, 해당 값에 대해서는 1번만 동작 가능
  4. 바뀌는 순간, a는 더이상 a가 아니게 되고, 다른 값으로 변화됨
  5. 다시 1번으로 돌아감
• push도 n번 일어난다.

따라서, 우리는 주어진 “a[0]을 맨 뒤로 보내기” 연산이 총 O(n) 번 발생한다는 것을 확인할 수 있다.

cost 변화량 계산법은 뭐지?

1. 맨 앞 인덱스의 제거가 필요하다.
   • 제일 앞 mex값을 갖는 경우 1개가 사라짐
2. 맨 앞 수가 사라짐으로 인한, 영향받는 경우 제거해야 한다.
   • a[0]보다 큰 애들은 a[0]이 된다.
   • a[0]보다 작은 애들은 변화가 없다.
   • a[0]과 같은 다른 인덱스에 존재하는 수는 없다.
3. 기존의 a[0]보다 큰 b[i] 값들이 a[0]이 된 경우에 대한 sum 값을 추가해야 한다.
   • 이때, dq에 a[0]을 함께 추가해주도록 하자.
4. sum에 p1이 맨 뒤로 가서 생기는 n을 추가해야 한다.
   • 이때, dq에 n을 함께 추가해주도록 하자.

• if (ans < sum) ans = sum; 로 마무리가 가능하다.

풀이

난이도 높은 문제는, 한가지 접근 방식으로 모든 것이 해결되진 않는다.
다양한 방식으로 접근해보고 풀어보려고 노력해야, 답이 나오는 경우가 많으니
탑다운, 바텀업 모두 사용해보며, 여러 방면으로 고민해보자.

#include <bits/stdc++.h>
#define ll long long
#define INF ((int)1e9 + 10)
#define lINF ((ll)1e18 + 10LL)
const ll MOD = 1000000007LL;
// #include <atcoder/modint.hpp>
// using mint = atcoder::modint998244353;

using namespace std;

void Solve() {
    int n;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    vector<ll> mexCnt(n + 1);
    vector<ll> arrCnt(n + 1);
    ll mex = 0;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        arrCnt[arr[i]]++;
        while (arrCnt[mex]) mex++;
        mexCnt[mex]++;
    }

    deque<pair<ll, ll>> dq;
    for (int i = 0; i <= n; i++) {
        if (mexCnt[i] != 0) dq.push_back({i, mexCnt[i]});
        sum += i * mexCnt[i];
    }

    ll ans = sum;
    for (int i = 0; i < n - 1; i++) {
        int cnt = 0;
        sum -= dq.front().first;
        dq.front().second--;
        if (dq.front().second == 0) dq.pop_front();
        while (!dq.empty() && dq.back().first > arr[i]) {
            sum -= dq.back().first * dq.back().second;
            cnt += dq.back().second;
            dq.pop_back();
        }
        sum += arr[i] * cnt + n;
        dq.push_back({arr[i], cnt});
        dq.push_back({n, 1});
        if (sum > ans) ans = sum;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) Solve();
    return 0;
}

/*
찾아야 할 것들
1. int 오버플로우, out of bounds
2. 특수한 경우(n=1?)
3. 잘못된 가정 & 증명

*아무것도 하지 않는 대신 무언가를 수행하기. 체계적인 상태를 유지.
*적어두기 & 구하고자 하는 것의 계층 구조 표현 -> 정확히 & 입체적으로 파악
*한가지 접근 방식에 얽메이지 말기 -> 응용의 끝 알기
*/
// 알고리즘의 작동방식 "완전히" 이해하려 노력하기 -> 수식 & 그림화, 조건 정리
// 수행 목표
// 1. 아이디어 획득 : "추론"
//     - 문제 알고리즘/특징의 "증명"으로 아이디어
//         - {BruteForce, greedy, D&C, DP, graph, math}
//     - 전체 알고리즘이 “결국 구하고자 하는 것” 놓치지 않기
//     - “책임” 뽑아내기 -> 개념화, 정의, 추상화, 귀납적 사고
//         - 각 기능들이 어떤 책임을 가지고 있는지
//         - “어떤 패턴”으로 동작하는지
//     - 가장 Naive한 상태/알고리즘부터 시작하기 (완전 탐색, 단순 자료구조)
//     - 뚜렷한 증명이 나오지 않을 땐, 어떤 기준을 만들고 나눠서 보기
//     - 뚜렷한 최적화 기법이 떠오르지 않을 땐, 문제에 주어진 특이한 특징을 잡기
//     - 단위 동작의 조건 분기 파악
//     - 가장 극단적인 경우에서 추론 (가장 차이가 뚜렷한 예제)
// 2. "처음"부터 직접 경우의 수 전개(수식&도식화, 엄밀한 조건 정리)
//     - 알고리즘 내에 어떤 역할들이 있는지 -> 직접 들어가보기
//     - 알고리즘 내에 어떤 기능들이 있는지 -> 직접 수행해보기
//     - "끝까지 구체화"로 접근해야, "깔끔한 추상화"가 나온다.
// 3. cutting | 구현(차근차근 단순화 & 최적화)

/*
수학적 접근 방법
1. 불변성
2. 극단성
3. 홀짝성
4. 단조성
5. 선형성
6. 영역성
*/

/*
정당성 증명 방법
1. 귀납법 -> 결과값 만드는 점화식의 존재성을 증명하는 것
2. 귀류법 -> 결과값의 참/거짓을 가정하고 이전단계의 모순을 발견하여 증명
3. 경우에 의한 증명 -> 반례 찾기
4. 구성적 증명 -> 부분문제의 결과값을 만드는 원인를 분석하여 증명하는 방법
5. 비둘기집의 원리
6. 대각선 논법(연역법) -> A<C 이고 C<B 임을 이용해 A<B를 증명하는 방법
*/

/*
take notes.
// 다시 보는용이 아닌
// 현재의 흐름을 가장 잘 이어갈 수 있도록 !!!

*/

// commit 시 피드백할 것 Message로 남겨두기!!
// 틀리면 느낌표 추가하기