ICPC World Finals 2021

oh hi

팀 구성

각기 다른 강점을 가진 셋이 모이면 좋은 시너지가 만들어집니다. 이번 월파를 결정지은 ICPC Seoul 2020은 제 팀원들의 강점이 골고루 부각된 대회였습니다.

• jh05013 (최재민): 접니다. 사전지식을 다량 보유하고 있으며, 긴 코드를 안정적으로 짤 수 있습니다. 서울 2020 때는 A, H, J를 풀었습니다. 월파 팀노트는 저 혼자 만들었습니다.
• easrui (이재웅): 코드포스 레이팅 2454입니다. 쉬운 문제를 빠르게, 그리고 어려운 문제도 잘 풉니다. 본인 말로는 DP 최적화에 자신있다고 합니다. 서울 2020 때는 C, E, L을 풀고, I의 풀이도 알아냈습니다.
• dillon0108 (김홍녕): IMO 금메달 출신인 만큼 수학 문제를 잘 풉니다. 서울 2020 때는 B, G, K(!!)를 풀었습니다.

이번 월파도 고난도 문제에 사전지식이랑 DP 최적화랑 수학 문제가 하나씩 나오면 동메달을 딸 수 있지 않을까??라고 생각했습니다.

ICPC Challenge

ICPC Challenge는 3시간 동안 진행하는 휴리스틱 대회로, 올해에는 화웨이에서 주최하여 multiprocessor scheduling 관련 문제를 냈습니다.

24등 했습니다.

코치들도 따로 ICPC Challenge에 참여했는데, tourist가 1등 팀을 이겼습니다 (...)

예비소집

11월 9일에는 2시간 동안 과거 월파 문제로 예비소집이 진행되었습니다. 사용된 문제는 다음과 같습니다.

• A: 2015 Catering
• B: 2018 Comma Sprinkler
• C: 2018 Go With the Flow
• D: 2020 Landscape Generator
• E: 2013 Pollution Solution

제가 BD, 재웅님이 C를 풀었습니다. 홍녕님이 E를 짜다가 남은 시간 동안 못 짤 거라는 결론을 내리고 제가 A를 대신 짜기로 했는데, 최소 비용 LR flow를 어떻게 풀지?? 하면서 코드를 마구 바꿔보다가 끝났습니다. 나중에 알고 보니 LR flow는 필요없고 MCMF로 된다고 합니다.

본대회

문제지

우선 제가 ABCD를 읽기로 했습니다. A는 설정이 너무 복잡해서 일단 넘겼습니다. B는 보자마자 다이아 근처의 트리 문제임을 직감했고 넘겼습니다. C를 읽었는데 딱 봐도 수학 문제라서 홍념님께 바로 전달했습니다. D는

그래서 A로 돌아왔습니다. 재웅님이 H를 제출했지만 틀렸습니다. 곧이어 홍녕님도 C를 제출했지만 틀렸습니다. 두 분이 각각 C H를 디버깅해보았지만 별 소득은 없었고, 제가 A를 반쯤 짠 사이 홍녕님이 C를 고쳐서 제출했지만 총 세 번 틀렸습니다. 고치는 동안 저는 다른 문제들을 읽고 있었고, J가 매우 쉬운 데다가 A의 나머지를 짜는 것보다 J를 짜는 게 더 빠를 거라고 판단해서 J를 짜기 시작했습니다.

H 76분 AC

J를 코딩하는 동안 재웅님과 홍녕님이 H를 열심히 고민하고 있었습니다. 답이 none인 경우는 나중에 생각하고 답부터 구해보기로 했는데, 그렇게 하면 예제 2도 나오지 않습니다. 수열의 길이가 유한해서 merge의 작동 방식이 그냥 둘을 번갈아서 넣는 게 아니라, 한 쪽이 다 떨어지면 다른 쪽만 들어가도록 되어 있기 때문입니다. 그래서 none을 처리하는 과정이 생각보다 복잡하다고 생각되었고, 그걸 고민하러 돌아간 뒤 재웅님이 H를 다시 짜서 맞았습니다.

J 84분 AC

별로 안 복잡했고 그대로 보완해서 맞았습니다.

A 99분 AC

내가 무릎을 꿇은 것은 추진력을 얻기 위함이었다.

팀원들이 더 풀 문제가 아직 없다고 하여 남은 A를 마저 짜서 맞았습니다.

나머지 팀원은 C가 오버플로우 이슈라고 판단해서, 제가 풀이를 그대로 받아서 파이썬으로 짰습니다. 두 번 더 틀렸습니다. 악마의 문제임이 분명해 보였습니다. 그 후 재웅님이 L을 짜기 시작했습니다.

L 157분 AC

그 사이 남은 문제들을 봤는데

• B는 할만해 보였습니다.
• D는

• E는 엄청난 수학 문제입니다. 이건 홍녕님께 맡겨야 되는 문제라서 바로 넘겼습니다.
• F도 할만해 보였으나, 이것도 수학 스타일의 기하라서 홍녕님께 넘겼습니다.
• G는 와일드카드 문자열 매칭 문제입니다. 사전지식 담당인 바로 제가 풀 문제가... 아니었습니다. 이건 제가 공부한 적 없는 문제고 팀노트에도 없었습니다. KMP 변형해서 풀 수 있을까 싶었지만, 저 와일드카드 매칭이 KMP가 아니라는 사실은 알고 있었고 재웅님이 안 될 거 같다고 하셔서 말았습니다.
• I는 어려울 것 같았습니다.
• K는 안 읽어봤지만 아무도 안 푼 문제라서 어려울 것 같았습니다.

