Google Codejam Kickstart 2020 Round 1-C 후기

2020년 구글 코드잼 라운드 1C 후기

작년에 이어서 올해에도 구글 코드잼에 참가했는데, 작년에는 2라운드 진출까지만 하고, 2라운드에서는 그냥 던져버렸었다. 올해에는 좀 더 나아진 모습을 보여주고자 했는데 결국 라운드 1C까지 왔다.

 

구글 코드잼은 Qualification Round이후 Round 1로 넘어가는데, 1라운드의 경우 A,B,C로 총 3번의 기회가 있다. 각각의 라운드에서 1500등 안에 들면 다음 라운드인 Round 2로 진출하게 되고, A라운드에서 1500등 안에 들어서 다음 라운드로 진출하게 되면 다음 B, C라운드는 참여할 수 없다.

 

즉 각각 A,B,C 라운드 별 1500명이 다음 라운드로 진출하게 되어 결과적으로는 4500명이 Round 2로 진출하게 된다. 그런데 올해 구글 코드잼의 등록자는 역대급이라고 하며(근데 매년 등록자의 수가 늘어난다고는 한다) 라운드 1A, 1B에서 처참하게 발려버려서 자신감이 꽤나 떨어져있는 상태였다.

 

대충 처참한 나의 이전 라운드 성적이다.

 

하지만 이번 라운드에선 아슬아슬하긴 하지만 어째 저째 다음 라운드로 진출하게 될 것 같다.

In review 상태인데, 뭐 부정행위를 한 것도 아니고 1389등을 했으니 Round 2를 체험해볼 수 는 있을 것 같다. 다만 좀 걱정이 되는 것은 Round 2가 DEFCON CTF Qualification Round와 일정이 겹친다는 것... 뭐 코로나 때문에 일정이 더 밀릴수도 있긴 하겠지만 애매한 것은 사실이긴 하다.

 

어쨋든 기적적으로 라운드 2로 진출하게 되었으니 당분간은, 어차피 이 글을 쓰는 시기로 부터는 열흘밖에 시간이 없긴 하지만 PS 공부를 좀 더 해봐야 겠다.

 

1. Overexcited Fan

1번 문제인데, 생각보다 너무 쉽게 나왔어서 오히려 걱정이 되었다. 빨리 풀기 대결이 되지 않을까 하는 그러한 우려이다. 어차피 상대평가라 난이도가 너무 쉬우면 오히려 불리하게 작용할 때도 있었다.

 

움직이는 녀석을 가장 빨리 만날 수 있는 시간대를 찾는 문제인데, 이동 거리를 L1 Distance(맨하탄 거리)로 바로 알아낼 수 있고, 이동하거나 멈추거나 둘 다 가능하므로, 이동경로별로 원점에서의 맨하탄 거리보다 현재 시간이 더 긴 순간이 만나는 순간이 되겠다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'

