ICPC Asia Seoul(Busan) Regional Contest 후기 (Last Dance)

어제 오늘 마지막 ICPC를 치고 왔다. 내년 부터는 나이 제한이 걸려 나가기 어려울 가능성이 높기 때문이다.

10월 11일 인터넷 예선

다음날 면접 일정이 있어 출국해야 하는 상황이라, 팀노트를 인쇄하고 짐을 챙겨두고 나왔다. 오랜만의 대회라 긴장이 많이 되었지만, Subway에서 점심식사를 하며 긴장을 풀었다.

 

내가 문제지 앞 부분을 봤는데, A가 쉬운 DP 같아서 내가 구현해서 해결했다. (7분)

 

khf1700이 F가 쉽다고 구현하였다. 하지만 틀렸다. 알고리즘이 맞는다는 사실을 증명할 수 있다 하여 내가 같이 봐줬다. 0을 제대로 처리 안한 것을 내가 지적했으나, 나 역시도 한 번 틀리게 고쳤다. 내가 코드를 한 번 더 고쳐서 맞았다. (22분)

 

내가 H번이 쉬운 문제라고 주장했고, 세그먼트 트리를 이용한 LIS 느낌의 DP를 짰는데 예제가 안 나왔다. 오랜만에 구현해본 세그먼트 트리의 문제인가 하여 디버깅하고 있는 동안 juneharold가 예제 2를 그려줬다. 내가 x축만 45도 돌렸다는 사실을 깨닫고, 고쳐서 맞았다. (68분)

 

I번을 잘 모르겠는 상태에서, juneharold가 노트에 근의 공식을 써서 식 변형을 시도해놓은 것을 보고, 그 존재를 깨달았다. 내가 조금 다른 형태로 식 정리 열심히 하니 단순하게 나왔다. 구현해서 맞았다. 정확한 근의 공식을 알려준 팀원 덕이 아니었으면 해결하지 못했을 수도 있을듯? (97분)

 

khf1700이 C번을 풀고 예제가 안 나오는데, 알고리즘은 정확하게 구현했다고 한다. 문제는 읽지 않은 상황이었지만, 코드를 보고 error-prone 한 패턴으로 작성된 코드블럭에서 typo를 몇개 잡아줬다. 제출했는데 틀렸다. 그제서야 문제와 풀이를 들어보니 가장 오른쪽의 배보다 더 오른쪽으로 가는 경우를 고려하지 않은 것 같았다. 코드를 복잡하게 고치길래 미안하다고 하고 컴퓨터를 가져와서 내가 맨 오른쪽에 가상의 점 몇 개를 더 넉넉하게 추가해서 AC를 받았다. (119분)

 

juneharold가 J번을 DFS로 cycle detection 해서 풀 수 있다고 주장했다. 거리 4만큼만 보면 되어서 $O(n(n+m))$에 돈다고 했다. 나는 짝수 길이의 짧은 cycle에 대한 논문들을 몇 개 본 기억이 있어서, 그런게 자명한 접근 같지는 않다고 생각했다. 나는 D번에서 플로우가 매칭들로 나눠질 것 같다는 생각이 들어서 더 고민해보고 싶기도 했고, 팀연습때 한번 맞는 풀이를 내가 정당성 검증을 빡세게 요구했던 적이 있어서, 머신도 비어 있으니 짜보라고 했다. 역시나 틀렸고, 내가 코드를 보고 반례를 알려줬고, DFS로 이걸 해결하려면 3개의 인자를 추가로 들고 다녀야 해서 TLE가 남을 알려줬다.

 

J번을 보다가 컷팅 잘 하면 빠르게 돌 것 같아서 구현해보는데, 생각보다 상수가 큰 것 같아서 고민하고 있었다. 다행히도 khf1700이 적절한 제안을 줘서 조금 더 발전시켜 상수 작은 $O(n^3)$ 풀이를 얻었다. 구현해서 AC를 받았다. (155분)

 

