ICPC 2021 후기

예선 후기는 stonejjun 블로그에서 볼 수 있다.

---

우선 대회 당일에 우여곡절이 정말 많았다. 대회 장소에 문제가 생겨서 세팅하기에도 바빴는데 프린터도 고장나서 그냥 노트북으로 순서대로 같이 읽기 시작했다.

A는 지문이 너무 길기도 하고 딱 봐도 처음 풀 문제는 아닌 것 같아서 B로 넘어갔다.
모든 색깔이 다 포함되는걸 무지개라고 하고, 두 겹인걸 찾으면 된다는 것까지는 이해했는데, 끝날 때까지 $P$도 임의로 정하고 $P'$도 임의로 정하는걸로 이해하고 있었다. 근데 stonejjun이 풀 수 있다고 해서 풀고 있었다.

이 쯤에 아마 프린터가 고쳐져서 문제를 뽑다가 다시 고장났다. 그래도 어찌저찌 앞 부분 문제는 볼 수 있었다. C는 그냥 시뮬레이션이었고 B도 코딩이 잠깐 막혀있어서 일단 내가 C부터 푼 뒤에 B도 금방 풀렸다.

[00:17] C (AC)
[00:23] B (AC)

이 때 D가 풀려 있어서 D를 봤다. 잠깐 고민해보니 완전그래프를 찾는 것보다는 간선을 뒤집는 느낌으로 같은 그룹일 수 없는 것들을 나누는게 편하다는걸 알아냈다.
나는 여기서 2-SAT으로 참 거짓 개수 차이를 최소화하면 된다는 많이 과한 풀이를 냈는데, ryute가 이분그래프에서 잘 나눠주면 된다고 정리해줘서 풀었다.

[00:50] D (AC)

이쯤부터 이것저것 문제를 다 보기 시작했다. A는 내가 봤는데, 이것도 끝날 때까지 해석을 잘못하고 있었다. HLD에 세그 같아서 포기하긴 했는데 생각보다 풀만 했던 것 같기도 하다.
G는 센트로이드로 무조건 풀 수 있다는건 알아냈지만 팀노트에 없어서 미루고 일단 stonejjun이 J를 풀고 있었다. 그러다 J가 막혀서 내가 센트로이드를 짜보려고 노트북을 잡았다.
근데 그 사이에 stonejjun이 L 풀이를 금방 찾았고 풀이가 깔끔해서 금방 풀었다.

[02:32] L (AC)

그리고 다시 센트로이드를 짜보니 생각보다 코딩이 잘 돼서 금방 맞았다.

[03:01] G (AC)

그러는 동안 ryute랑 stonejjun이 E 풀이를 거의 냈고, 4트만에 맞았다.

[03:39] E (AC) (+3)

이제 stonejjun은 계속 J를 시도하면서 나랑 ryute는 F를 풀기로 했다.
F는 금방 매우 그럴싸한 풀이가 나왔지만 확실하지는 않았고, 1.2초 제한에 $n$이 $10^6$인데 세그를 써야돼서 아주 불안한 풀이였다.
그래도 일단 그렇게라도 짰더니 WA가 나왔다. 등호 하나 때문인 것 같아서 고쳐서 냈더니 또 WA였다. 그런데 고친 거에서는 예제도 안 맞아서, 풀이가 잘못 됐다는걸 알았다.

여기서 나는 삼분탐색을 넣고 세그를 sparse table로 바꾸겠다고 했는데, 사실 그 방법은 더 문제가 많았고, ryute가 원래 풀이에서 반대 방향으로도 하면 된다는 걸 찾아서 그렇게 고쳤다.
이제 아니나 다를까 TLE가 나서 어떻게든 세그를 안 쓰든가 비재귀로 짜서라도 내보든가 해야 하는 상황이 됐다.
근데 비재귀 세그도 팀노트에 없어서 망했다고 생각했는데, 막상 짜보니 생각보다 잘 돼서 극적으로 맞았다.

[04:32] F (AC) (+5)

남은 시간 동안 K를 보니 아무리 봐도 KMP 같지만 어떻게 해야되는지는 모르겠어서 사실상 쉬었다.
stonejjun은 계속 J를 고치면서 끝까지 제출해봤는데 아쉽게도 풀리진 않았다.

---

결과적으로는 우여곡절이 많았던 것 치고 매우 잘 풀렸다. 다만 G랑 F에 좀 과한 풀이를 쓰면서 패널티가 조금 말린 것 같다.
우리 팀의 고점은 J를 마지막에 맞거나, A나 K가 아는 문제여서 보자마자 풀 수 있는 상황이겠지만 그렇지 않았던게 조금 아쉽기는 했다.
올해 동안 UCPC는 예선 20등, 본선 21등을 하고 ICPC는 예선 13등, 본선 14등을 하는 매우 일관적인 결과가 나왔으니 결론적으로 딱 비슷하게 했다. 게다가 팀연습을 2번만 한 것 치고는 그냥 역할배분이 잘 됐으니 오히려 아주 잘 풀린 것 같다.
대학오면 ICPC 열심히 준비해서 나갈 줄 알았는데 막상 해보니 간절함이 많이 부족하긴 하다. 그래도 다행히 상을 타서 앞으로 마음은 좀 편할 것 같다.