(팀연습) ACM-ICPC 2018 Daejeon Regional

그간 2번의 팀연습을 더 거쳤으나... absolving을 제대로 하지 못했다. 1주일 12문제도 생각보다 많이 빡세다는 것을 느끼게 되었다.

아무튼 그동안 많은 일이 있었는데, 7월 27일의 예선을 가볍게 진출한 후, 이제 본선을 앞두고 마지막 팀연습을 하게 되었다.

약간 늦게 만나고 노트북 세팅도 상당히 오래 걸린지라, 5시간짜리 문제셋을 골라 2시간 정도 하다가 그냥 가기로 했다.

문제셋은 뭐를 할까 고민하다가, 우리 실력이 어느 정도 되는지도 볼 겸 2018 ACM-ICPC Daejeon Regional을 하기로 했다.

codeforces에 GYM 탭에서 virtual round를 진행할 수 있었는데, 놀랍게도 그 때 대회를 진행했던 사람들의 데이터도 그대로 들어있다.

작년 VISSLLE 팀도 잘 보존되어 있다.. 반갑다 ㅠㅠ

자세히 살펴보니 status도 WA, RTE같은게 아닌 그냥 Rejected이고 제출 시간도 다 n분 00초인 것을 보아 그냥 스코어보드를 보고 역추적을 한 것이 아닌가 생각된다.

아무쪼록, 덕분에 대회 환경과 완전히 동일한 환경에서 문제풀이를 진행할 수 있었다. 갓드포스에 다시 한 번 감사한다. (백준도 빨리 virtual contest 만들길..)

결과

엄청 잘 풀었다!

문제셋이 쉬운 편이었지만, 본선 8솔브는 확실히 많이 푼 게 맞다.

만약 이 팀 그대로 참가를 했더라면, 본선 87개 팀 중 18등의 성적을 거두었을 것이다.

타임라인

오후 3시 50분~오후 5시 10분: 노트북 세팅

토요일에 열리는 본선을 대비하여 노트북을 세팅했다. 이번 팀연습도 마찬가지로 노트북 1대로 진행했다.

한 명은 sublime text를 쓰고, 한 명은 vim을, 한 명은 vs code를 쓰기 때문에 설정할 게 조금 많았지만 의외로 서로 충돌도 안나고 좋았다.

나는 A~D번, N군은 E~H번, D군은 I~L번을 하기로 분배했다.

0:06 D. Happy Number

A번은 보고 바로 넘기고, B번은 보고 어 쉽네 생각하며 풀까 고민했는데 D가 뭔가 쉬워보여서 잠깐 읽었더니 엄청난 꿀문제.

숫자가 1에 도달하는지, 1이 아닌 사이클에 도달하는지만 확인해주면 된다.

중간에 인터넷이 끊겨서 제출이 약간 늦었다.

0:41 B. Connect3

이후 쉽다고 생각한 B번 구현에 들어갔는데 구현이 생각보다 약간 하드코딩이었다.

b = 1일 때 예외라고 생각해서 예외처리를 해줬다가 한 번 틀렸는데, 코드를 프린트(폰으로 옮겨서 보기...)하고 D군에게 넘겨줬다. 이후 수정해서 AC.

B번은 전형적인 백트래킹 문제로 기둥 4개에 테트리스 마냥 돌을 넣어서, 3개를 연속하도록 만들면 이기는데 주어진 좌표에서 끝나는 winning position의 갯수를 구하는 문제이다. 총 16칸에 빈 것, A, B 3가지 상태가 존재하므로 2 * 16 = 32비트에 한 상태를 표현할 수 있다. 모든 경우를 따져가며 조건에 맞는 position일 때 set에 넣어주면 간편하다.

0:50 K. Untangling Chain

이 사이 D군이 가볍게 해결. 그리드에서 선이 주어지는데, 선의 방향은 그대로 유지한 채 선이 서로 겹치지 않도록 길이를 잘 바꾸어주어야 한다.

이런 문제의 풀이 방법은 여러 가지가 있을 수 있는데, 나는 꺾을 때마다 왼쪽/오른쪽에 선이 각각 어디까지 있는지 구하고 선이 없는 곳까지 이동해 준 것 같다.

1:05 C. Game Map

이 사이 나는 스코어보드를 보고 C번이 엄청난 꿀문제라는 것을 알고 컴퓨터를 다시 받았다. 사실 B번을 잡기 전에 C번을 먼저 잡았어야 하지만 C번이 스코어보드에 뜰 때쯤에는 B번이 80%정도 구현되어 있었으므로 어쩔 수 없는 것 같다.

