ICPC 2025 예선 후기

서론

이거 쓰려고 블로그를 팠다.
원래 8월 초까지도 아직 내가 초보라고 생각해서 나갈 생각이 없었다.
그러다가 기회가 4번 정도밖에 없다고 생각해서 동방에서 팀을 모집하고 있던 chang06과 blackkarn과 참가하게 되었다.
본선 진출까지가 계획에 있었기 때문에 팀노트도 남들은 tex로 정교하게 작성한 반면 우리 팀은 docs 파서 3일 전부터 짰다.

대회

대회 전

cpp에 scanf를 쓰는 사람은 처음 봤다.
컴퓨터도 놀랐는지 팀 연습 중에 실행 파일을 바이러스로 감지해서 작동을 안 했었고, 대회 끝날 때 까지 방화벽을 끈 상태로 진행을 했다.

0:00

시작하자마자 3개로 분류했고, 한국어 먼저 읽기로 했다.
내가 A, chang06이 F, blackkarn이 I를 맡았다.

0:08 (F, WA)

chang06이 처음으로 가져가서 풀었다가 실패했다.
처음부터 WA를 받아서 멘탈이 털릴 법도 한데 전날 돌았던 셋들 덕분에 그나마 나았던 것 같다.

0:13 (I, AC, First)

F WA 이후 blackkarn이 가져가서 풀었다. 심지어 퍼솔을 했다.
이후에 보니 전형적인 경시 수학 문제 스타일이어서 빨리 풀 수 있었을 듯 하다.
보통 A를 가장 많이 풀었던데 이때까지 나는 A의 그리디가 가능한 지를 계속 고민하고 있었다.

0:17 (F, AC)

chang06이 결국 다시 가져가서 풀었다. 사실 나는 A에 집중하고 있어서 뭘 고쳤는지는 모른다.

0:32 (A, AC)

A가 그리디함을 90% 확신하고 blackkarn에게 확인받고 2차원 dp를 통해 풀었다.
확실히 2분 퍼솔이 나올 만한 문제였다.

1:11 (H, AC)

chang06이 대충 풀 수 있을 것 같다 한 후에 가져가서 풀었다.
예제부터 안 나와서 좀 고생했는데 잘 풀었다고 한다.
이때 동안 그나마 만만해보이는 C와 D, J를 blackkarn과 같이 고민하고 있었다.
이걸 맞을 당시에 1n등이었던 것으로 기억한다.

1:22 (J, 3WA)

blackkarn이 사각형인 회로가 존재하기만 하면 된다고 했고, dfs 트리를 통해 판별하고자 했다.
그래서 트리의 부모의 부모의 부모와 연결되어있으면 되지 않겠냐고 했고, 틀렸다.
이를 고치는 동안 chang과 D를 버리고 C, E, J를 고민하고 있었다.

테스트로 한 번 더 제출했는데 틀렸다.
나는 그냥 두 점 잡아서 나이브하게 돌리는 방법을 말했는데, 뭔가 찝찝해서 계속 다른 반례를 찾기로 했다.
이 무렵, C에서 그냥 우주선 중간의 점들을 잘 압축하면 되는거 아니냐는 아이디어를 던졌다.
가능한 지는 둘째치고, 얼마나 줄여야 할 지도 잘 몰랐다.

자신과 2대 위 부모가 연결되고 자신의 부모와 3대 위 부모가 연결되는 이상한 반례를 찾았다.
이를 추가해서 제출했고 틀렸다.
이후 꽤 케이스가 많은 반례가 나와서 dfs를 포기하고 나에게 키보드를 넘겼다.
이후 나는 C를 정리한 후에 풀려고 코드를 적었다.

2:27 (J, AC)

C를 적던 중에 맨탈이 터졌다.
우주선의 순서와 넘어가는 범위를 다 신경써야 하는, 백준에서 나오면 무조건 넘기는 많조분이였다.
그래서 70% 정도를 적고 그나마 정신적으로 이로운 J를 내가 말한 방식대로 풀고, 운 좋게 AC를 받았다.

2:53 (C, AC)

C만 풀면 6솔이고, 프리징이었지만 6솔 컷이 거의 우발 컷이여서 이걸 풀어야만 했다.
앞에 있는 팀은 잘 떠들고 있던데 굉장히 부러웠다.
chang06이 E에서 N log^2 N 풀이를 찾았다는데 시간상 불가능하다고 하여 C에 집중하기로 했다.
옆에서 팀원들은 개쩌는 반례를 손으로 만들었고, 코드 오류를 찾는데 꽤 도움이 됐다.
결국 7분 남기고 정제되지 않은 풀이를 일단 제출 했는데 운 좋게 맞았고, 남은 7분동안 자축하며 있었다.

후기

팀 대회로써는 처음이고, 일반 대회로서도 Matkor 7회를 제외하면 처음이어서 확실히 보완해야할 점이 많이 보였다.
다행히도 역대급 고점이 터져, 본선 30등 안에 들 수 있게 되었다. 코포를 좀 열심히 해야겠다.