지난번 팀연습때 쉬운 문제인데도 디버깅하느라 시간 끌려서 결국 못 푼 문제가 확실히 많았어서 지난 팀연습이 끝난 뒤 가장 먼저 한 일은 ‘1PC로 인한 병목 및 디버깅 문제 해결’ 이었습니다. 논의 중에 나온 여러 의견 중 jame0313님이 코드 짜다가 막히면 짜던 코드를 인쇄하고 PC를 다른 사람에게 넘겨주자는 의견쪽으로 힘이 실렸는데, 이 방법은 문제가 코드를 인쇄할 방법이 없다는 것입니다. 팀연습 및 대회를 집이 아닌, 스터디 카페에서 진행하고 있기 때문에, 저희 팀 노트북의 코드를 인쇄용 컴퓨터로 옮길 방법이 없었습니다. 오프라인 대회였으면 이런 고민을 안 해도 됐을텐데.. 내 오프라인 대회 돌려줘 ㅠㅠ…
다행히도 연습 장소가 집에서 가장 가까웠던 kyaryunha가 프린터를 지름으로써 문제가 해결되었습니다. (행동력 리스펙 ㄷㄷ) 중간에 배송이 취소되는 등의 이슈가 있긴 했지만 재주문해서 어찌저찌 이번 팀연습부터 바로 프린터와 함께하게 되었습니다.
이번 팀연습셋은 1PC 병목 해결을 위해 문제수가 많은 셋을 풀어보자고 했고, 총 14문제로 구성된 NWERC 2020을 하자고 제안했는데… 팀연습 전날에 보니 3문제는 예비소집문제였고 본 대회 문제는 11문제여서 약간 당황했습니다 ㅋㅋ..
팀연습이 시작되자마자 셋이서 A, B, C번을 하나씩 나눠가질 생각부터 하고있었는데, 정작 출력은 K부터 시작했습니다. 그리고 K번 지문이 짧아보여서 읽어봤는데 그냥 첫 번째 줄에서보다 두 번째 줄에서 더 많이 등장하는 문자열을 출력하면 되는 문제였고, 제가 금방 코딩해서 AC를 받았습니다.
K solved (by artichoke42, 5min, 제출 1회)
K번을 푼 이후로, H번과 C번을 푼 사람이 나왔다고 해서, H번은 제가, 그리고 C번은 kyaryunha가 읽기 시작했습니다. H번은 정렬한 후 중앙값부터 시작해서 작은 값/큰 값을 번갈아 출력하면 될 것 같았고, jame0313님이 더 빠르게 구현할 수 있을 것 같아 코딩을 넘겼는데 지금 생각해보면 굳이 넘길 필요는 없었던 것 같긴 합니다 ㅋㅋ.. 아무튼 H번도 11분경에 AC를 받았습니다.
H solved (by artichoke42 & jame0313, 11min, 제출 1회)
H를 푼 이후 저와 jame0313님은 푼 사람이 나온 A를 잡고 있었던 한편, kyaryunha는 C에서 2WA를 쌓고 뇌절중이었습니다. 옆에서 C 코드를 본 jame0313님이 소수점 출력 자리수를 늘려볼 것을 제안했지만 WA 하나만 더 쌓을 뿐이었습니다. 그래도 곧 kyaryunha가 본인 코드의 실수를 잡아내고 26분에 결국 AC를 받았습니다.
C solved (by kyaryunha, 26min, 제출 4회)
A번은 처음 봤을 때는 냅색이나 그리디처럼 보였는데, 냅색을 하기엔 k 제한이 너무 크고, 그리디는 반례가 금방 나왔습니다. 그러던 중 작은 범위에서는 냅색을 하고, 큰 범위에서는 정해놓은 작은 범위 안에 들 때까지 그리디하게 고르는 ‘믿음에 의한’ 풀이를 생각해냈고, jame0313님이 비슷하게 풀리는 문제를 SCPC에서 본 것 같다면서 코딩에 들어갔습니다. 하지만, WA를 받았고, 작성한 코드가 오버플로우 이슈가 있는 것을 발견하고, long long으로 고쳐 냈지만 여전히 WA였습니다. 이쯤에서 저는 F 해석 뇌절하고 있던 kyaryunha에게 F 문제 설명을 해주고, D로 넘어갔습니다.
D번은 기하학문제였고, 일단 (0, 0)을 출력한 뒤 \( x^2 + y^2 = d \) 를 만족하는 (x, y)쌍을 모두 출력하는 것을 n번 반복하면 될 것 같아보였습니다. 쿼리 제한이 1000이었기 때문에 (x, y)쌍이 140개 이하일 것이라는 ‘믿음’에 의한 풀이였는데, 140개에 한참 못미칠 것 같아 코딩에 들어갔습니다. 코딩은 금방 끝나긴 했지만, 예제가 나오기는 커녕 런타임 에러가 떠서 코드를 인쇄하고 F 풀이를 떠올린 kyaryunha에게 PC를 넘겨줬습니다.
디버깅은 생각보다 금방 끝났는데, scanf 인자에 &를 안 붙인 것이 문제였습니다. ???: 이럴 거면 C++쓰세요! kyaryunha가 F 코딩하다 막혔는지 PC를 다시 저에게 넘겼고, D 코드를 고치고 예제가 잘 나오는 것까지 확인하고 냈는데, 1번 TC에서부터 시간이 오래 걸리길래 일단 A 코드의 오류를 찾은 jame0313님에게 PC를 넘겼습니다.
jame0313님은 A 코드를 금방 고쳐서 AC를 받았고, 얼마 안지나 제 D코드가 ILE(Idleness Limit Exceeded)가 난 것을 확인했습니다. printf는 “\n” 출력하면 flush를 알아서 하는 줄 알았는데, 아니었던 모양입니다. 그래서 코드에 fflush(stdout)을 넣고 제출해봤는데 이번엔 RTE를 받았습니다. 쿼리 횟수 초과인가? 싶었는데 알고보니 범위를 벗어난 x, y좌표 때문이었고, 이 부분을 고치고 D도 AC를 받았습니다.
A solved (by artichoke42 & jame0313, 82min, 제출 3회)
D solved (by artichoke42, 89min, 제출 3회)
A와 D가 풀린 이후, jame0313님이 E가 게임 dp같다고 던지시길래 제가 잡고, jame0313님은 G, I, J를 번갈아 읽기 시작했습니다. E를 처음에는 이동 1회씩만 하는 줄 알고 단순 브루트포스 아닌가? 하고 짰는데 예제 3번에서 오답을 내는 것을 보고 그제서야 해석을 제대로 했습니다.
일단 Alice가 이기는지 여부는 밋 인 더 미들을 쓰면 될 것 같은데, tie인지 Bob이 이기는지 여부를 어떻게 판별해야 할지 모르겠어서 jame0313님에게 문제 설명을 해줬는데, jame0313님이 Bob이 커버할 수 있는 칸이 절반 이하이기 때문에 랜덤으로 뚫을 수 있을 것 같다고, 짜보겠다고 했습니다. 그렇게 E 코딩은 막힌 채로 디버깅만 간간히 도와드리기로 하고, 저는 I로 넘어갔는데, 약 3~40분정도 들여서 E 코딩을 끝내고, 제출해서 AC를 받았습니다.
E solved (by artichoke42 & jame0313, 188min, 제출 1회)
여담인데 MITM + 랜덤이 정해가 맞다고 합니다. 대회에 랜덤 알고리즘이라니 
한편 E보다 코드가 조금 더 일찍 완성된 F는 예제가 잘 나와서 제출했는데 WA를 2번 받은 듯 보입니다. F 뇌절이 장기화되는듯 보여서 kyaryunha에게 풀이 설명을 들었는데 반례가 바로 보여서 제시해 줬습니다. 이후 E 코딩을 끝낸 jame0313님도 F 풀이에 합류해서 저는 다시 I로 넘어갔습니다.
jame0313님이 E를 짤동안 본 I는 Tijmen의 시작 위치에 대해서는 선형탐색, Annemarie와 Imme의 시작 위치에 대해서는 이분탐색으로 풀면 \( O(N^2 \log^2 n) \) 에 풀수 있을 것 같은 문제였습니다..만 구현이 좀 많이 빡세보였습니다. 코딩할 자신이 없어서 팀원들에게 부탁하려 했지만 마땅치 않아보여서 이번엔 꼼짝없이 제가 코딩하게 되었습니다.
남은 시간동안 kyaryunha와 제가 번갈아가면서 각각 F와 I 코딩을 했고, 각각 277분, 288분에 AC를 받았습니다. 어찌저찌 풀긴 했지만 짜고 보니 제쪽은 코딩하는데 2시간씩이나 쓸 정도의 구현 난이도는 아니었는데.. 여전히 제 구현실력은 갈길이 멀다는걸 깨닫게 되었습니다.
F solved (by kyaryunha & jame0313, 277min, 제출 4회)
I solved (by artichoke42, 288min, 제출 2회)
총 8솔브를 했고, 남은 B, G, J(특히 B)가 solved.ac 기준 다이아 4 이상의 상당히 어려운 문제였기 때문에 풀 문제는 다 푼 느낌입니다. 게다가 다이야 5였던(지금은 플래티넘 1로 내려간) E번도 풀었기 때문에 순위가 꽤 높을 줄 알았는데.. 459팀 중 169등으로 썩 만족스럽지 않은 퍼포먼스가 나왔습니다.
이번 팀연습을 돌아보자면..
우선 프린터 체감이 상당히 컸습니다. 원래 다른 사람이 코딩중일때 할 수 있는 거라곤 다른 문제 읽기 내지는 풀이 로직 점검 정도였는데, 코드 인쇄를 함으로써 코드상의 문제도 찾을 수 있게 되어, 1PC로 인한 병목을 효과적으로 줄일 수 있었던 것 같습니다. 프린터 없었으면 지난 팀연습때처럼 F랑 I는 커녕 E조차도 시간 부족해서 못 풀었을 수도 있었을 것 같습니다. 그리고 저 같은 경우, 노트북 화면을 보면서 디버깅할 때보다 프린트해서 디버깅 할 떄 코드 이해가 더 잘되고, 버그도 더 빨리 찾게 된다고 느겼습니다.
그럼에도 불구하고 여전히 1PC로 인한 병목은 약간 남아있는 것 같습니다. 대부분 제 문제긴 한데, 인쇄된 코드에서 버그를 찾았고, 고쳐서 제출만 하면 되는 상황에서 다른 팀원을 기다리느라 시간을 끌린 경우가 많았습니다. 이런 상황에서는 코딩하다 막히면 컴퓨터 넘겨달라고 하곤 했는데, 금방 고칠 수 있는 문제면 앞으로 컴퓨터를 즉시 뺏어야 할 것 같습니다.
그리고 자잘한 코딩 실수가 너무 많은 게 좀 아쉬웠습니다. F번이야 로직 문제였기 때문에 어쩔수 없다 쳐도, C, A, D, I번은 모두 자잘한 코딩 실수로 인한 WA였습니다. 코딩 실수만 없었어도 140 페널티가 절약되고, 특히 A번, D번 디버깅 할 시간에 E, F, I번을 더 빨리 풀거나, J번을 풀 수도 있었기 때문에 더욱 아쉽네요.
문제별로 보자면, E번과 F번이 가장 아쉬웠습니다. 이번 팀에서도 제가 문제 읽기 담당이 될 것 같기 때문에(코딩 빈도가 가장 낮으므로..), E번과 같은 해석실수는 치명적입니다. 단기간에 영어 실력을 늘릴수는 없겠지만 적어도 문제를 꼼꼼히 읽기라도 해야겠습니다.
F번은 저나 jame0313님이 좀 더 빨리 kyaryunha를 도왔어야 했습니다. kyaryunha가 F를 1시간 반정도 붙잡고 있을 때 쯤에서야 F번 로직을 듣고 반례를 제시했었는데, D번을 푼 직후에 E를 잡을 게 아니라 F번을 같이 푸는게 차라리 더 나았을 것 같습니다. 당시 E를 푼 팀보다 F를 푼 팀이 한 10배쯤 더 많았기 때문에.. 문제를 푼 뒤에 팀원 상태를 확인하고(팀원이 한 문제를 오래 잡고 있는지 등등..) 다음 문제를 잡아야 한다는 교훈을 얻을 수 있었습니다.