2024 ICPC Seoul Regional 본선 후기

2024년 11월 23일 10:00~15:00에 ICPC Seoul Regional 본선 대회를 치렀습니다.

최종순위 1위로 월드 파이널 진출을 거의 확정했습니다.
좋은 성적 거둘 수 있게 도와준 팀원들(kizen 이동현, leinad2 최다니엘), 그리고 그 외 많은 지인분들께 진심으로 감사하다는 말씀 올리고 싶습니다. 월드 파이널에서도 좋은 결과로 마무리할 수 있도록 노력하겠습니다.

대회 복기 겸 전체적인 타임라인을 작성해보려고 합니다.

대회 시작 전 (~0:00)

문제가 총 12문제임을 확인했습니다. 늘 하던 대로 leinad2가 A~D를, 제가 E~H를, kizen이 I~L을 읽어보기로 했습니다.

0:00~0:08

leinad2가 A를 읽고 바로 풀이를 떠올려서 짜기 시작했습니다. 제가 담당한 문제의 첫인상은 다음과 같았습니다.
E: 풀이는 어렵지 않은 대신 구현 디테일이 많아보이는 기하 문제였습니다. 저는 기하에 굉장히 약하기 때문에, leinad2나 kizen에 양도하는 것이 전략적으로 좋으리라 생각하여 패스했습니다.
F: 어떻게든 시간을 들이면 풀릴 것 같은데, 제한이 0.7n²인 걸로 보아 그리 자명한 문제는 아닐 것 같았습니다.
G: 문제가 너무 단순해서, 처음엔 정말 쉬울 거라고 생각했습니다. 다만 이렇게 단순한 문제가 쉽게 풀리면 지금까지 대회에 나온 적이 없을 리가 없다고 생각해서 의외로 매우 어려운 문제일지도 모르겠다고 생각했습니다.
즉, G를 읽고 나온 결론은 '매우 쉽거나 매우 어려울 것이다' 였습니다. 그래서 G를 잠깐 잡아보고 진전이 없으면 F를 잡기로 하여 G를 고민하기 시작했습니다.
[0:08] leinad2가 A AC를 받았습니다.

0:08~0:17

leinad2는 B 풀이를, kizen은 L 풀이를 떠올렸습니다.
G는 고민할수록 진전이 없어서, 앞서 생각한 대로 우선 F를 고민해보기로 했습니다.
[0:17] leinad2가 B AC를 받았습니다.

0:17~0:25

leinad2가 AC를 받자마자 kizen이 L을 짜기 시작했습니다.
F에서 중요한 관찰을 했습니다.
초기 수열의 inversion 개수가 2n(n-1) ~= 2n²인데, 한 번의 swap으로 줄어들 수 있는 inversion 개수는 최대 3입니다.
최소 0.67n²회 정도의 swap이 필요하므로, 0.7n²의 제한이 상당히 빡빡합니다. 한 번의 swap에 inversion 수를 3 줄이기 위한 조건을 알아낸 후, 그 조건을 만족하게끔 swap하는 횟수가 최대한 많게 하기 위한 해를 construct하면 되겠다고 생각했습니다.
[0:25] kizen이 L AC를 받았습니다.

0:25~0:49

leinad2가 J 풀이를 떠올리고 구현을 시작했습니다.
F에서 중요한 관찰을 한 후에 조금씩 말려서 시간이 조금 걸렸지만, 가능성이 높은 풀이를 떠올리는 데 성공했습니다. F는 문제 특성상 로컬로 정답 여부 확인이 가능했던지라 우선 짜 보기로 했습니다.
J를 제출했는데 틀렸습니다. 많은 팀이 J를 틀리고 있었기에 고려하지 못한 부분이 있을 것이라 생각했습니다. J 코드를 출력해서 leinad2가 디버깅을 진행했고, 그 사이 제가 F 코드 작성을 시작했습니다.
[0:49] leinad2가 J를 계속해서 수정한 끝에, 3번의 패널티로 AC를 받았습니다.

0:49~1:08

kizen이 C, H가 구현 가능하다고 했습니다.
[1:08] F 구현을 마무리했습니다. 로컬에서 돌렸을 때 최대 케이스까지 맞아서 거의 확신에 찬 상태로 제출했고 AC를 받았습니다.

1:08~1:54

kizen이 C 구현을 시작했습니다.
1솔 이상 나온 모든 문제의 풀이가 준비된 상황이었고 남은 문제는 D, E, G, I, K였습니다. 그 중 K가 가장 할만해 보여서 잡았고, K를 2~30분 정도 고민해서 풀이를 내는 데에 성공했습니다.
kizen이 C에서 TLE를 받았습니다. K 구현이 어렵지 않았기 때문에 C는 나중에 돌아와서 풀기로 하고 제가 K를 구현했습니다.
[1:54] K 구현을 마무리하였고 AC를 받았습니다.

1:54~2:44

kizen이 C를 최적화하기 위해 노력했습니다. 문제 특성상 상수가 굉장히 빽빽했기 때문에 조금 고전했습니다. 온갖 최적화와 커팅을 했는데도 계속해서 TLE가 났습니다. 결국 C는 나중에 돌아와서 다시 보기로 하고 kizen이 H를 구현하기 시작했습니다.
[2:44] H의 구현 난이도가 상당히 높았는데 kizen이 H AC를 한 번에 받았습니다.

