Google Code Jam 2021

오랜만에 써 보는 후기 글

Qualification Round

Rank 8381 / 42 points. 30점 통과로 다음 라운드 진출했다.

1번은 쉬운 문제였다.

2번은 DP로 했는데 그리디를 써도 잘 된다는 걸 나중에 알았다.

3번도 쉬운 문제 같았으나, 꼼꼼한 구현이 필요해 보였다. 어차피 3/4번 중 하나만 풀면 되어서 시도하지 않았다.

4번은 처음에 재밌는 문제라고 생각하고 짰다가 몇번 틀렸고, 알고 보니 지문을 잘못 읽었었다. 적당히 통과할 정도로만 풀고 넘어갔다.

5번은 뭐 뭔소리인지 모르겠네 알기 싫다.

Round 1A

당시 육군훈련소 군사훈련으로 불참;;

인터넷 편지로 1A 3번 문제를 보내 주신 분이 두 분 계셨다. 감사합니다. (__)

Round 1B

Rank 641 / 59 points. 1000등 안에 들어서 다음 라운드 진출했다.

1번 같은 건 왜 존재하는 걸까...

2번은 1번보다 쉬운 문제라고 생각했다. 답을 고정하면 그 답이 가능한 해인지를 판별할 수 있기 때문에, 모든 답 후보를 해 보면 된다. 답이 최대 $max(A, B) \times (\log \sum U)$ 이라고 가정해서 넉넉하게 401까지 돌렸고, 시스템 테스트에서 틀렸다. 나중에 풀이를 보니까 402가 최대라고 적혀있었다. 그래서 한 글자 고쳐서 다시 냈지만, 여전히 WA. 아마 다른 문제점이 있는 것 같다. 사실 내 논리에서는 400 근처의 수가 나올 수 없다. 뭔가 내가 아주 단단히 잘못 생각한 것 같으나, 깊게 알아보기는 귀찮아서 패스.

3번은 그냥 아무 그리디나 짰다. 대회 당시에는 2번 Large가 맞을 거라고 확신해서, 그냥 여기까지 하고 놀러 갔다.

Round 2

Rank 292 / 79 points. 1000등 안에 들어서 다음 라운드 진출했다.

1번은 쉬운 문제였다.

2번은 정수론 + DP였는데 약간 전형적인 유형이어서 빨리 풀었다.

3번은 $V_N$ 만 고정되었다면 제1종 스털링 수를 찾는 문제가 된다. 그래서 이런 저런 필요충분조건을 찾고 문제를 변환해 보았으나 잘 풀리지 않았다. 그렇게 찾을 때는 분할 정복 + FFT 같은 걸 끼얹을 각오로 했는데... R2 3번에서 그런 각오를 한 것 자체가 문제였던 것 같다. 쉽게 생각하면 쉽게 풀리는 문제였고 바로 못 찾은게 아쉬운듯. 어쨌든 Small을 긁고 잘 안 돼서 4번으로 넘어갔다.

4번은 BOJ 11493 동전 교환 과 비슷한 느낌의 괜찮은 MCMF 문제였다. 이것도 아무래도 전형적인 유형이어서, 무난하게 풀 수 있었다. 4번을 푼 이후에는, 굳이 3번까지 풀 필요는 없어 보여서 게임하러 갔다.

Round 3

Rank 19 / 70 points. 25등 안에 들어서 다음 라운드 진출했다.

몇달 만에 진지하게 친 대회라서 잘 할 수 있을까 걱정했는데 다행이도 잘 됐다. 2020년에 WF 첫 진출한 이후부터는 개인적인 한계를 돌파한 것 같아 만족스럽다.

사실 난 오프라인 라운드를 정말 가고 싶은데, 올해 코드잼도 당연하지만 온라인으로 진행한다. 아쉽지만 뭐 세상 일이 다 마음대로 되는 것은 아니니 내년을 기약해 보자.

