아인스트라세의 SW 블로그

오랜만에 퇴근 후 23:35 쯤에 코드포스 라운드가 있길래 참여해보았다.

최근 코포에서 미끄러져서, 레이팅이 블루에서 다시 민트로 떨어져버렸는데

다시 블루로 돌아가겠다는 신념으로 참가한 라운드였다.

Div2는 총 7문제가 나왔고, 결과는 4솔

A번 문제 Changing Volume

https://codeforces.com/contest/1255/problem/A

볼륨을 a에서 b로 변경해야 하는데, 볼륨은 음수가 불가능하고 버튼 한번을 눌러서 +- 1,2,5 중 하나의 액션을 할 수 있다.

총 6가지 액션이 가능한 셈이다.

버튼을 최소 횟수를 눌러서 볼륨을 a에서 b로 변경할 때, 최소 누르는 횟수를 알아내는 문제이다.

뭔가 bfs로 탐색을 해야 정확할 것 같은 느낌인데, 케이스를 나눠서 보면 그리디하게 풀린다.

만약 a와 b의 절댓값 차이가 5이하인 경우들을 체크해보자.

차이가 5인 경우 = +5를 한번 누름

차이가 4인 경우 = +2를 두번 누름 = 혹은 +5를 한번, -1를 한번 누름

차이가 3인 경우 = +2를 한번 +1를 한번 누름 = +5를 한번, -2를 한번 누름

차이가 2인 경우 = +2를 한번 누름 < +5를 한번, -2를 한번, -1를 한번 해서 총 3번 누름

차이가 1인 경우 = +1를 한번 누름 < +5를 한번 -2를 두번 해서 총 3번 누름

차이가 5초과인 경우는 5를 누르는 것이 최소로 줄이는 것이 자명한 상태이다.

차이가 5이하인 경우도, +5와 -를 조합하는 경우와 +만으로 누르는 경우를 비교했을 때, +만으로 조합하는 경우가 횟수가 작거나 같다.

따라서 차이값에 대하여 큰 단위부터 누르면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
void solve() {
	int a, b;
	cin >> a >> b;
	int diff = abs(a - b);
	int ans = 0;
	ans += diff / 5;
	diff %= 5;
	ans += diff / 2;
	diff %= 2;
	ans += diff;
	cout << ans << endl;
}
int main() {
	int tc;
	cin >> tc;
	while (tc--) solve();
}

B번 문제 Fridge Locker

https://codeforces.com/contest/1255/problem/B

논란이 많은 문제이다...

냉장고가 private 해 지기 위해서는, 서로다른 2개 이상의 냉장고와 연결된 체인이 있어야 한다.

이 조건은 모든 냉장고에 다 적용되어야 하므로, 최소 냉장고 개수와 동일한 수의 체인이 있어야 조건이 맞게 만들 수 있다. (체인 하나 당 2개의 냉장고를 연결하므로)

그리고 cost는 냉장고별 고유값을 더한 값이므로, 어차피 모든 냉장고는 고유값 * 2만큼은 코스트를 써야 한다는 점에

그냥 원형으로 체인을 덮은 뒤, 남는 체인들은 a값이 가장 낮은 냉장고에 걸어버리는 식으로 풀이를 했다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
typedef pair<int, int> pii;
pii a[2005];
void solve() {
	int n, m;
	cin >> n >> m;
	int total = 0;
	for (int i = 0; i < n; i++) {
		a[i].second = i + 1;
		cin >> a[i].first;
		total += a[i].first;
	}
	total *= 2;
	sort(a, a + n);
	if (m < n || n <= 2) {
		//impossible
		cout << -1 << endl;
		return;
	}
	int rest = m - n;
	total += rest * (a[0].first + a[1].first);
	cout << total << endl;
	for (int i = 1; i < n; i++) {
		cout << i << ' ' << i + 1 << endl;
	}
	cout << n << ' ' << 1 << endl;
	for (int i = 0; i < rest; i++) {
		cout << a[0].second << ' ' << a[1].second << endl;
	}
}
int main() {
	int tc;
	cin >> tc;
	while (tc--) {
		solve();
	}
}

라고 생각했지만, 엄청난 반례가 나타나게 되는데....

https://codeforces.com/blog/entry/71562

위의 그림의 경우, 내가 만든 풀이법에 대한 반례가 된다. 남는 체인이 있는 경우 저런 경우가 생기는 것이다.

보통 이런 경우가 생기면 해당 코드포스 라운드는 Unrate가 되어 점수 반영이 되지 않게 되는데, 이번에는

해당 문제 오류때문에 피해를 본 사람만 따로 어필을 한 경우 그 해당 사람만 Unrate되도록 조치되었다.

어쨋든 문제를 푸는 도중에는 이러한 사실을 잘 몰랐다 ㅠ

C번 League of Leesins

https://codeforces.com/contest/1255/problem/C

문제 본문은 좀 특이했던듯.

Permutation 원본에서, 원래 위치에서 3개씩 끊어서 자른 뒤 3개짜리 묶음의 순서와, 묶음 내 순서를 마구잡이로 섞은 것을 준다.

이를 통해 원본을 알아내야 하는데,

