Sign in Subscribe

Codeforces Round #687 (Div.2) A~E

witch

• 14 min read

어제 돌았던 버추얼을 이제 풀이를 쓴다. 이때 현장에서 치렀어야 했다는 생각이 강하게 든다. 아무튼 원래 내가 잘 풀었으면 좋은 셋이고 내가 말리면 구데기셋이라는 알고리즘 판의 합리화 법칙에 따라 이건 좋은 셋이었다.

A. Prison Break

Problem - A - Codeforces
Codeforces. Programming competitions and contests, programming community
Codeforces

n행 m열 사이즈의 격자로 된 감옥에 죄수들이 칸마다 각각 한 명씩 갇혀 있다. 그런데 (r,c) 위치에 탈옥할 수 있는 구멍이 있다. 모든 죄수들이 1초에 한번씩 상하좌우로 움직일 수 있고 최적으로 움직일 때 모든 죄수들이 탈옥구멍으로 도달하는 데까지 걸리는 시간을 구하면 된다. 모든 칸에 죄수들이 무조건 있다고 했으므로 (탈옥 구멍에서 가로로 가장 먼 사람의 거리)+(탈옥 구멍에서 세로로 가장 먼 사람의 거리) 가 답이다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, m, r, c;
		cin >> n >> m >> r >> c;
		int ans = max(n - r, r - 1) + max(m - c, c - 1);
		cout << ans << "\n";
	}
 
	return 0;
 
}

B. Repainting Street

Problem - B - Codeforces
Codeforces. Programming competitions and contests, programming community
Codeforces

1부터 n까지의 번호가 붙은 집들이 쭉 늘어서 있다. 각각의 집들은 $$ c_i $$ 의 색으로 칠해져 있다. 이때 우리는 n개의 집들을 모두 하나의 색으로 통일하고 싶다. 그런데 집의 색을 덧칠하는 능력은 한정되어 있어서, 하루에 연속된 집 k개만 원하는 색으로 덧칠할 수 있다(물론 k개의 연속된 집 중 이미 원하는 색으로 칠해진 집이 있다면 그 집은 안 칠하고 그냥 넘어가도 된다). 그때 가장 적은 일수만 써서 집을 칠하려면 며칠이 필요한지 구하면 된다. 집의 개수가 10만개이고 색은 최대 100개밖에 안 되므로 모든 색에 대해, 모든 집을 같은색으로 다 칠하는 데 걸리는 시간을 계산해 보고 그중 가장 작은 것을 택하면 된다. 대충 잡아 1000만의 연산횟수. 제한시간 1초에 넉넉히 들어온다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, k, arr[100005];
		cin >> n >> k;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		int max_color = 0;
		for (int i = 0; i < n; i++) {
			max_color = max(max_color, arr[i]);
		}
 
		int ans = 10000000;
		for (int i = 1; i <= max_color; i++) {
			int cur_color = i, cur = 0, tmp_ans = 0;
			while (cur < n) {
				if (arr[cur] != cur_color) {
					cur += k;
					tmp_ans++;
				}
				else {
					cur += 1;
				}
			}
			ans = min(ans, tmp_ans);
		}
		cout << ans << "\n";
 
 
	}
 
	return 0;
 
}

C. Bouncing Balls

Problem - C - Codeforces
Codeforces. Programming competitions and contests, programming community
Codeforces

칸이 지어진 2차원 직선 바닥에서 공을 튀겨서 나아가게 한다고 생각해 보자. 우리는 p번째 칸에서 공을 튀기고, 공은 k칸 간격으로 튀기면서 나아간다. 즉 p, p+k, p+2k, ... 번째 칸을 밟으면서 나아간다는 것이다. 그런데 만약 공이 밟아야 하는 칸에 바닥이 없다면 공은 떨어지고 만다. 우리는 이 공이 무사히 튀기면서 n번째 바닥을 지날 수 있도록 해야 한다.

문제에서는 공을 튀기는 초기의 바닥의 상태가 주어진다. 그런데 우리는 공을 무사히 n번 지점까지 통과시켜야 하므로, 우리에게 2가지 연산이 허용된다. x초를 사용하면 원래는 바닥이 없던 칸에 바닥을 만들어줄 수 있다. 그리고 y초를 사용해서 첫번째 바닥을 없애고 남은 바닥들을 한 칸씩 앞으로 끌어와 줄 수 있다. (단 아무리 바닥을 없애도 바닥은 최소 p칸 이상 남아 있어야 한다)

처음 생각은, 만약 블럭을 하나도 없애지 않고 진행하려고 한다면 p, p+k, p+2k,...,(n이하) 칸에 모두 블럭이 있어야 한다. 따라서 블럭이 없는 칸에 블럭을 생성하는 비용만이 든다.