1번은 포럼에 가니까 욕하는 사람들이 많던데 난 재미있는 문제라고 생각한다. 길이가 홀수일 때는, 두 숫자의 자릿수가 1 차이가 날 수밖에 없다. 이 경우에는 자릿수가 큰 쪽을 최소화하고, 작은 쪽을 최대화하면 되니, Greedy하게 할 수 있다. 짝수일 때는 Backtracking을 한다. 앞에서부터 채워나가는데, 만약 다른 수를 채웠다면, 그 시점부터는 백트래킹이 더 이상 필요 없고 홀수처럼 Greedy하게 할 수 있다. 같은 수를 채웠다면 계속 진행한다. 입력으로 들어온 수 중 같은 수를 두 개씩 짝지으면, 같은 수를 채운 케이스는 이 짝 중 하나를 사용한 케이스라고 볼 수 있다. 짝은 많아야 18개고, 이들 중 어떤 짝을 소비했는지만 중요하니, Bit DP하듯이 memoization하면 된다. 가장 쉬운 문제 치고 어려웠지만, 재미있는 관찰로 백트래킹을 깔끔하게 prune할 수 있다는 점이 흥미로웠다.

2번은 처음에 조합 탐색 같은 걸 생각해봤으나, 그 방법으로는 승산이 없어 보였다. 사각형 조건을 빼고 하면, Max flow 혹은 복잡한 Greedy로 해결할 수 있는 문제였다. 사각형 조건을 빼도 이렇게 어려운 문제인데, 심지어 추가되는 사각형 조건도 엄청나게 복잡하다. 복잡한 풀이에 복잡한 조건이 붙었으니 미친듯이 어려운 문제... 가 아니라, 오히려 두 조건이 너무 복잡하기 때문에, 인위적인 함정일 가능성이 높고, 그걸 파악하면 쉬워진다고 생각했다. (조금 더 논리적인 이유를 들자면, 사각형 조건이 없어도 Max flow 인데, Max flow 자체를 응용해서 할 수 있는 게 Cost 주는 거 말고는 없어서 풀이 선택지가 좁다고 느꼈다.)

일단 사각형이라는 조건 자체를, 다음과 같은 submatrix가 없는 조건으로 강화할 수 있다. 이 조건은 강한 조건이다. 사각형이 없는 올바른 답이더라도 이러한 submatrix가 존재할 수 있다. 앞의 사고 전개에 의해서, 믿음을 가지고 강하게 간 것이다.

/...\

.....

\.../

그래서 정말 Naive하게, 이러한 submatrix가 있으면 전부

\.../

.....

/...\

로 바꿔줬다. 이렇게 하더라도 카운트 자체에는 변화가 없기 때문에, 이 변환 자체는 항상 해 줄 수 있다.

고로, 저러한 submatrix가 존재하면 바꾸는 것을 계속 반복해 줬다. 무한 루프 없이 수렴한다는 것을 증명해야 하는데, 솔직히 하지 못했다. Small이 나왔고, 무한 루프가 안 돌 것 같아서, 믿음으로 제출했고 맞았다.

그리고 3번과 4번이 남았다. 1/2번에서 총 4번 틀려서 실수도 많이 하고, 이미 3/4번 Small을 한 20분 정도 안에 푼 사람들이 있었다. 그래서 AB + CD small (=55)는 기본이고, ABD (=70) 나 ABC + D small (=74) 에서 컷이 형성될 것이라고 생각했다. 두 개를 다 풀 필요는 아마 없겠지만 하나는 풀어야 하기 때문에 간을 잘 봐야 했다.

먼저 3번을 잡았는데 문제 자체가 너무 더럽고 풀기 싫게 생겨서 걱정이 되었다. 선이 하나만 있을 경우에는 이 선의 한 점을 기준으로 각도 정렬 후 Convex hull을 구하는 식으로 할 수 있으나, 이것 조차도 케이스가 있으니 두 개가 있을 때는 케이스를 줄이기가 쉽지 않을 거라고 생각했다. Small이 있으니 케이스를 못 줄이면 복잡도 면에서 손해를 보는 편이 나은데, 내가 생각한 풀이 방향은 $O(N \log N)$ 보다 느리게 구현한다고 그다지 간단해지지 않았다. 이 때 상당히 당황했다. 스코어보드 특성상 사람들이 지금 3번을 small만 푼 건지 둘 다 푼건지 알 수도 없고, 내가 무식해서 케이스가 많은 건지 그냥 어려운 건지도 알 수가 없다. 일단 진전 없이 패스.

4번도 이래저래 복잡한 문제였다. 4번은 Small부터 생각하는 게 좋을 것 같아서 일단 느린 풀이로 시작했다. 많이 알려진 테크닉이지만, 최댓값의 기댓값은 모든 $1 \le i \le m$ 에 대해 점수가 $i$ 점을 넘을 확률의 합이다. parametric search와 동일한 이치로, 점수가 $i$ 점 이상인지 아닌지를 구하는 문제는 보통 점수 최대화보다 쉽다. 이 문제도 예외는 아니다.