인접한 묶음들은 2개의 숫자가 동일하다는 것을 알 수 있다.

그리고 처음과 끝에 등장하는 숫자 하나는 단 한번만 등장한다는 특징이 있으므로, 이를 이용해서 하나하나 연결시켜서

찾아나가면 된다.

구현이 좀 귀찮았던 문제이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int arr[100005][4];
vector<int> pos[100005];
 
vector<int> tail, subtail;
int find_val(int a, int b, int no) {
	for (int i = 0; i < pos[a].size(); i++) {
		for (int j = 0; j < pos[b].size(); j++) {
			if (pos[a][i] == pos[b][j]) {
				int idx = pos[a][i];
				int candid = arr[idx][3] - a - b;
				if (candid != no) {
					return candid;
				}
			}
		}
	}
	assert(false);
	return -1;
}
int find_pos(int a, int b) {
	for (int i = 0; i < pos[a].size(); i++) {
		for (int j = 0; j < pos[b].size(); j++) {
			if (pos[a][i] == pos[b][j]) {
				return pos[a][i];
			}
		}
	}
	assert(false);
	return -1;
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n - 2; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[i][0] = a;
		arr[i][1] = b;
		arr[i][2] = c;
		arr[i][3] = a + b + c; //summation
		pos[a].push_back(i);
		pos[b].push_back(i);
		pos[c].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (pos[i].size() == 1) tail.push_back(i);
		else if (pos[i].size() == 2) subtail.push_back(i);
	}
 
	vector<int> ans;
	int no = tail[0];
	ans.push_back(no);
	vector<int> rest;
	for (int i = 0; i < 3; i++) {
		int val = arr[pos[no][0]][i];
		if (val == tail[0]) continue;
		rest.push_back(val);
	}
	int prev;
	if (pos[rest[0]].size() == 2) {
		ans.push_back(rest[0]);
		ans.push_back(rest[1]);
		prev = rest[0];
	}
	else {
		ans.push_back(rest[1]);
		ans.push_back(rest[0]);
		prev = rest[1];
	}
	while(ans.size() < n) {
		//int position = find_pos(prev, ans.back());
		//int next = arr[position][3] - prev - ans.back();
		int next = find_val(prev, ans.back(), no);
		no = prev;
		prev = ans.back();
		ans.push_back(next);
	}
	for (auto v : ans) {
		cout << v << ' ';
	}
	cout << endl;
	return 0;
}

D번 Feeding Chickens

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

이것도 구현형 문제이다. 닭들이 Rice가 포함된 셀을 가장 비슷하게 가져가도록 만들면 된다.

전체 Rice 수를 R, 닭의 수를 K라고 할 때 //(floor(R/K)//)를 각자 주고, //(R - floor(R/K)*K//)만큼의 닭에게는 +1만큼 더 지급한다고 치면 된다.

그리고 땅 분할은 맨 위 row부터 지그재그로 가로로 훑고 내려오는 식으로 할당하면 된다.

첫줄을 왼쪽에서 오른쪽으로 훑고, 두번째 줄은 오른쪽에서 왼쪽으로 훑고, 그담에 다시 왼쪽에서 오른쪽

이런식으로 훑으면서 내려가면 인접한 땅을 할당하되 중복 할당 되지 않도록 할 수 있다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
vector<char> chick;
vector<int> needs;
string field[105];
int row_rices[105];
void solve() {
	int total_rices = 0;
	int r, c, k;
	cin >> r >> c >> k;
	memset(row_rices, 0, sizeof(row_rices));
	needs.clear();
 
	for (int i = 0; i < r; i++) {
		cin >> field[i];
		for (char c : field[i]) {
			if (c == 'R') row_rices[i]++;
		}
		total_rices += row_rices[i];
	}
 
	int each = total_rices / k;
	int rest = total_rices - each * k;
	for (int i = 0; i < rest; i++) {
		needs.push_back(each + 1);
	}
	for (int i = rest; i < k; i++) {
		needs.push_back(each);
	}
	int x, y, dir;
	x = y = 0;
	dir = +1;
	for (int i = 0; i < k; i++) {
		int need = needs[i];
		char ch = chick[i];
		int got = 0;
		while (got < need || i+1 == k) {
			if (y == -1) {
				dir = +1;
				y = 0;
				x++;
			}
			else if (y == c) {
				dir = -1;
				y = c - 1;
				x++;
			}
			if (x == r) break;
 
			if (field[x][y] == 'R') {
				got++;
			}
			field[x][y] = ch;
			y += dir;
		}
	}
	for (int i = 0; i < r; i++) {
		cout << field[i] << endl;
	}
	return;
}
int main() {
	for (char c = '0'; c <= '9'; c++) chick.push_back(c);
	for (char c = 'a'; c <= 'z'; c++) chick.push_back(c);
	for (char c = 'A'; c <= 'Z'; c++) chick.push_back(c);
	int tc;
	cin >> tc;
	while (tc--) solve();
 
	return 0;
}

E번부터는 풀지를 못했고 이해도 좀 덜 했는데, Editorial을 보면서 공부좀 해 보아야 겠다.

Editorial

https://codeforces.com/blog/entry/71594