그리고 맨 앞의 블럭 한 칸을 없애고 시작하면 p+1, p+k+1, p+2k+1, ...칸에 모두 블럭이 있어야 하고 (블럭 한 칸 없애는 비용)+(밟아야 하는 칸들 중 블럭 없는 칸에 블럭 생성하는 비용) 만큼이 든다. 이런 식으로 하면 0~k-1개의 블럭을 없애고 나서 게임을 진행하는 경우에 대한 각각의 비용이 발생하는데 이 중에 최솟값을 구하면 된다고 생각해서 코드를 짰다. 틀렸다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, p, k;
		string level;
		cin >> n >> p >> k;
		p--;
		cin >> level;
		int x, y, ans = 2000000000;
		cin >> x >> y;
		for (int i = p; i < p + k; i++) {
			int make = 0;
			for (int j = i; j < n; j += k) {
				if (level[j] != '1') { make++; }
			}
			ans = min(make * x + (i - p) * y, ans);
		}
		cout << ans << "\n";
 
	}
 
	return 0;
 
}

생각하지 못했던 부분은, 만약 블럭을 없애는 비용이 아주 적고 블럭을 생성하는 비용이 매우 크다면 블럭을 최대한 없애는 게 이득이라는 것이었다. 따라서 k-1개의 블럭까지 없애는 경우만이 아니라, p개만 남기고 모든 블럭을 없애버리는 경우까지 생각해야 한다는 것이다. 그리고 이걸 단순히 나이브로 처리할 경우 시간복잡도가 O(n^2)가 되어 버리므로 시간초과가 난다(그래서 나도 시간초과를 1번 받았다). 따라서 어느 칸에서 시작하냐에 따라 몇 개의 칸을 새로 생성해야 하는지를 저장해 두는 배열을 미리 만들어 두고 풀어야 한다. 밑 코드의 dp배열이 그것이다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		int n, p, k;
		string level;
		cin >> n >> p >> k;
		cin >> level;
		p--;
		int x, y, ans = 2000000000;
		cin >> x >> y;
 
		int dp[100005] = { 0 };
 
		for (int i = p; i < n; i++) {
			if (level[i] == '0') { dp[i % k]++; }
		}
 
		int push = 0;
		for (int i = p; i < n; i++) {
			int tmp_ans = dp[i % k] * x + push * y;
			ans = min(ans, tmp_ans);
			push++;
			if (level[i] == '0') { dp[i % k]--; }
		}
		cout << ans << "\n";
 
	}
 
	return 0;
 
}

D. XOR-gun

Problem - D - Codeforces
Codeforces. Programming competitions and contests, programming community
Codeforces

오름차순으로(갈수록 숫자가 커짐)된 수열이 주어진다. 우리가 가진 xor-gun을 쏘면 일어나는 일은, 수열의 인접한 두 숫자를 xor한 후에 그 숫자를 원래 두 숫자가 있던 자리에 삽입하는 것이다. 이때 우리는 이  xor-gun 을 최소한으로 쏴서 이 수열의 오름차순을 깨버리고 싶다. 수열의 오름차순을 깰 수 있는, 최소한의 xor-gun을 쏘는 횟수를 구하면 된다.

내가 대회 시간 안에 절대로 생각 못했던 부분이었는데(그래서 시간 내에 못 풀었음), 수열 내의 숫자의 최대 범위가 109 , 즉 230 이하이므로 만약 수열의 길이가 60 이상이면 최상위 비트가 겹치는 숫자 두 개 이상이 생기게 된다. 그때는 그 두 개의 숫자만 xor하면 수열의 오름차순이 깨진다(최상위 비트가 0이 되어 버리므로, 2배 이상 작아지고 따라서 양옆의 숫자들보다 작아진다). 수열의 길이가 60 이상일 땐 답이 1인 걸로 처리하면 된다는 것을 알 수 있다. 나머지 경우들 즉 수열의 길이가 60 미만일 때는 길이가 충분히 작으므로, 모든 경우의 수를 xor시켜보면 된다.

만약 우리가 어떻게 잘 xor-gun을 사용해서, 수열의 오름차순이 깨져서 $$ a_l > a_r $$ 인 상황이 생겼다고 하자. 그러면 $$ a_l = a_{l} \oplus\ ...\oplus\ a_m, a_r=a_{m+1} \oplus\ ... \oplus\ a_r $$ 이 될 것이다(m은 l과 r 사이의 어떤 중간 지점) 따라서 우리는 수열에서 나올 수 있는 모든 l,m,r에 대해 시뮬레이션을 해보고, $$ a_l > a_r $$ 이 되는 경우를 찾아서, 그 중 xor-gun발사횟수가 가장 적은 것을 답으로 내면 된다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, arr[100005];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	if (n > 60) { cout << "1\n"; }
	else {
		int ans = 2000000000;
		for (int gap = 2; gap < n; gap++) {
			for (int l = 0, r = gap; r < n; l++, r++) {
				for (int m = l; m <= r; m++) {
					int lxor = 0, rxor = 0;
					for (int i = l; i < m; i++) {
						lxor ^= arr[i];
					}
					for (int i = r; i >= m; i--) {
						rxor ^= arr[i];
					}
					if (lxor > rxor) { ans = min(ans, gap - 1); }
				}

			}
		}
		if (ans == 2000000000) { cout << "-1\n"; }
		else { cout << ans << "\n"; }
	}

	return 0;

}

