2020년 구글 코드잼 Qualification 라운드 후기 글이다.
이번에는 총 5문제가 나왔고, TC set이 1개짜리부터 3개짜리까지 다양하게 있었다.
결과만 말하자면 4번째 문제 Hidden set과 5번째 문제 Hidden set 빼고는 다 풀었다.
등수는 4769등인데, 이 추세로는 Round 2도 못갈듯하다. 올해 참가자가 역대 최대라는 이야기가 있던데, 올해 목표인 코드잼 티셔츠 받기는 힘들것 같기도 하다 ㅠㅠ
4번문제 Hidden Set은 Solution은 이미 생각해서 짰는데, 버그 하나때문에 날려먹은 케이스이다.
끝나고 나서 다시 디버그 해서 풀어보니 잘 맞았었는데 애석한 상황이다.
끝나고 나서 맞은 상황이다. Interactive Problem이라서 디버깅 환경 구축하는 것도 꽤 귀찮고 했었다.
일단 푼 문제들 간단하게 리뷰를 해보자.
1. Vestigium (7pt)
첫번째 문제 답게 매우 쉬웠던걸로 기억한다. Latin square matrix라고 각 오와 열에 1부터 N까지의 수가 1번씩만 나타나는 녀석에서 왼쪽위부터 오른쪽아래로 되는 대각선의 값들의 합이 trace라고 하는데 임의의 matrix가 주어질 때, 이 trace를 구하고, Latin square rule을 위반하는 row와 column의 수를 출력하면 되는 그런문제이다.
하나하나 다 따라가면서 체크하면 답이 나온다. 문제 이해하는데 시간을 더 쓴 것 같다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int trace = 0, duprow = 0, dupcol = 0;
int matrix[105][105];
int n;
cin >> n;
int check[105];
for (int i = 0; i < n; i++) {
memset(check, 0, sizeof(check));
for (int j = 0; j < n; j++) {
int v;
cin >> v;
matrix[i][j] = v;
check[v]++;
if (i == j) trace += v;
}
int correct = 0;
for (int i = 1; i <= n; i++) {
if (check[i] == 1) correct++;
}
if (correct != n) {
duprow++;
}
}
for (int i = 0; i < n; i++) {
memset(check, 0, sizeof(check));
for (int j = 0; j < n; j++) {
int& v = matrix[j][i];
check[v]++;
}
int correct = 0;
for (int i = 1; i <= n; i++) {
if (check[i] == 1) correct++;
}
if (correct != n) {
dupcol++;
}
}
cout << trace << ' ' << duprow << ' ' << dupcol << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}2. Nesting Depth (5pts, 11pts)
문자열 다루는 문제 같은 문제인데, 숫자가 나오면, 각각의 숫자는 자신을 둘러싼 괄호가 자신의 숫자만큼 나와야 한다. Greedy하게 이전 숫자보다 큰 숫자가 나오면 여는 괄호를 더 열어주고, 더 작은 숫자가 나오면 닫아주고, 마지막에 다 닫아주면 된다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
string s;
string ans = "";
cin >> s;
//int opened = 0;
int prev = 0;
for (char c : s) {
int cur = c - '0';
if (cur > prev) {
int diff = cur - prev;
//diff만큼 더 연다
for (int i = 0; i < diff; i++) {
ans += "(";
}
}
else if (cur < prev) {
int diff = prev - cur;
for (int i = 0; i < diff; i++) {
ans += ")";
}
}
prev = cur;
ans += c;
}
if (prev > 0) {
while (prev--) {
ans += ")";
}
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}
3. Parenting Partnering Returns(7pts, 12pts)
부모 두명이서 아기 돌보는 스케쥴?을 각자 스케쥴링 하는데, 가능하게 스케쥴링 하면 되는 문제이다. 각각 task가 시작하는 시간 기준으로 정렬을 한 뒤, 그리디하게 지금 일 가능한 녀석들을 스케쥴링 해주면 된다.
소팅하기 전에 원래 Index 기준으로 답을 입력해야 하는 것을 깜빡해서 한번 WA를 받았다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
string mark[2] = { "C", "J" };
void solve() {
int fins[2];
fins[0] = fins[1] = 0;
int resp[1005];
memset(resp, -1, sizeof(resp));
int n;
vector<pair<pii, int>> tasks;
tasks.clear();
cin >> n;
for (int i = 0; i < n; i++) {
int s, e;
cin >> s >> e;
tasks.push_back(make_pair(make_pair(s, e), i));
}
sort(tasks.begin(), tasks.end());
for (auto task : tasks) {
bool alloced = false;
for (int candid = 0; candid < 2; candid++) {
if (fins[candid] <= task.first.first) {
fins[candid] = task.first.second;
//ans += mark[candid];
resp[task.second] = candid;
alloced = true;
break;
}
}
if (alloced == false) {
cout << "IMPOSSIBLE" << endl;
return;
}
}
string ans = "";
for (int i = 0; i < n; i++) {
ans += mark[resp[i]];
}
cout << ans << endl;
}
int main() {
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}4. ESAb ATAd(1pt, 9pts, 16pts)
interactive 문제이다. 오랜만에 interactive 문제를 봐서 환경 구축도 귀찮았다. 일단 interactive_runner.py랑 judge.py를 코드잼측에서 제공을 해준다.
두 녀석들 다 받은 뒤, 내가 짠 코드 바이너리가 ps.exe라고 할때 다음과 같이 명령어를 수행하면 test가 가능하다.
$ python3 interactive_runner.py python3 judge.py 0 -- ps.exeinteractive_runner.py는 -- 기준으로 왼쪽에 있는 command와 오른쪽에 있는 command를 각각 쓰레드로 실행시킨 뒤, stdin/stdout를 각각 연결해주는 역할을 한다.
python3 judge.py 0라고 실행하면 서버가 어떻게 응답하는지를 확인해볼 수 있다. 0을 인자로 넣으면 1번째 test set(b=10)이 나오고, 1를 인자로 넣으면 2번째 test set(b=20)이 적용된다.
맨처음에 문제 내용을 이해하는데에도 꽤나 오래걸렸었다. 문제를 잘 이해못하고 테스팅 툴을 이해못해서, 파이썬 코드를 뜯어서 분석해 보기도 했었다.
문제 내용을 대충 설명해보자면, B bit의 임의의 수를 서버에서 지정한다. 이 값을 우리가 맞추면 되는데, 최대 150번의 쿼리가 가능하다. 각 쿼리를 하기 위해서 1~B에 해당하는 정수 하나를 보내면 그 쿼리 번째 bit값을 리턴해준다. 근데 10번 요청을 할 때 마다 서버에 저장된 B bit가 랜덤한 확률로 값이 바뀌게 된다. 50%확률로 Negation 연산이 일어나고(1이 0이 되고, 0이 1이 된다), 50%확률로 Reverse 연산이 일어나서 1번 비트가 B번 비트로, 2번 비트가 B-1번 비트가 되고 이런식으로 바뀌게 된다.
따라서 25%확률로 Negation만 일어나고 25%확률로 Reverse만 일어나고 25%확률로 Negation과 Reverse가 동시에 일어나고, 25%확률로 아무일도 안일어난다.
서버에 저장된 bit를 맞추는 것은 Negation, Reverse가 일어난것을 다 쳐서, 답을 맞추는 시점에 맞는 bit이기만 하면 정답처리가 된다. 그리고 정답을 제출하는 것은 Query로 안친다고 한다.
1번째 test set는 각 비트별로 값을 한번씩 다 물어본 뒤 이어서 응답을 주면 풀린다. 10번 쿼리를 했지만, 답변하는 것은 쿼리가 아니므로 비트 변조가 안일어난 상태이다.
2번째만을 위한 답 코드 말고 3번째에도 해당되는 솔루션을 생각했는데 대략 다음과 같다.
일단 bit값들을 앞에서부터 5개, 뒤에서부터 5개씩 해서 10개씩 받는다. 그러면 그 10개의 뭉치는 바뀌어도 같은 시점에 바뀌기 때문에 초기 값은 같은그룹들을 모을 수 있다.
첫번째 그룹은 [1~5]비트와 [96~100] 비트가 된다. 두번째 그룹은 [6~10]비트와 [91~95]비트가 된다.
같은 그룹끼리는 Reverse가 되어도 같은 그룹끼리 바뀌게 되므로 같이 움직인다고 볼 수 있다.
그러면 여기서 1번 비트와 해당하는 100번 비트가 둘다 같은 숫자이면 Reverse되어도 그대로이다. 그리고 1번 비트와 100번 비트가 서로 다른 숫자라면 Negation되어도 Reverse되는 것과 같은 효과가 난다.
이러한 점을 이용해서 같은 그룹내에 대칭인 bit와 아닌 bit가 둘 다 있다면, 이 2개의 비트를 확인해서 Negation이 되었는지 Reverse가 되었는지를 확인할 수 있다.
그리고 만약 한 그룹이 모두 대칭인 수로만 이루어져 있거나, 모두 비대칭인 수로만 이루어져 있다면 더욱 쉽다. 대칭인 수로만 이루어져 있으면 Neg만 확인하면 되고, 비대칭인 수로만 이루어져 있으면 Rev랑 Neg랑 동일하게 칠 수 있다.
이를 이용해서 그룹의 수를 모두 알아내고(100번의 쿼리로), 각각 그룹 별 Neg랑 Rev가 일어났는지를 체크를 한다. 각각 그룹당 2번 이하의 쿼리로 일어났는지를 확인할 수 있으므로 10번의 쿼리마다 5개의 그룹을 확인할 수 있다. 그리고 10번의 쿼리가 일어난 뒤는 Bit fliping이 어떻게 일어났는지 알기 위해서 기준이 되는 그룹을 하나 두고(이 그룹은 비대칭과 대칭이 둘다 있어야지 Rev와 Neg를 둘다 확인가능) 그녀석으로 체크를 한다.
그래서 10번의 쿼리마다 최소 4개의 그룹의 상태를 확인가능하다.
그러면 130번 쿼리 내에 모든 그룹의 상태를 확인할 수 있다.
디버깅 할때에는 query 함수를 디버깅용 서버 상태를 알려주는 녀석으로 만들어서 했다.
모두 대칭이거나 비대칭인 경우의 체크를 조금 잘못해서 3번째 set에서 틀리긴 했었는데 고쳐서 이제는 모두 정답이 나온다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define TOTAL_BIT_NUM 105
#define GROUP_NUM 12
int tc, n;
int bits[TOTAL_BIT_NUM];
int mirror[TOTAL_BIT_NUM];
int mirror_cnt[GROUP_NUM];
int neged[GROUP_NUM];
int reved[GROUP_NUM];
int g_neged, g_reved;
void solve10() {
for (int t = 1; t <= tc; t++) {
string ans = "";
for (int i = 1; i <= n; i++) {
cout << i << endl;
cout.flush();
string s;
cin >> s;
ans += s[0];
}
cout << ans << endl;
cout.flush();
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
}
pii get_canary(int gnum) {
int neg_canary, rev_canary;
neg_canary = rev_canary = -1;
for (int i = gnum * 5; i < gnum * 5 + 5; i++) {
if (mirror[i] && neg_canary == -1) {
neg_canary = i; //rev 되도 변하지 않음
}
if (!mirror[i] && rev_canary == -1) {
rev_canary = i; //rev 되면 변함
}
}
return make_pair(neg_canary + 1, rev_canary + 1);
}
//debug
/*
int samples[] = {0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1 };
int query(int pos) {
static int count = 0;
int ret = samples[pos - 1];
count++;
if (count == 10) {
cout << "---------------------------------------" << endl;
count = 0;
if (rand() % 2 == 0) {
cout << "Negation !!!" << endl;
for (int i = 0; i < 100; i++) {
samples[i] ^= 1;
}
}
if (rand() % 2 == 0) {
cout << "Reversed !!!" << endl;
for (int i = 0; i < 50; i++) {
swap(samples[i], samples[99 - i]);
}
}
cout << "---------------------------------------" << endl;
}
return ret;
}
*/
int query(int pos) {
cout << pos << endl;
cout.flush();
int ret;
cin >> ret;
return ret;
}
void solve_large() {
while (tc--) {
//입력받기
memset(bits, -1, sizeof(bits));
memset(mirror, 0, sizeof(mirror));
memset(mirror_cnt, 0, sizeof(mirror_cnt));
memset(neged, -1, sizeof(neged));
memset(reved, -1, sizeof(reved));
g_neged = g_reved = 0;
for (int i = 0; i < n / 10; i++) {
// [i*5+1, i*5+5]이랑 [n-5*i-4, n-5*i]
//10개씩 뭉텅이로 받되, 앞에서부터 5개, 뒤에서부터 5개가 하나의 셋트이다.
//앞에서부터 5개
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] = query(j + 1);
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] = query(j + 1);
}
}
//base group를 찾는다.
//base는 palindrome한 쌍과 palindrome 아닌 것 값 하나를 알아내면 된다.
//팰린드롬은 complement 연산을 했는지를 확인하는 용도이다.
//palindrome아닌 것은 reverse연산을 했는지 확인하는 용도이다.
//base 그룹은 mirror_cnt가 1~4 사이의 값이다.
for (int i = 0; i < n / 2; i++) {
int j = n - i - 1;
if (bits[i] == bits[j]) {
mirror[i] = mirror[j] = 1;
mirror_cnt[i / 5]++; //해당 그룹에 palindrome 인 수 개수.
}
}
// mirror_cnt가 5인 그룹에는 rev 연산이 무의미함
// mirror_cnt가 0인 그룹은 rev 연산과 neg 연산이 같다.
int base_gnum = -1;
for (int i = 0; i < n / 10; i++) {
if (mirror_cnt[i] > 0 && mirror_cnt[i] < 5) {
base_gnum = i;
break;
}
}
if (base_gnum == -1) {
//모든 그룹이 palindrome이거나 그 반대인경우
//neg만 체크하면 된다.
for (int i = 0; i < n / 10; i++) {
int k = i * 5 + 1;
int res;
res = query(k);
if (bits[k - 1] != res) {
//real time negation
//앞에서부터 5개
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] ^= 1;
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] ^= 1;
}
}
}
string s = "";
for (int i = 0; i < n; i++) {
if (bits[i]) {
s += "1";
}
else {
s += "0";
}
}
cout << s << endl;
cout.flush();
//get response
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
else {
//일반적인 섞여있는 경우
pii base_canary = get_canary(base_gnum); // {neg, reg}
int query_left = 8;
if (query(base_canary.first) != bits[base_canary.first - 1]) {
neged[base_gnum] = 1;
}
else {
neged[base_gnum] = 0;
}
if (query(base_canary.second) != (bits[base_canary.second - 1] ^ neged[base_gnum])) {
reved[base_gnum] = 1;
}
else {
reved[base_gnum] = 0;
}
(void)0;
for (int i = 0; i < n / 10; i++) {
if (i == base_gnum) continue; //base 그룹은 미리 구해놨으므로 안구해도 된다.
if (query_left < 2) {
if (query_left == 1) query(1);
query_left = 8;
if (query(base_canary.first) != (bits[base_canary.first - 1] ^ neged[base_gnum] ^ g_neged)) {
g_neged ^= 1;
}
if (query(base_canary.second) != (bits[base_canary.second - 1] ^ neged[base_gnum] ^ reved[base_gnum] ^ g_neged ^ g_reved)) {
g_reved ^= 1;
}
}
if (mirror_cnt[i] > 0 && mirror_cnt[i] < 5) {
pii canary = get_canary(i);
query_left -= 2;
if (query(canary.first) != (bits[canary.first - 1] ^ g_neged)) {
neged[i] = 1;
}
else {
neged[i] = 0;
}
if (query(canary.second) != (bits[canary.second - 1] ^ g_neged ^ g_reved ^ neged[i])) {
reved[i] = 1;
}
else {
reved[i] = 0;
}
}
else {
query_left--;
if (query(i * 5 + 1) != ((bits[i * 5] ^ g_neged) ^ (mirror_cnt[i] == 0 ? g_reved : 0))) {
neged[i] = 1;
}
else {
neged[i] = 0;
}
reved[i] = 0;
}
}
//apply answers
for (int i = 0; i < n / 10; i++) {
int cneged = (g_neged ^ neged[i]);
int creved = (g_reved ^ reved[i]);
if (cneged) {
for (int j = i * 5; j < i * 5 + 5; j++) {
bits[j] ^= 1;
}
//뒤에서부터 5개
for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
bits[j] ^= 1;
}
}
if (creved) {
for (int j = i * 5; j < i * 5 + 5; j++) {
int k = n - j - 1;
swap(bits[j], bits[k]);
}
}
}
string s = "";
for (int i = 0; i < n; i++) {
if (bits[i]) s += "1";
else s += "0";
}
cout << s << endl;
cout.flush();
string res;
cin >> res;
if (res[0] == 'N') exit(1);
}
}
return;
}
int main() {
cin >> tc >> n;
if (n == 10) {
solve10();
}
else {
solve_large();
}
}
5. Indicium(7pts, 25pts)
마지막 문제인데, Small tc만 풀이법을 알겠고, large는 모르겠다.
원하는 Trace에 해당하는 Latin square matrix를 찾거나, 불가능하다고 말해줘야하는 그런 문제이다.
Backtracking으로 풀 수 있고, 특정 K값을 트레이스로 갖는지 알아야 한다.
만약 K가 주어지면, 1~N의 범위의 수 N개의 합으로 K를 만들 수 있는 조합들을 구해본다.
그리고 그 조합들의 수로 대각선으로 나열한 뒤, 남은 칸에다가 수를 채워서 Latin square matrix를 만들 수 있는지만 확인하면 된다.
이때 만약 수 조합이 1 2 2 3 4 라는 조합으로 12라는게 되는지 확인해야 할 때, 순서는 중요치 않다는 것을 알 수 있는데, 이때 하나의 성질을 활용하면 된다.
즉 1 2 2 3 4로 Latin square 매트릭스를 만들 수 있으면 1 3 4 2 2 로도 만들 수 있는데, Latin square matrix는 행 단위로 순서를 바꾸거나 열 단위로 서로 순서를 바꾸어도 Latin square matrix이다. 왜 그런지는 조금만 생각해보면 알 수 있다.
따라서 조합별로 가능한 라틴 스퀘어 매트릭스가 있는지를 다 체크해보면 Small tc는 맞출 수 있다.
Large tc는 이분매칭을 쓴다는 것 같은데, 나중에 다시 공부해봐야 겠다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
int n, k;
//n개의 숫자(1~n) 합으로 k를 만드는 경우의 수를 다 만들어야한다.
int val[6];
struct Chunk {
int v[5];
};
vector<Chunk> comb[26];
void dfs(int offset) {
if (offset <= n) {
for (int i = val[offset - 1]; i <= n; i++) {
val[offset] = i;
dfs(offset + 1);
}
}
else {
Chunk chunk;
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += val[i];
chunk.v[i - 1] = val[i];
}
comb[sum].push_back(chunk);
}
}
int row[5], col[5];
int field[5][5];
bool backtrack(int i, int j) {
if (i >= n) {
//모두 성공한 경우
cout << "POSSIBLE\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << field[i][j] << ' ';
}
cout << endl;
}
return true;
}
if (j >= n) {
//다음줄로 이동
return backtrack(i + 1, 0);
}
if (field[i][j] != -1) {
//이미 지정된 경우(diagonal)
return backtrack(i, j + 1);
}
for (int v = 1; v <= n; v++) {
if (((row[i] & (1 << v)) == 0 && (col[j] & (1 << v)) == 0)) {
//set
field[i][j] = v;
row[i] |= (1 << v);
col[j] |= (1 << v);
//search
if (backtrack(i, j + 1)) {
return true;
}
//unset
row[i] &= (~(1 << v));
col[j] &= (~(1 << v));
field[i][j] = -1;
}
}
return false;
}
void solve() {
cin >> n >> k;
for (int i = n; i <= n * n; i++) {
comb[i].clear();
}
//n에 대한 가능한 모든 숫자 조합들을 만들어냄
dfs(1);
for (int i = 0; i < comb[k].size(); i++) {
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(field, -1, sizeof(field));
for (int j = 0; j < n; j++) {
int v = comb[k][i].v[j];
field[j][j] = v;
row[j] |= (1 << v);
col[j] |= (1 << v);
}
if (backtrack(0, 0)) return;
}
cout << "IMPOSSIBLE\n";
return;
}
int main() {
val[0] = 1;
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
printf("Case #%d: ", t);
solve();
}
}'알고리즘 & Problem Solving' 카테고리의 다른 글
| Google Codejam Kickstart 2020 Round 1-C 후기 (0) | 2020.05.06 |
|---|---|
| Google Codejam Kickstart 2020 Round B 후기 (0) | 2020.04.22 |
| Google Kickstart Round A 2020 풀어보기 (0) | 2020.03.31 |
| 백준 1854번 K번째 최단경로 찾기 문제 풀이 (0) | 2020.02.26 |
| 백준 1753번 문제 '최단경로' 풀이 (0) | 2020.02.26 |