이후 D번을 고민하다가 대회가 끝났고, 6솔브한 팀이 되게 많은 것 같아서 걱정을 했지만 의외로 넉넉하게 본선에 진출했다. 이런저런 아쉬움은 있었지만, 다행이었다.

11월 21일 금요일

새벽 감성 속에 대만 리저널 후기를 정리하는 글을 썼다. 내가 키보드를 잡다가 인터넷 예선과 대만리저널 모두 말아먹은 것 같아서, 이번에는 키보드 욕심을 부리지 말자고 생각했다.

 

일반화학실험을 빠르게 마쳐야 제시간에 부산에 갈 수 있어서, 조원과 함께 실험을 아주 빠르게 마치고 나왔다. 실험 조원은 베트남 출신 신입생으로, 조원 역시도 ICPC를 친다.

 

부산에 도착했는데 재학증명서를 안 가져왔음을 깨달았다. 내가 원래 약간 관종이라, RUN 디스코드에 약간의 어그로를 끌었다. 그런데 나만이 아니어서, octane의 재학증명서도 같이 인쇄해서 들고갔다. 아쉽게도 계정 아이디/비밀번호가 안 맞아서 비회원 요금을 지불했다.

 

 

예비소집 때 C번 문제의 지문을 읽지 않고 예제만 보고 제출했다가 틀렸다. 지문을 읽어보니 생각보다 어려웠고, 마치고 TAMREF 한테 나의 아이디어를 이야기 하니 조금 더 가면 된다고 했다.

 

parkky 팀과 함께 채점 서버에 소스코드 연산량을 의도적으로 조절하며 내보면서, 나눗셈을 포함한 사칙연산 약 2억번, 대회장에 준비된 로컬 머신 기준 0.6초 정도에 도는 코드가 1초 제한 안에 아슬아슬하게 돈다는 사실을 확인했다.

 

이후 서면에 잡은 도요코인 호텔에 체크인 했다. 숙소로 가는 택시에서 8884844년 만에 건너는 광안대교가 기억 속의 무언가보다 1557배 예뻐 보였다.

 

저녁으로는 간만에 부산 온 김에 이재모피자를 먹고 싶었지만, 웨이팅이 말도 안됐다. 그래서 고등학교 후배 parkky와 모교에 들렀고, 나의 게으름을 누구보다 잘 아시는 수학 선생님과 간만에 즐거운 대화를 나누었다.

 

은사님께서 내가 대학교 공부 너무 날로 먹으면서 여행만 다닌다고 머리 빠르게 돌아갈때 연구자의 길을 걸어보는 것을 추천해주셨다. 새로 집필하신 교과서도 선물 받았다.

 

간만에 당감동에 오니 예전에 가던 국밥집이 생각나서 parkky를 데리고 갔다. 백양돼지국밥 근본있다. 배고파서 수육까지 시켰고, 식사는 내가 샀다. 대선 소주 없으니 아쉬웠다.

 

이후 숙소로 돌아와 이런 저런 고민을 하다가 자려고 시도했다. 잠이 잘 안와서 소주를 괜히 안마셨다는 생각을 했다.

11월 22일 토요일

아침 5시 30분에 눈을 떠서, 어제 연습세션 문제를 업솔빙 했다. 깨달음을 얻었다. 업솔빙 하다 보니 팀원들끼리 모이기로 한 시각보다 늦게 내려가서, 대회장에도 약간 늦게 도착했다. 내가 스태프 했을 때 1등 했던 팀도 대회장에 지각했었다고, 괜찮을 것이라 알려줬다. 가는 길에 junie랑 통화하면서 이따 한 잔 하기로 했다.

 

막상 대회장에 들어오니, 긴장 되기 시작했다. 긴장을 풀 겸 junggoldchae, man_of_learning, abra_stone 등 UCPC 같이 운영한 친구들 자리를 돌아다니며 인사했다. 스태프가 와서 자리로 돌아가라고 해서 돌아갔다.

대회