E. New Game Plus!

Problem - E - Codeforces
Codeforces. Programming competitions and contests, programming community
Codeforces

솔직히 E의 위용에 걸맞지 않은 문제라고 생각한다. 나는 실제 대회에서 E를 잡아 본 적이 한번도 없지만(읽어 본 적도 기억에 없다) 이를 풀었고, 코드도 굉장히 간단하다.

우리는 1부터 n까지 번호가 붙어 있는 보스들을 하나씩 잡아 나간다. 보스를 잡는 순서는 내 마음대로 할 수 있다. 그런데 보스들마다 숫자 $$ c_i $$ 가 붙어 있다. 또한 '보스 보너스' 라는 개념이 있다. 처음의 보스 보너스는 0이다. 내가 어떤 보스를 잡으면 현재의 보스 보너스 값이 내 점수에 더해지고, 그 다음 그 보스의 $$ c_i $$ 가 보스 보너스에 더해진다. $$ c_i $$는 음수일 수 있고 따라서 보스 보너스 또한 음수가 될 수 있다. 보스를 잡으면 점수가 깎일 수도 있다는 것이다!

이때 우리는 게임의 버그를 이용할 수 있는데 게임을 진행하는 도중 원하는 때에, 잡은 보스들은 그대로 잡은 상태로, 보스 보너스 값을 0으로 초기화시킬 수 있다. 이 버그는 k번 사용 가능하다. 이 버그를 최대 k번 이용할 때, n마리의 보스를 전부 잡고 나서 얻을 수 있는 최대의 점수를 구하면 된다.

먼저 우리가 생각할 수 있는 건, 당연히 $$ c_i $$ 가 큰 보스부터 잡아야 한다는 것이다. $$ c_i $$ 는 보스 보너스에 누적되고, 보스 보너스는 내가 다른 보스를 잡을때마다 계속 더해지니 당연한 것이다. 그런데 우리는 k번, 보스 보너스를 초기화 가능하므로 잡는 보스들의 그룹을 k+1개로 나눌 수 있다고 생각할 수 있다. 한 개의 그룹을 다 잡고 초기화, 다음그룹 다 잡고 초기화... 한다고 생각하면 이해가 쉽다. 그럼 $$c_i$$가 큰 것부터 잡는다고 할 때, 그 보스를 어떤 그룹에 넣어야 하는가? 이는 현재 가장 누적된 보스 보너스가 큰 그룹에 넣으면 된다. 그렇게 해야, 만약에 보스 보너스나 $$c_i$$가 음수더라도 점수의 감소를 최소화할 수 있기 때문이다. $$c_i$$가 큰 보스부터 잡는 건 정렬로 처리할 수 있고 k+1개의 그룹 관리는 우선순위 큐로 할 수 있다.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <queue>
typedef long long ll;
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	ll n, k, score[500005];
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> score[i];
	}
	sort(score, score + n, greater<ll>());
	priority_queue<ll> pq;
	for (int i = 0; i < k + 1; i++) { //k+1 group of boss
		pq.push(0);
	}
 
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ll largest = pq.top(); pq.pop();
		pq.push(score[i] + largest); //보스잡고 보너스
		ans += largest;
	}
	cout << ans << "\n";
 
	return 0;
 
}

우선순위 큐라는 아이디어가 생각보다 ps에서 자주 쓰임을 느낀다. 최근에 푼 https://www.acmicpc.net/problem/15748 도 그렇고, 무엇보다 내가 이 E번을 푸는 데 가장 결정적인 역할을 했던 문제는 https://codeforces.com/contest/1353/problem/D 이 문제다. Lawali 님이 '이 문제는 딱 봐도 그거(우선순위 큐)다' 라는 말을 남기셔서 왠지 열받아서 그 뒤로 우선순위 큐라는 것을 문제 풀 때마다 약간씩은 염두에 두게 되었다.

아이디어를 떠올리는 것 자체는 엄청 어렵지는 않고(물론 진짜 라이브로 대회 칠 때는 풀 수 있다고 장담 못하겠지만 나는 다른 D,E급 문제들에 비해서는 쉬운 아이디어라고 느낀다), 우선순위 큐를 생각할 수 있다면 풀 수 있을 것 같은 문제다.

Sign up for more like this.

Enter your email
Subscribe