[Codeforces] Round 850 - Monsters (hard)

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

문제

각각 $a_i$의 체력을 가진 $n$ 마리의 monster가 주어졌을 때,
우리는 2가지 연산을 수행할 수 있다.

1. 임의의 살아있는 몬스터에 1의 데미지를 준다.
2. 살아있는 모든 몬스터에게 1의 데미지를 준다.
   (만약, 이 과정에서 1마리 이상의 몬스터가 죽는다면, 2번 연산을 반복한다.)

2번 연산은 매 step마다 한번만 사용이 가능하다.

$k = 1, 2, ..., n$ 마다, $k$ 마리의 몬스터를 모두 죽이기 위한 1번 연산의 최소 수행 횟수를 구해야 한다.

example

1
3
3 1 2

풀이

1번 연산의 횟수를 최소로 만들기 위해선 2번 연산의 효율을 높이면 된다.
(즉, 몬스터의 체력이 1부터 시작하여 연속적이게 만들면 된다.)

예를 들어, 현재 몬스터들의 체력이 [ 4, 4, 4, 4 ]일 때,
몬스터들의 체력을 [ 1, 2, 3, 4 ] 로 만든다면, 2번 연산을 통해 모든 몬스터를 죽일 수 있다.

한가지 생각할 점이 있다면, 고려하지 않아도 되는 몬스터의 체력이 존재한다는 점이다.

고려하지 않아도 되는 몬스터가 중요한 이유는 다음과 같다.

위의 사진처럼 고려하지 않아도 되는 몬스터로 인해 1번 연산횟수가 달라지기 때문이다.

그렇다면 고려하지 않아도 되는 몬스터가 없을 경우, 1번 연산 횟수는 어떻게 될까?

오름차순으로 정렬된 몬스터들의 체력을 $a$라 하고,
2번 연산을 수행하기 직전 몬스터들의 체력을 $b$라고 할 때

1번 연산 수행 횟수는 아래와 같이 구할 수 있다.
$\sum_{i=1}^{m} (a_i - b_i) = \sum_{i=1}^{m} a_i - \frac{m(m+1)}{2}$ ($m$은 현재 몬스터로 만들 수 있는 연속적인 수열의 최소 크기)

우리는 매 step에서 몬스터가 추가될 때, 고려하지 않아도 되는 몬스터를 제외하고 계산함으로써 1번 연산 횟수를 최소로 만들 수 있다.
(위의 예시에서는 체력이 2인 몬스터가 들어왔을 때, 체력이 5인 몬스터를 고려하지 않음으로써 a의 합을 줄였다)

더 나아가 고려하지 않아도 되는 몬스터는 어떻게 구할 수 있을까?

1 ~ m까지 $b$를 만듦에 있어서 임의의 $x$에 대해 $x$를 초과하지 않는 monster의 수가 $k_x$라고 한다면
$k_x > x$ 인 $x$ 값이 존재한다면 '고려하지 않아도 되는 몬스터'가 존재한다는 것을 알 수 있다.
(1 ~ 5까지의 $b$를 만들 때, 1 ~ 5 사이의 값이 6개 있으면 하나는 필요없는 값임)

---

위에서 정리한 것을 토대로 1 ~ n까지의 각 $x$에 대해서 $x - k_x$ 값을 저장할 것이다.
그리고 체력이 $x$인 몬스터가 추가될 때마다 $[x:n]$ 범위의 값을 1씩 빼주면 된다.

이 때, $x - k_x < 0$인 값이 존재할 때마다 해당 조건을 만족하는 가장 작은 $x$의 몬스터를 없애주면 된다. (다시말해 고려하지 않는다)

마지막으로 체력이 $x$인 몬스터가 들어올 때마다 구간 연산이 수행이 되는데,
느리게 갱신되는 세그먼트트리를 사용하면 구간 연산을 빠르게 구할 수 있다.

느리게 갱신되는 세그먼트 트리 가이드

code

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
using lld = long long;

struct Info {
	lld value;
	lld idx;
};

Info min(const Info& a, const Info& b) {
	if (a.value == b.value) {
		if (a.idx < b.idx) {
			return a;
		}
		return b;
	}
	else if (a.value < b.value) {
		return a;
	}
	return b;
}

void update_lazy(vector<Info>& segtree, vector<lld>& lazy, int idx, int start, int end) {
	if (lazy[idx] != 0) {
		segtree[idx].value -= lazy[idx];
		if (start != end) {
			lazy[idx * 2] += lazy[idx];
			lazy[idx * 2 + 1] += lazy[idx];
		}
		lazy[idx] = 0;
	}
}

void update(vector<Info>& segtree, vector<lld>& lazy, int idx, int start, int end, int left, int right, int value) {
	update_lazy(segtree, lazy, idx, start, end);

	if (end < left || right < start) {
		return;
	}

	if (left <= start && end <= right) {
		segtree[idx].value -= value;
		if (start != end) {
			lazy[idx * 2] += value;
			lazy[idx * 2 + 1] += value;
		}
		return;
	}

	int mid = (start + end) / 2;
	update(segtree, lazy, idx * 2, start, mid, left, right, value);
	update(segtree, lazy, idx * 2 + 1, mid + 1, end, left, right, value);
	segtree[idx] = min(segtree[idx * 2], segtree[idx * 2 + 1]);
}

void init(vector<Info>& segtree, int idx, int start, int end) {
	if (start == end) {
		segtree[idx] = { start + 1, start };
		return;
	}

	int mid = (start + end) / 2;
	init(segtree, idx * 2, start, mid);
	init(segtree, idx * 2 + 1, mid + 1, end);
	segtree[idx] = min(segtree[idx * 2], segtree[idx * 2 + 1]);
}

int main() {
	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;

		vector<Info> segtree((n + 1) * 4);
		vector<lld> lazy((n + 1) * 4);
		init(segtree, 1, 0, n);
		
		lld cur_value;
		lld sum = 0;
		lld size = 0;
		for (int i = 0; i < n; i++) {
			cin >> cur_value;
			cur_value--;

			update(segtree, lazy, 1, 0, n, cur_value, n, 1);
			if (segtree[1].value < 0) {
				sum += (cur_value + 1) - (segtree[1].idx + 1);
				update(segtree, lazy, 1, 0, n, segtree[1].idx, n, -1);
			}
			else {
				sum += cur_value + 1;
				size++;
			}
			cout << sum - (size * (size + 1)) / 2 << " ";
		}
		cout << "\n";
	}

	return 0;
}