E. Chain Reaction (Educational Codeforces Round 164 Div. 2)

• 링크

https://codeforces.com/contest/1954/problem/E

• 내가 푼 방법

아마 혼자서 아무런 힌트도 보지 않고 푼 문제 중 가장 어려운 문제라고 할 수 있을 것 같다.
풀어내고 나서 굉장히 뿌듯했다.

생각보다 푸는 방법은 어렵지 않았다. 다만 내가 푸는 방식에서는 세그먼트 트리, 누적합, 분할정복이 필요하고 알기만 하면 된다. 그리고 시간 복잡도의 증명도 조금 알아야 한다.

1. 분할정복

일단, 1~maxElement까지 모든 k를 돌면서 최소 몇 번 만에 몬스터들을 다 죽일 수 있는지 판단해야 한다.
사실, 근데 잘 생각해 보면 어떤 몬스터를 선택하는지는 중요하다. 어떤 몬스터를 선택하더라도 죽은 몬스터를 만나지만 않는다면 끝까지 가기 때문이다.

즉, 선택하는 몬스터가 아니라 선택하는 영역이 중요한 것이다.
영역은, 어떻게 나뉠까? 가장 작은 수를 기준으로 왼쪽, 오른쪽으로 나뉘게 된다. 전형적인 분할정복이다.
가장 작은 수를 고르는 과정에서 세그먼트 트리가 필요했다. 아마 다른 방법으로 풀 수 있었겠지만 나는 세그먼트 트리가 생각이 났다.

2. 누적합

그러면 이제 각각의 k마다 빠르게 minimum 한 횟수를 구할 수 있어야 한다.
도저히 생각나지 않는 와중에 그림을 그리다가 깨달을 수 있었다.

그림을 보면 알 수 있듯이, 특정수가 가장 minimum 한 영역의 개수를 알아낼 수 있다. 그러면 이것을 이용해서 현재까지 x의 데미지를 줬다면, 남은 구간의 수를 구할 수 있다.

하지만, 1~maxElement까지 해당 구간의 수를 이용하여 몇 번의 공격을 날렸는지 알려면 각각 하나의 k 씩 k만큼 증가하면서 구간의 수를 알아내야 한다.

딱 봤을 때는 시간 복잡도가 무조건 넘어갈 것으로 생각했다.

그때, 연산 횟수를 정리해 보았는데 아래와 같은 수식이 나왔다.

딱 봐도 기하급수적으로 증가 폭은 낮아질 것이로 생각이 들었고, 인터넷에 검색해 보니 log 단위라고 한다. 물론 발산하는 형태이긴 하다.

어쨌든 이렇게 해서 하나하나 구해도 시간복잡도가 넘지 않는다고 판단한 뒤에 구성한 코드들이 다음과 코드이다.

• 시간 복잡도

https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%99%94%EA%B8%89%EC%88%98
1+1/2+1/3+...1/1e5는 log 1e5로 나타낼 수 있다.
그렇기 때문에, 시간 복잡도는
O(max(n * log n, maxElement * log maxElement)) 로 결정될 수 있다.

• Correct Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

vector<long long> arr;
vector<long long> tree;
long long n;
long long height;
long long leafNodeCnt;
vector<long long> add;
vector<long long> cnt;

void initTree() {
    for (int i = height - 1; 0 <= i; i--) {
        for (int j = 1 << i; j < (1 << (i + 1)); j++) {
            long long leftIdx = tree[2 * j];
            long long rightIdx = tree[2 * j + 1];
            if (arr[leftIdx] <= arr[rightIdx]) {
                tree[j] = leftIdx;
            } else {
                tree[j] = rightIdx;
            }
        }
    }
}

long long searchMin(int cur, int left, int right, int sl, int sr) {
    if (sl <= left && right <= sr) {
        return tree[cur];
    }
    if (sr < left || right < sl) {
        return 0;
    }
    long long leftIdx = searchMin(cur * 2, left, (left + right) / 2, sl, sr);
    long long rightIdx = searchMin(cur * 2 + 1, (left + right) / 2 + 1, right, sl, sr);
    if (arr[leftIdx] <= arr[rightIdx]) {
        return leftIdx;
    }
    return rightIdx;
}

void dnq(long long left, long long right) {
    if (left == right) {
        add[arr[left]]--;
        return;
    }
    long long addSum = -1;
    long long minIdx = searchMin(1, 1, leafNodeCnt, left, right);
    if (left != minIdx) {
        dnq(left, minIdx - 1);
        addSum++;
    }
    if (right != minIdx) {
        dnq(minIdx + 1, right);
        addSum++;
    }
    add[arr[minIdx]] += addSum;
}

void solve() {
    cin >> n;
    arr.resize(n + 1, 0);
    arr[0] = 2e9;
    long long maxElement = 0;
    for (int i = 1; i < arr.size(); i++) {
        cin >> arr[i];
        maxElement = max(maxElement, arr[i]);
    }
    height = ceil(log2(n));
    leafNodeCnt = 1 << height;
    tree.resize(leafNodeCnt * 2, 0);
    for (int i = 0; i < n; i++) {
        tree[i + leafNodeCnt] = i + 1;
    }
    initTree();
    add.resize(maxElement + 2, 0);
    cnt.resize(maxElement + 2, 0);
    dnq(1, n);
    long long addSum = 1;
    for (int i = 1; i < add.size(); i++) {
        cnt[i] = addSum;
        addSum += add[i];
    }
    for (int i = 1; i <= maxElement; i++) {
        long long result = 0;
        long long num = 0;
        while (true) {
            if (cnt.size() <= num + 1 || cnt[num + 1] == 0) {
                break;
            }
            result += cnt[num + 1];
            num += i;
        }
        cout << result << " ";
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("e.input.txt", "r", stdin);
    solve();
    return 0;
}