APIO 2025 후기

2025년 5월 17일에 진행한 APIO 2025 후기입니다.

선발고사가 끝난 이후로 PS를 엄청 열심히 했고 한국 6등 안이라는 게 또 엄청나게 비현실적인 성적은 아니라 APIO를 잘 봐서 메달을 따는 것을 목표로 했습니다.

문제 순서는 1번 Hack, 2번 Permgame, 3번 Rotate 입니다.

 

0:00 ~ 0:42 (8 + 0 + 0 = 8)

모든 문제를 이해하고 이 중 가장 간단해 보이는 1번 문제를 잡았습니다.

풀테는 어려워 보였기에 1, 2번 섭테를 한 번에 풀 방법을 생각해 봤습니다.

$N<=500000$이므로 $N$에 대한 이분탐색을 하면 될 것 같았습니다.

그래서 구현했으나 최악의 경우 비용이 $N+logN$개라 1번 섭테만 맞았습니다.

 

0:42 ~ 1:13 (8 + 0 + 16 = 24)

이후 3번을 봤습니다. 1, 2번이 애드혹같은 반면에 3번은 평소에 풀던 문제 같아서 바로 올바른 관찰을 해냈습니다.

수직인 두 직선을 만들면 이 두 직선을 제거해도 아무 문제가 없고 최대한 많은 수직 직선 쌍을 만들어야 한다는 관찰을 해냈고 이를 검증하기 위해 섭테 중 에너지 증가 조건을 무시해도 되는 2번 섭테를 풀었습니다.

 

1:13 ~ 1:41 (8 + 0 + 100 = 108)

관찰이 참이라서 이후에는 쉽게 할 수 있을 것 같았고 간단한 그리디를 떠올렸습니다.

이후 세그트리 + 셋질로 풀테를 구현했습니다.

많조분 + 셋질이라 구현이 좀 오래 걸렸지만 그래도 AC를 받아 좋았습니다.

3번 문제가 관찰이 그렇게 어렵지 않고 셋질이나 세그트리가 없는 풀이도 충분히 가능할 것 같아서 많은 사람이 풀었을 것으로 예상했습니다.

 

1:41 ~ 1:49 (8 + 6 + 100 = 114)

2시간 만에 2번을 처음 긁으려 했는데 서브테스크를 보니 $e > m$일때는 $p[i]=i$인 $i$ 개수가 정답 같아서 찍고 제출해서 맞았습니다.

증명은 풀고 나서 차수가 3 이상인 정점이 있을 때 문제가 생긴다는 것을 이용해서 바로 했습니다.

 

1:49 ~ 2:02 (8 + 12 + 100 = 120)

위 관찰로 인해 그래프가 사이클 혹은 path이어야 함을 알아냈고 m=2일 때는 트리이며 간선 하나를 swap 해줄 수 있어 모든 사이클을 없애줄 수 있음을 깨달았습니다.

이를 이용한 코드를 짰고 첫 번째 섭테를 긁었습니다.

 

2:02 ~ 3:00 (8 + 12 + 100 = 120)

3번째 트리 섭테를 노렸습니다.

길이가 긴 path면 한 사이클에서 최대한 빼는 것이 이득이라고 생각해 이를 구현해 줬으나 1시간 동안 AC를 받지 못했습니다.

 

3:00 ~ 3:38 (25 + 12 + 100 = 137)

1번으로 돌아왔고 두 번째 섭테를 긁을 방법을 생각하고 있었습니다.

첫 번째 섭테를 긁을 때 collisions 함수의 반환 값을 이용하지 않아 이를 이용한 풀이를 찾으려고 해봤습니다.

그러자 바로 $[1, 1000000]$에 대해 쿼리를 날린 결과물로 이분탐색을 하는 풀이가 나와서 긁었습니다.

 

3:38 ~ 4:19 (25 + 22 + 100 = 147)

swap을 통해 사이클이 합쳐질 수 있고 모든 사이클을 합쳤을 때 가장 큰 점수를 얻을 수 있음을 관찰해 이를 구현해 줬습니다.

 

4:19 ~ 5:00 (25 + 22 + 100 = 147)

1번과 2번을 동시에 고민했습니다.

2번은 크기가 3인 사이클에서는 최악의 경우 2만큼씩 사이클이 떨어져서 이를 계속 시뮬레이션하는 방법을 생각해 냈지만 구현해도 점수가 나오지 않았습니다.

그리고 대회가 끝난 직후에 구현이 틀렸다는 것을 깨달았습니다. ㅠㅠ

1번은 부분 수열의 합이 $[1, 1000000000]$ 구간의 모든 수가 되는 그러한 수열을 찾으면 부분 점수를 긁을 수 있어 이를 찾으려고 했으나 못했습니다.

약 팔기 문제처럼 하면 됐는데 이것을 생각하지 못하고 막 피보나치를 변형하나 n진법을 이용하나 이런 생각들밖에 하지 못했습니다.

결국 남은 시간 동안 아무런 점수도 긁지 못했습니다.

 

결론

147점을 받았고 대회가 끝난 날 지인들에게 열심히 물어봐 제 위에 점수 차가 크게 4명이 있다는 사실을 알아냈습니다.

6등 안에 들어야 상을 받아서 매우 애매한 점수 때문에 엄청나게 긴장됐습니다.

모든 대회가 그렇듯이 얻을 수 있는 점수를 모두 얻지 못한 게 또 너무 아쉬웠습니다. (2번 문제의 M=3 서브테스크) 

 

이후 성적이 나왔는데 한국 5등이었고 점수 분포를 보니 무조건 동메달 이상의 메달을 얻을 수 있었습니다.
한국 TOP 6은 순서대로 lumine_scence, mingyu331, namolbbaemi, turgon314, woohyun_jng, magic_spirit 가 됐습니다.
한국 5등은 지금까지의 저의 최고 등수라서 APIO 메달을 받을 수 있음이 기쁨과 동시에 지금까지 했던 노력이 의미가 있다는 것도 아주 기뻤습니다.

물론 엄청난 실력자 2명이 참여하지 않아서 운도 좋긴 했습니다.

 

공식 결과는 아직 나오지 않았지만 아마 동메달을 받지 않을까 싶습니다.

 

5/27: 동메달을 받았습니다.