대회가 시작된 직후, 내가 대회 환경을 setup 하였고, khf1700이 M번 풀이가 있다고 했다. 쉬운 것 같아보여서 듣고 내가 짜고 싶었지만, 그냥 머신을 비워줬다. 예제가 나오지 않아서 헤매길래, 내가 M번 문제를 봤는데, 그런 복잡한 코드가 필요 없는 것 같았다. 내가 머신을 뺏었고, 입력 값이 3의 배수여도 되는 코드를 짰다가, 문제를 자세히 읽고 정수를 3번씩 출력하는 코드로 바꾸어서 AC. (12분)

 

이 때 머신을 뺏어서 약간 미안했다.

 

L번 문제 요약을 들었고, 쉬운 문제라서 내가 구현하는데, juneharold가 조금 더 구현이 쉬운 방법을 제안해줘서 그렇게 짰다. AC. (17분)

 

다른 팀이 G번을 많이 푼다고 juneharold가 문제를 요약해줬다. 이분탐색 후 시뮬레이션을 하면 될 것 같지 않냐고 되물어봤는데, 잘 모르겠다고 했다. 그래서 내가 조금 더 설명했고, 그도 동의하여 구현했다. WA를 받았고, dm을 짜도 답이 안 나오길래 오버플로우 때문임을 깨달아 적절히 수정 후 AC. (58분)

 

khf1700이 E번이 쉬운 문제이고, 트리 DP라고 했다. 팀연습때 트리 DP를 두 명이 같이 짜서 틀린 것을 내가 고쳐서 맞았던 기억이 있어서, 점화식이 명확히 나왔냐고, 식을 보여달라고 했다. 식 조차 필요없을 정도로 좌우에 최대한 균등하게 서브트리를 배치하면 된다고 했다. 뭔가 사기풀이 같아서 증명 가능하냐고 물어봤지만, 증명은 안 되지만 강한 확신이 있다고 해서 비켜줬다. 내가 너무 컨트롤프릭 처럼 머신을 혼자 쓰려고 하는지에 대한 고민을 약간 했다.

 

그동안 juneharold가 요약해준 것을 듣고 C번을 고민해봤는데, 간선을 추가해 생길 수 있는 bounded region은 서로 crossing 할 수 없으므로 (laminar set 느낌) 부모 자식 관계가 있는 forest처럼 생각할 수 있고, 차례로 합쳐가면서 넓이를 구해주면 될 것 같아 보였다. 이것을 제안해봤는데, 너무 복잡하다고 했다.

 

juneharold가 region의 둘레를 알면 넓이를 구할 수 있다고 했다. 내가 반례를 줬는데, 사실은 문제의 조건을 만족하지 않는 반례였다. 무언가 미심쩍은 면은 있어서 더 생각해보기로 했다. 문제의 조건을 만족해도 안되는 것 같은 근거를 조금 생각해보고 말았다.

 

제출 없이 E번 코딩이 길어지길래, E번을 독립적으로 풀어보려고 봤는데, 아까 들은 풀이가 안 될 것만 같은 생각이 들었다. 논리적인 설득을 해야할 것 같아서, 구현 중인 풀이에 대한 반례 구성을 시도해보았고, 되는 것 같았다. 그 즈음 juneharold가 아까 반례는 틀렸고, C번의 관찰에 대한 확신이 있다고 하였고, 나도 반례를 생각해보려 하니 막상 기억이 안나서, LCA를 구하면 풀 수 있다는 말을 일단 받아들였다.

 

khf1700에게 예제가 안 나오냐고 물어봤고, 반례가 있는 것 같으니 머신을 비우는게 좋겠다고 조금 강력하게 말했다. juneharold가 머신을 넘겨받고 구현을 시작했고, 나는 khf1700으로 부터 그의 풀이에 대한 설명을 들었다. 서브트리를 좌/우 어디에만 둘지 결정하면 되고, 배치하는 순서가 상관이 없다는 이야기를 들었다. 그 풀이와 풀이를 사소하게 수정해도 여전히 고칠 수 없는 몇 가지 오류를 반례를 통해 알려줬다. 그리고 exchange argument의 개념을 알려줬고, 그리디 알고리즘이 되는 확신이 생기면 이 개념을 통해 정당성을 생각해봐 달라고 부탁했다.

 