각 $2^N$ 개의 카드 부분 집합 중, Alice가 최적으로 결정했을 때 도달할 수 있는 카드 부분집합을 모두 찾자. 이건 게임 트리에서 바텀업 DP를 하면 된다. 점수가 $i$ 점 이상인 카드들이 Alice가 도달가능한 집합을 이룬다면, $i$ 점이 가능한 것이다. Alice가 도달 가능한 집합을 유효한 집합이라고 부르자. 각 유효한 집합에서, 집합 안은 모두 $i$ 점 이상이고 밖은 모두 $i$점 미만일 확률을 계산한 후 합하면 전체 문제가 해결된다. 이게 Small을 푸는 풀이이다.

Small을 푸는 풀이를 바로 Large로 확장할 좋은 방법은 떠오르지 않았다. 부분집합 열거만 잘 하면 되겠지만 $2^{32}$ 라서 애매하게 잘 안 됐다. 약간 어려운 문제 느낌이 나서, 3번으로 돌아가서 방황했다. 3번은 문제 자체에 Key idea랄게 없어서 구체화만 하면 되고, 4번은 idea가 없으니, 기본적으로 3번에 투자하고, 가끔씩 4번을 보는 전략을 택했다.

그런데 이 과정에서 3번의 구체화는 진전이 없었지만, 4번의 key idea는 떠올랐고 거기서 그대로 풀려버렸다.

내 Small의 시간 복잡도는 $O(2^N (2^L + M))$ 정도였는데, 일단 $M$ 을 떼는 것은, 구하는 식이 $2^L$ 차 다항식 $p(x)$ 를 $p(1) + p(2) \ldots + p(M)$ 까지 합한 식이기 때문에, 100개 항 정도를 계산한 후 interpolation하거나 Berlekamp-Massey를 사용하면 된다. 이건 Small 풀 때도 대충 이리 될거라 짐작을 하고 있었다.

어려운 부분은 $2^N$ 을 안 도는 것이다. 하지만 $N \le 32$ 이니 아예 다항시간까지 할 필요는 없고 지수부의 상수만 짤라줘도 된다. 2개 이상 나온 것들만 Brute force하고, 0번 나온 걸 따로 처리한다 (이건 쉬우니 생략), 그러면 $2^{N/2}$ 개의 가능성이 있고, 1개 등장한 항들에 대해서 잘 해결해 주면 된다. 우리가 유효한 집합에 대해서 관심있는 것은 그 내용이 아니라 크기 뿐이라는 것이다. 크기만 고정하면 확률 계산을 할 수 있기 때문이다. 이렇게 하면 게임 트리에서 앞서보다 조금 더 복잡한 DP를 하면 된다. $DP[v][w]= \{v$의 서브트리에서 $w$개의 한번 등장하는 원소를 골라서 현재 노드를 참으로 만드는 경우의 수$\}$ 라고 하면, 이 DP를 $4^L$ 에 계산할 수 있다 ($8^L$ 이 아니다.) 그렇게 하면 전체 문제가 해결된다. 그래서 구현했고 AC.

ABD를 푼 이후에는 15분이 남았고 C는 0점이었다. C를 Small만 풀어도 통과할 거라는 확신이 있었지만, 그러기에도 시간이 너무 없는 상황이었다. 그 사이에 딴짓도 하고 여러 방황을 했지만, 멘탈 잡고 차근차근, 정말 Small만 풀 수 있는 아주 간단한 풀이를 생각해보기로 했다. 그리고 위에서 했던 온갖 관찰과 구질구질한 케이스가 필요 없는 아주 나이브한 $O(N^3)$ 풀이를 생각했다, 그냥 지금 교차하는 현이 없으면 추가하는 걸 반복하는 풀이 -_- 그런데 이 때 5분 남아서 이걸 짜기도 너무 늦었었다. C 풀때 진작 생각했으면 안정적으로 진출했을 것 같지만... 하여튼 그 이후 조마조마하게 스코어보드를 기다렸다. 반쯤 체념하고 기다렸는데 의외로 D번을 푼 사람이 적고 C는 3명밖에 없어서 파이널 진출.