문제는 neighboring node의 갯수가 증가하도록 경로를 최대 얼마나 길게 잡을 수 있냐는 문제인데, 갯수 기준으로 정렬하고 뒤에서부터 차근차근 업데이트하면 된다.

1:49 L. Vacation Plans

이 사이 D군이 다시 L번을 잡고, 파워 코딩을 한 뒤 제출하고 WA.

아 밥먹으러 가자~ 하고 3명이서 사이좋게 학식을 먹으러 갔다.

학식을 먹으면서 D군이 폰으로 코드를 좀 보다가 수정해서 제출, WA. 다시 수정해서 제출, AC!!

밥을 먹으면서 순위가 올라가는 팀이 있다?! 푸슝푸슝

L번은 상당히 까다로운 문제에 속하는데, 풀이는 추후 업데이트해야겠다.

이후 N군이 G번을 구현하며 고통받고 있을 때, F번과 I번 솔루션까지 다 나왔다.

결국 N군이 고통을 견디지 못하고 잠들게 되었다. 그래서 일단 F를 먼저 풀었다.

3:23 F. Philosopher’s Walk

아주 헷갈리는 구현 문제. 한 변의 길이 n이 주어질 때, $n^2 / 4$마다 구간이 달라지므로 구간을 반영해서 회전과 대칭을 "잘" 고려하며 재귀적으로 코드를 짜면 된다.

4:18 G. Rectilinear Regions

잠든 N군을 뒤로하고 D군이 마침내 AC. 문제는 그리 어렵지는 않은데, 라인 스위핑 느낌으로 쭉 훑으면서 넓이를 잘 더해주면 된다.

약간 까다로운 케이스가 몇 가지 있는데, 이것 또한 잘 처리할 수 있도록 코드를 잘 작성해주면 된다.

4:54 I. Slot Machines

어려운 문제였지만 풀어내서 기뻤다. 4시간이 지나가니 다들 상태가 안 좋아져서 꽤 간단한 코드임에도 불구하고 디버깅을 참 오랫동안 했다.

결국 30분을 남기고 갓-D군이 작은 케이스에 대해 brute force 코드를 짜서 출력을 비교해보았는데, 우연히도 brute force 출력이 잘못 나온 케이스에서 내 풀이도 잘못 나와서 틀린 점을 발견하고, 5분을 남기고 AC를 받을 수 있게 되었다. 틀린 이유는 길이 1일 때 while문에서 break를 넣지 않았기 때문...

정해는 아닌 것 같지만, 해싱을 이용해서 풀었다. 풀이는 다음과 같다.

먼저 반복 길이 p = 1일 때, 최소의 k값을 찾는다.

다음부터, 반복 길이 p를 1씩 늘려가며 찾기를 반복하는데, 기존의 p + k의 최솟값을 t라 하면 문자열이 최소 t - p - 1번 인덱스부터는 사이클을 이루어야 t보다 더 작은 값을 얻을수 있음을 알 수 있다. t - p - 1번 인덱스 이후의 부분이 사이클을 이루는지는 길이 p씩 끊어서 같은지 비교함으로써 빠르게 알 수 있다. time complexity는 대략 harmonic series를 이루는데, $O(n\log{n})$ 정도이다.

t - p - 1번 인덱스 이후가 같다면, 이제 그 앞을 하나하나 비교해보면 되는데, 비교할 때마다 t값이 1씩 줄어드므로 이 과정은 최대 $O(n)$번 시행된다.

정해는 KMP 알고리즘을 이용하는 것 같은데, KMP 알고리즘은 그간 배운 많은 알고리즘 중에서 정말 유일하게 아무리 봐도 직관적으로 와닿지가 않는 알고리즘이다. 문자열 해싱으로 KMP 알고리즘을 대부분의 경우에서 대체할 수 있는데, 아주 만족스럽다. 해싱 찬양해~

(못 푼 문제 - 차차 풀어보기)

H. Rock Paper Scissors

정말 많은 팀이 푼 문제지만, 우리는 고민을 아무리 해도 해답을 알 수 없었다. 풀이를 보고 할 말을 잃었는데, 그야말로 전형적인 FFT 문제인 것을 전혀 캐치를 못하였던 것이다. (어차피 팀원 중 아무도 FFT를 사용할 줄 몰라서 알아도 못 풀었을 것 같다)

작년 예선에도 FFT 문제가 나왔던 터라, 많은 팀들이 빠르게 풀어낼 수 있었던 것 같다.

E. How Many to Be Happy?

A. Broadcast Stations

J. Strongly Matchable