반례를 만들어서 서브트리를 작은 순으로 적당히 번갈아가며 놓는 방법을 생각했으나, 확실하게 그냥 DP로 해도 쉬운 것 같았다. 그런데 이 시점에서 설득하느라 너무 지친 나머지 나는 문제를 열심히 보지는 않았다. 배가 고파서 도시락을 열심히 먹었다. 김밥이 맛있었고, 닭강정도 괜찮았다. 샌드위치는 빵이 살짝 목 막힐 것 같아서 손 대지 않았다. 과일도 당도가 좋았다!

 

그래도 남들이 풀길래 K번을 봤다가 각 점 중심으로 각도순 정렬 하면 안되냐고 이야기를 꺼냈는데, 뭔가 mis-communication으로 서로 다르게 받아들였던 것 같다. 그 후 불도저 트릭을 쓰는 뇌절 풀이를 생각했다. 이건 명확히 설명할 수 있다 생각했는데, 팀원들이 안되는 것 같다고 했다. 나는 사실 불도저 트릭을 잘 몰라서, 일단 고민해달라고 부탁하고, 다시 밥을 먹었다.

 

이후 C번 제출이 틀렸다고 하여 코드를 봐줬고, LCA 구현에 틀린 부분이 있어서, 일단 그 부분을 적절히 찾아서 알려줬다. 그런데도 WA가 나왔고, 그제서야 이야기 나누다가 아까 까먹은 반례가 생각났고, juneharold도 반례가 있는게 맞는 것 같다고 했다. 나의 풀이를 설명했는데, juneharold는 여전히 어떻게 되는지 모르겠다고 했다.

 

khf1700이 D 풀이가 있어서 짤 수 있을 것 같다고 했는데, 그냥 내가 I를 짤테니 정확한 식이나 조건을 구해달라고 부탁했다. 잠깐 컴퓨터를 넘겨 받아 I를 구현했다. 그 과정에서 평소에 하지 않을법한 실수로 1번 틀렸다. 아무튼 AC. (214분)

 

D번 정확한 풀이를 khf1700과 juneharold가 찾았다 하여 khf1700에게 머신을 넘겨줬다. 케이스를 꼼꼼히 봐야하는 것 같긴 한데, 집단지성으로 잘 했으리라 생각했다. 그 사이에 juneharold가 E번 그리디가 된다고 또 다른 그리디를 제시했고, 나는 exchange argument가 어떻게 성립하냐고 물어봤는데, 그건 모르겠다고 했다. 그래서 내가 그냥 컴퓨터 비면 DP를 짜겠다고 했다.

 

D번 WA를 받고 디버깅이 한참동안 끝나지 않아, 대회 종료 조금 전에 내가 컴퓨터를 뺏어왔다(...) 이미 코딩 하고 싶지 않고, 괴로운 상황이었지만, 그래도 키보드를 치고 싶었기 때문이다. 마지막 남은 체력을 모아 E번을 짜기 시작했다. 평소 같으면 하지 않을 실수들이 많아 굉장히 부끄러웠다. (subtree size 구하는 코드 등등 사소한 데서 많은 오타가 나서 디버깅을 조금 했다.)

 

그 와중 D번 고쳐야 할 부분이 명확하다고 비켜달라고 해서 비켰는데, 아쉽게도 틀렸고, 손으로 작성한 로직과 새로 제출한 코드에 불일치가 있어서 그것도 고쳐봤는데 틀렸다고 들었다. 그 즈음에 앞자리 DaiMonge 팀이 10번째 솔브를 해서 작게 박수 쳐줬던 기억이 난다.

 

