Google Code Jam 2019 Round1C 후기

결론만 말하자면, 820등으로 Round 2로 진출

 

Round 1에서 1 Solved로 떨어진 작년과 비교하면 발전이 있기는 했었다.

 

이번 라운드는 오후 6시부터 8시 반까지 진행되었는데, 8시 30분부터 불꽃 축재를 보러 가야하기 때문에 사실상 8시까지만 문제를 풀 수 있었다.

 

최대한 집중해서 문제를 풀었는데, 배점을 확인해서 난이도가 1 < 2 < 3 인것을 알고 1번부터 풀이를 시작했다.

 

- Robot Programming Strategy

문제를 읽어보고 토너먼트 방식이라는 점에 꽤나 복잡한 문제라고 생각해보았는데, 사실 모든 적들을 다 이길 수 있는 조합을 만들어 내면 된다.

 

Strategy가 끝에 다달으면 다시 Cyclic하게 순환된다는 점에 유의해야 한다. Brute-Force로 Visible만 풀려고 했는데, 생각보다 N값이 작아서 Hidden 도 풀렸다.

 

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

set<string> enemy;
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		int A;
		cin >> A;
		enemy.clear();
		string ans = "";
		bool ok = true;
		for (int i = 0; i < A; i++) {
			string s; cin >> s;
			enemy.insert(s);
		}
		for (int i = 0; i < 500; i++) {
			int R, S, P;
			R = S = P = 0;
			for (auto s : enemy) {
				char c = s[i % (int)s.length()];
				if (c == 'R') R++;
				else if (c == 'S') S++;
				else if (c == 'P') P++;
			}
			int C = 0;
			C += R > 0 ? 1 : 0;
			C += S > 0 ? 1 : 0;
			C += P > 0 ? 1 : 0;
			if (C == 3) {
				ok = false;
				break;
			}
			else if (C == 1) {
				if (R) ans += "P"; //바위에는 보
				else if (S) ans += "R"; //가위에는 바위
				else ans += "S"; //보에는 가위
				break;
			}
			else {
				//vector<string> victim;
				if (R == 0) { //보와 가위
					ans += "S";
					//i번째에 P인놈들 삭제
					for (auto s : enemy) {
						char c = s[i % (int)s.length()];
						if (c == 'P') {
						    enemy.erase(s);
							//victim.push_back(s);
						}
					}
				}
				else if (S == 0) {
					ans += "P"; //바위와 보
					//i번째에 R인놈들 삭제
					for (auto s : enemy) {
						char c = s[i % (int)s.length()];
						if (c == 'R') {
						    enemy.erase(s);
							//victim.push_back(s);
						}
					}
				}
				else if (P == 0) {
					ans += "R"; //가위와 바위
					//i번째에 S인놈들 삭제
					for (auto s : enemy) {
						char c = s[i % (int)s.length()];
						if (c == 'S') {
						    enemy.erase(s);
							//victim.push_back(s);
						}
					}
				}
				//for (auto s : victim) {
				//	enemy.erase(s);
				//}
				//victim.clear();
			}
		}

		printf("Case #%d: %s\n", t, ok == false ? "IMPOSSIBLE" : ans.c_str());
	}
}

 

- Power Arrangers

Permutation 순열 관련된 문제였다. 백준에서 K-번째 시리즈를 풀이하면서 대충 풀이가 영감이 왔는데 풀이는 다음과 같다.

나타난 순열들의 첫번째 글자들이 나타난 횟수를 모두 센다 -> 다 4!번(24) 나타나고 하나만 23번 나타난다. 그러면 23번 나타난 녀석이 첫번째 글자다.

 

23번 나타난 녀석들을 다시 확인해보면 나머지는 다 3!번(6) 나타나고 하나는 5번 나타난다. 그러면 두번째 글자를 알아낼 수 있다.

 

6번 나타난 녀석은 나머지는 2!번(2) 나타나고, 하나는 1번 나타난다. 세번째 글자는 1번 나타난 녀석이다.

 

마지막에는 1번 나타나게 되는데, 0번 나타난 녀석이 4번째 글자고 남는녀석이 5번째 글자가 된다.

 

Python으로 작성해보려다가 답답해서 다시 C++로 작성했다. Visible만 맞추고 갈려고 했는데 Hidden 도 맞는 솔루션이었다.

 

디버깅이 까다로웟는데, 파일 입출력으로 로그를 찍어서 확인하면서 디버깅했다.

 

#include <bits/stdc++.h>
using namespace std;
int value[] = {23, 5, 1, 0};
#define endl '\n'
int main() {
	// ofstream fout("output.txt");
	int T, F;
	setbuf(stdout, NULL);
	setbuf(stdin, NULL);
	cin >> T >> F;
	
	for (int t=1; t<=T; t++) {
		set<int> left;
		left.clear();
		left.insert(0);
		left.insert(1);
		left.insert(2);
		left.insert(3);
		left.insert(4);
		vector<int> index[5];
		vector<int> ans;
		int cnt[5];
		ans.clear();
		memset(cnt, 0, sizeof(cnt));
		for (int i=0; i < 5; i++) index[i].clear();
		
		for (int i=1; i <=595; i+=5) {
			cout << i << endl;
			string s;
			cin >> s;
			char c = s[0];
			cnt[c-'A']++;
			index[c-'A'].push_back(i);
		}
		int idx = 0;
		for (int i=0; i < 5; i++) {
			if (cnt[i] == value[0]) {
				idx = i;
				break;
			}
		}
		// fout << "CNT = {" << cnt[0] << "," << cnt[1] << "," << cnt[2] << "," <<cnt[3] << "," <<cnt[4] << "}" << endl;
		ans.push_back(idx);
		left.erase(idx);
		// fout << idx << endl;
		vector<int> next;
	
		for (int kk = 1; kk <4; kk++) {
			next.clear();
			for (int q : index[idx]) {
				next.push_back(q+1);
			}
			memset(cnt, 0, sizeof(cnt));
			for (int i=0; i < 5; i++) index[i].clear();

			for (auto i : next) {
				cout << i << endl;
				string s;
				cin >> s;
				// if (kk == 2) {
				// 	fout << "query = " << i << endl;
				// 	fout << s << endl;
				// }
				char c = s[0];
				cnt[c-'A']++;
				index[c-'A'].push_back(i);
			}
			
			for (int i=0; i < 5; i++) {
				if (cnt[i] == value[kk] && left.find(i) != left.end()) {
					idx = i;
					break;
				}
			}
			ans.push_back(idx);
			left.erase(idx);
			// fout << "IDX = " << idx << endl;
			
			// fout << "CNT = {" << cnt[0] << "," << cnt[1] << "," << cnt[2] << "," <<cnt[3] << "," <<cnt[4] << "}" << endl;
		}
		if (left.size() == 1) {
			for (auto v : left) {
				ans.push_back(v);
			}
		}
		//ans.push_back(10 - ss);
		
		string ans_str = "";
		for (int a : ans) {
			ans_str += (char)(a + 'A');
		}
		
		cout << ans_str << endl;
		string res;
		cin >> res;
		if (res[0] == 'N') return 0;
	}
}

 

2번문제까지 풀이하고 나니 8시 10분정도 되어서 곧바로 부리나케 뛰쳐나갔다.

 

3번문제는 대회때는 문제도 읽지 못한 셈. 나중에 3번 문제도 풀어보도록 하겠다.