2:44~3:27

leinad2가 E 구현을 시작했습니다. E가 기하 문제였지만 비교적 구현이 수월할 것이라고 했습니다.
E를 제출했으나 WA를 받았습니다. 그래도 풀이가 거의 확실했기 때문에 코드를 출력해서 눈으로 디버깅하면 충분히 맞을 수 있을 것이라 생각했습니다.
kizen이 G의 사풀을 떠올렸습니다. 각 index에서 끝나는 가장 긴 100개의 palindrome만 고려하는 방식이었는데, 직관적으로 반례를 만들기가 매우 어려울 것 같아서 구현하고 제출했지만 WA를 받았습니다. 이후 제가 조금 보완하여 가장 짧은 65개의 palindrome과 가장 긴 65개의 palindrome만 보자는 의견을 냈습니다(65라는 숫자가 크게 의미있는 것은 아닙니다).
[3:27] 이렇게 하면 정말 반례를 만드는 것이 거의 불가능할 것 같아서 제출했는데 AC를 받았습니다.

3:27~4:04

C를 디버깅하지 말고 제가 처음부터 다시 짜는 것이 나을 수도 있겠다고 생각했습니다. 보먼 볼수록 문제를 보고 나올 만한 풀이는 상당히 한정적인 것 같아서, 같은 풀이 내에서 캐시 히트를 최대화하는 것이 핵심일 거라고 생각했습니다. 그래서 배열 인자 순서나 for문 순서에 신경쓰면서 캐시 히트를 최대화하는 방향으로 코드를 새롭게 작성했습니다. 시간이 오래 걸리더라도, 한 번에 맞는 것이 중요할 거라고 생각했습니다.
제가 C 코드를 작성하던 중, leinad2와 kizen이 함께 E 코드를 읽으면서 디버깅을 진행했습니다. 결정적인 오류를 찾는 데에 성공했고, 제가 잠시 구현을 중단한 후 E 코드를 약간 수정했습니다.
[4:04] 몇 번의 수정을 거쳐서 E AC를 받았습니다.

4:04~4:11

[4:11] C 구현을 마무리했습니다. 제출하여 AC를 받았습니다.

4:11~5:00

이제 남은 문제는 D와 I입니다. D는 제가 PST를 이용한 루트로그 풀이를 떠올렸는데, 1초 안에 PST 루트로그가 돌 리가 없을 거라 생각하여 포기했습니다. I는 leinad2와 kizen이 사풀을 하나씩 떠올려서 둘 모두 구현해보기로 했습니다.
사실 간단하게 순위 계산을 해보았는데, 엄청난 이변이 일어나지 않는 이상 저희 우승이 거의 확정임을 확인하였고 그래서 조금은 여유로운 마음으로 임했습니다.
두 사풀을 모두 구현하기에는 시간이 부족할 것이라 판단해서 kizen의 사풀만 구현하기로 했는데, 끝까지 디버깅에 실패했고 결국 AC를 받지 못했습니다.

여담으로 I는 원래 사풀처럼 보이는 풀이를 짜면 의문의 보장으로 풀리는 문제이며, 그게 정해라고 합니다. 풀이 슬라이드에 2가지 풀이가 있었는데 풀이1이 kizen의 사풀, 풀이2가 leinad2의 사풀이었습니다.

마치며 (5:00~)

계산을 통해서 저희가 우승이라는 사실을 어느 정도 예상하고는 있었습니다. 프리즈 전까지 6솔이어서 걱정도 안 했던 문송송 팀이 10솔을 했다는 정보를 듣고 잠시 매우 당황했지만, 그래도 다행히 패널티 차이로 우승할 수 있었습니다.

팀연습 과정에서 제가 스스로 만족할 만한 기여를 하지 못한 적이 종종 있었습니다. 그렇기에 더욱, 팀원들에게 미안하지 않도록 좋은 실력을 보여주고 싶다는 생각이 컸던 것 같습니다.
하지만 오늘만큼은 제가 낼 수 있는 최선의 결과를 냈다고 생각해서 정말 뿌듯합니다. 만일 우승을 하지 못했더라도 제 자신에 대하여 후회하지 읺았을 것입니다.

팀원들 모두가 오늘 매우 잘해주었습니다.
leinad2는 무난한 난이도를 가진 많은 문제들을 빠른 속도로 해결해 주었으며, 구현 난이도가 매우 높은 E도 정확하게 구현해 주었습니다.
kizen은 거의 모든 팀이 패널티를 받은 H를 한 번에 정확하게 구현해 주었으며, G에서 반례를 만들기가 거의 불가능한 사풀 아이디어를 떠올렸습니다. 사풀 아이디어를 떠올리지 못했다면 G를 해결하지 못하여 우승하지 못했을 것입니다.

오늘의 우승이 저의 개인 기량에서만 비롯되었다고 절대 생각하지 않습니다. 최고의 팀원들, 응원해 주었던 주변 지인들, 그리고 약간의 운까지, 모든 것들이 최상으로 맞물려 얻은 값진 우승이라고 생각합니다. 우승을 차지했지만 앞으로도 갈 길이 멉니다. 자만하지 않고 월드 파이널에서도 좋은 결과를 거두기 위해 더욱 열심히 노력하겠습니다. 감사합니다.