결국 다시 컴퓨터를 넘겨받았지만, E번 점화식이 정작 내가 헷갈려서, 코드를 제출하지 못하고 대회가 끝났다. 짐 챙기는 사이에 juneharold가 나의 C번 풀이가 맞는 것 같은데, 이상하게 설명해서 이해를 하지 못했다고 알려줬다.

대회 이후

마지막 대회인 만큼, 결과에 아쉬움이 상당히 많이 남았고, 화가 나는 부분도 있었고, 또 팀에서 혼자 선배로서 예선과 대만, 부산에 걸쳐 삽질을 많이 한 것 같아서 미안함도 있었다. 아무리 못해도 6~7문제는 풀만한 셋이라 아쉬움이 유독 많은 하루였다.

 

나오는 길에 생각해보니, 잡고 있던 머신을 놓으라고 커뮤니케이션 하는 과정에서 전달이 잘 안되어서, 틀린 풀이를 왜 짜냐는 식의 꼽 주는 수준으로 이야기 해서 팀원들 기분이 상한 면도 있으리라 느껴졌다. 어쩌면 그 이전 대회들에서 디버깅 길어지는 것을 보지 못해, 내가 머신을 뺏어와서 코드에 개입 했던 것이 감정적으로 쌓였을 수도 있으리라 생각한다. 아무쪼록 팀워크 능력에 있어 아직 내가 개선해야 할 요소가 많은 것 같다. 그래서인가 팀원 한 명은 시상식 전에 귀가하고, 다른 한 명은 시상식을 즐기지 못하고 회사 일을 하게 만든 것 같아 약간은 미안했다.

 

어찌 됐든 나의 마지막 ICPC는 끝났고, 우리팀은 57등으로 마무리했다. 아쉬운 결과이지만, 지나간 일은 털어버리는게 맞다고 생각한다. 다음 주에 팀원들에게 저녁을 한 번 사기로 했다.

그래도 ICPC 덕에 대학교에 적응을 잘 하지 못하던 휴학 전의 기간을 즐겁게 보낼 수 있었고, 언제건 소주 한 잔 걸칠 수 있는 친구들도 많이 생겼고, 이력서 한켠도 약간은 채워지고, 좋은 회사에서 직장 생활을 해봤던 것 같다. 이런 점에서 운 좋은 대학생활을 했다고 느끼며...

 

시상식을 즐겼다. 올해도 alperatz(suckzo_o)님의 스코어보드 언프리징은 기깔났고, 기술 스태프 분들의 운영은 매끄러웠으며, 인쇄한 코드가 배달되는 속도에서 현장 스태프 분들의 빠른 일처리가 잘 느껴졌다. 내가 현장 스태프 했을 때는 저렇게 까지 빠르진 않아서 더 그랬을듯.

뒷풀이

대회를 마치고 20s(benedict0724, junie, TAMREF) 팟에 탑승해 이재모피자를 다시금 시도해보겠다는 원대한 계획을 가졌으나, 도착해 보니 이미 대기는 마감이었다. 그래서 차이나타운의 마가만두에 줄을 섰고, 유감스럽게도 benedict0724는 기차를 타러 먼저 돌아갔다.

 

마가만두 대기가 생각보다 천천히 줄어서 G번 문제를 출제한 kipa00과 아주대학교 팀도 조인해서 함께 식사를 하였다. 지인(?) 팟(namnamseo, zigui, suckzo_o, yclock)도 우리와 함께할 수도 있다고 들었는데, 타이밍 이슈로 그러지 못했다 :( 대신 2차로 그쪽 팟 식사 자리에 꼽사리 껴서 즐겼다. 저녁으로 먹은 중식이 아주 휼륭했고, 2차에서는 배불러서 소주만 깨작깨작 마셨는데 서울 올라가는 기차에서 엄청난 갈증을 느꼈다.

 

아무튼 아쉬움과 허전함, 약간의 짜증은 소주를 털어넣는 그 순간에 사라졌고, 즐거운 기억만 남아서 다행이다!