그래서 풀 게 B밖에 없었습니다.

Key랑 trap이 없다고 하면, 문제의 답은 2 * (전체 간선의 가중치 합) - (출발점에서 가장 먼 정점까지의 거리)입니다. 여기에 key랑 trap을 넣으면 그 "가장 먼 점"이 key 쪽의 서브트리 안에 있을 때 문제가 됩니다. 그래서 그 서브트리만 제외하고 가장 먼 정점까지의 거리를 구하면 될 것이라고 판단했고, 오일러 투어 트릭이랑 세그먼트 트리를 열심히 짜서 냈지만 틀렸습니다.

C 207분 AC

그 와중에 C의 실수가 발견되었는데, q^6 <= 10^18이니까 q <= 1000만 봐도 된다고 생각했던 게 원인이었습니다. 실제로는 q^5 스케일이었습니다. 4000으로 바꿔서 맞았습니다.

저 B 풀이에는 반례가 있었습니다.

  1
 / \
2   3
   /
  4
   \
    5
   /
  6
   \
    7

3이 key, 2가 trap, 모든 간선의 길이가 1이라고 하면, 위 풀이대로 하면 11이 나옵니다. (134567654312) 하지만 정답은 9입니다. (1312134567)

이 케이스를 해결하려면 루트가 아닌 두 정점 사이 거리를 구해야 돼서, 안 그래도 자료구조 2개로 복잡해진 코드에 LCA까지 집어넣어야 합니다. 이게 실화야???

F 261분 AC

홍녕님이 F를 짜서 맞았습니다. 제가 문제 전달을 잘못해서 꽤 삽질했습니다.

재웅님이 I 풀이를 알아냈다고 해서 들어봤지만 영 아닌 것 같았습니다. 스코어보드를 보면 꽤 어려운 문제일 텐데 그렇게 간단하게 풀릴 게 아닐 것 같았고, 풀이 자체도 좀 의문이 들었습니다. 하지만 재웅님이 확신을 가지고 있는 듯 했고 15분만에 짤 수 있다고 하셔서 I로 들어갔고, 틀렸습니다.

남은 시간 동안에는 제가 B를 마저 짰고, 두 팀원이 I를 디버깅했습니다. 그런데 LCA는 생각보다 너무 짜기 복잡한 친구였습니다. 간선에 가중치까지 있으니까 더욱 그랬습니다. 안 보고 짤 수 있는 거라서 팀노트에 안 넣었는데, 잘 다룰 줄도 모르는 것들(dominator tree 등등...)을 좀 빼고 LCA를 넣을 걸 그랬습니다.

여차저차해서 LCA를 짰는데 제가 만들었던 저 반례가 안 나왔습니다. 디버깅을 해보니까 off-by-1 에러 같았습니다. 하지만 어떻게 고쳐도 답이 안 나왔습니다. 그리고 대회 종료까지 1분 남은 채 마침내 저 반례가 제대로 나왔는데, 이제는 예제에서 세그폴트가 났습니다. 자료구조 3개를 동반한 200줄짜리의 끔찍한 혼종은 그렇게 대회 종료와 함께 멸망하고 말았습니다.

대회 끝나고 들은 바로는 I는 그냥 틀린 풀이였다고 합니다.

결과

한국 팀의 결과는 다음과 같습니다.

• 서울대: 9솔브 1303페널티 4등
• KAIST (우리 팀): 6솔브 1004페널티 31등
• 고려대: 3솔브 485페널티 76등

모두 수고하셨습니다!

서울대는 2연속으로 금메달을 따냈습니다. 1등은 MIT가 무려 11솔브로 차지했습니다. 축하합니다!

D는 아무도 못 풀었습니다.

후기

이번 월파도 고난도 문제에 사전지식이랑 DP 최적화랑 수학 문제가 하나씩 나오면 동메달을 딸 수 있지 않을까??라고 생각했습니다.

사실 셋 다 나왔습니다. 고난도 문제 중에 G는 사전지식, I는 DP, E는 수학이었습니다. 아쉽게도 쉬운 문제인 C랑 H에서 많이 말렸고, 저기까지 안 가도 solved.ac 플래티넘 급 문제가 너무 많아서 건드리지 못했습니다.

B를 못 푼 게 아쉽지만 그래도 5시간 안에 풀 만한 건 B 빼고 다 푼 것 같습니다.

홍녕님은 대회 끝나고 호텔로 돌아가는 길에 E의 풀이를 알아냈다고 하셨고, 저도 공항에서 I의 풀이를 대강 머릿속으로 알아냈습니다. B G I는 이번 달에 꼭 풀어봐야겠습니다.

D는 영원히 안 풀 예정입니다.

귀국해서 집으로 온 지금은 월파 경험이 꿈만 같습니다. 슬슬 대학원으로 돌아갈 시간입니다.

업솔빙 (티어 스포일러 주의)

일주일 동안 DEK 빼고 다 풀었습니다.

한 달 동안 D 빼고 다 풀었습니다. D는 왜 안 풀었냐면,

풀이

ICPC World Finals 2021 풀이