const int dx[] = { +1, -1, 0, 0 };
const int dy[] = { 0, 0, +1, -1 };
int val(char c) {
	if (c == 'S') return 3;
	if (c == 'N') return 2;
	if (c == 'W') return 1;
	return 0;
}
void solve() {
	int x, y;
	string steps;
	cin >> x >> y;
	cin >> steps;
	int ans = -1;
	for (size_t i = 0; i < steps.size(); i++) {
		int k = val(steps[i]);
		x += dx[k];
		y += dy[k];
		int dist = abs(x) + abs(y);
		if (dist <= i + 1) {
			ans = i + 1;
			break;
		}

	}
	if (ans == -1) {
		cout << "IMPOSSIBLE\n";
	}
	else {
		cout << ans << endl;
	}
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

2. Overrandomized

꽤나 신박한 내용의 문제였다. TC가 3가지로 나뉘는데, 마지막 TC의 경우 //(Q=-1//)로 고정이라는 것이 어떻게 보면 힌트가 좀 되었다.

문제 조건을 보면, N, R, D가 각각 chosen independently and uniformly at random from~ 과 같은 제약사항이 있다.

따라서 랜덤의 upper-bound역시 랜덤이므로, 이 값들은 순서는 중구난방이겠지만, 결국은 계단과 같은 모양으로 나타나게 될 것이다. //(10^4//)개의 쿼리 값들을 알려주니 대충 아래와 같은 형식으로의 값들이 나타난다고 볼 수 있겠다.

 

rand() % 10

rand() % 20

rand() % 30

rand() % 40

...

rand() % 100

 

이렇게 되면 아무래도 맨 앞자리의 수가 1로 시작하는 수의 값이 맨 앞자리의 수가 2로 시작하는 녀석보다는 많을 것이고, 2로 시작하는 녀석은 3으로 시작하는 녀석보다 많을 것이고.. 와 같은 통계적 상관관계가 나타날 것이다.

이러한 점을 이용해서 가장 앞자리에 나타나는 알파뱃의 출연 빈도를 체크해서 내림차순으로 정렬하면 이 알파뱃들이 1부터 9의 숫자를 나타낼 것이다.

 

또한 0의 경우는 첫번째 자리에서만 나타날 수 없는 수이므로, 전체 나타난 알파뱃 중 맨 앞자리에 나타나는 알파뱃들을 빼면 나오게 될 것이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
#define NUMTC 10000
typedef pair<ll, string> pis;
typedef pair<ll, char> pic;
ll cnt[30];
void solve() {
	set<char> occurs;
	set<char> nonzero;
	occurs.clear();
	nonzero.clear();
	memset(cnt, 0, sizeof(cnt));
	int U;
	pis arr[NUMTC + 5];
	vector<pic> ans;
	ans.clear();
	char output[11];
	cin >> U;
	for (int i = 0; i < NUMTC; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	for (int i = 0; i < NUMTC; i++) {
		auto& s = arr[i].second;
		nonzero.insert(s[0]);
		//첫번째만 셈
		cnt[s[0] - 'A']++;
		for (char c : s) {
			occurs.insert(c);	
		}
	}
	for (int i = 0; i < 30; i++) {
		if (cnt[i]) {
			ans.push_back(make_pair(cnt[i], i + 'A'));
		}
	}
	for (auto c : nonzero) {
		occurs.erase(c);
	}
	char zero = *occurs.begin();
	sort(ans.begin(), ans.end(), greater<pic>());
	for (int i = 0; i < 9; i++) {
		output[i+1] = ans[i].second;
	}
	output[0] = zero;
	output[10] = 0;
	printf("%s\n", output);
	return;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

3. Oversized Pancake Choppers

이 문제는 고생을 꽤 했다. 마지막 문제 답게 난이도도 꽤 어려웠던 것 같은 느낌이다.

근데 사실 아이디어는 어느정도 생각을 해서 Middle TC는 맞출 수 있을 것 같았는데 한가지 조건을 빼 먹어서 업솔빙하면서도 많이 틀려먹었다.

 

결국 wwiiiii님의 코드를 참고한 뒤 힌트를 얻었다.

 

analysis를 보고 미들 TC를 맞추는 풀이까지만 적용해서 풀어보았다.

 

조각의 크기를 //(Ai//)중 하나로만 가능하다고 생각한 고정관념에 따라 틀려버렸는데, 조각의 크기는 //(Ai / k//)가 가능하고, 이때 //(k//)는 1과 //(D//)사이의 수가 된다.

analysis에서 Time Complexity가 //(O(D*N^2)//)라고 했을때, D가 왜 들어가나 이해를 못했는데 이것 때문이었다.

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 305
ll A[MAXN];
void solve() {
	ll N, D;
	cin >> N >> D;
	ll ans = D - 1;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
	// K를 perfect-cut 개수라고 하면 D - K가 정답이 된다.
	for (int i = 0; i < N; i++) {
		for (ll k = 1; k <= D; k++) {
			ll unit = A[i];// 조각의 크기는 unit / k이다.
			ll pieces = 0; //조각의 개수
			for (int j = 0; j < N; j++) {
				ll chunk = A[j];
				pieces += chunk * k / unit;
			}
			if (pieces < D) continue; //다 잘라도 이 조각 개수가 안나오는 경우 skip
			pieces = 0;
			int K = 0; // 모두 다 떨어지는 조각 개수
			for (int j = 0; j < N; j++) {
				ll chunk = A[j];
				ll add = chunk * k / unit;
				if ((chunk * k) % unit == 0 && pieces + add <= D) {
					pieces += add;
					K++;
				}
			}
			ans = min(ans, D - K);
		}
	}
	cout << ans << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

 

TC 3에 대한 솔루션 코드 업솔빙은 나중에 시간나면 해보도록 하겠다..... 나중에 스코어 보드를 보니, 한국인 참가자 중에서는 TC3를 맞춘 사람이 1명도 없었다. 코드를 보니 아이디어는 대충 비슷하게 구현은 한 것 같은데 다들 TLE가 나서 그런듯 하다.

 

TC3에 대한 심플한 솔루션 코드를 odh님이 작성하셨다. 참고해보면 좋을듯.