2025 인하대학교 프로그래밍 경진대회 (IUPC) 참가 후기

Let lapinism win shake!

---

IUPC라는 대회를 알게 된 건 22년 봄입니다.
그땐 막연히 "졸업 전에 한번 우승해 보고 가야겠다"라며 생각했었는데, 다행히도 올해 그 목표를 이뤄냈습니다.

지금 생각해 보면 운이 잘 따라준 부분이 많았습니다.
예제 입력이 아니었으면 최소 1시간은 삽질했을 문제(K)가 있었고,
못 풀고 있다가 뜬금없이 방법이 떠오른 문제들(G, H)이나,
겨우 버그를 잡아낸 문제(F)가 그렇습니다.

다음은 shake! 일 텐데, 이런 걸 보면 아직 한참 부족한 것 같습니다.
코드포스든, 앳코더든, 경험을 다양하게 쌓아야 할 필요성이 느껴지네요.

느낀 점도 많고, 전체적으로 재밌는 대회였습니다.

아래는 대회 타임라인입니다.
일부 문제의 스포일러가 포함되어 있습니다.

~0:03 A (+)
~0:09 B (+)
~0:16 C (+)
첫 3문제는 가장 쉬운 문제라고 하길래, 첫 3문제를 먼저 풀고 나머지를 차례대로 보려고 했습니다.
A번이 최근 나온 A번 중에선 어려웠어서...
증명 없이 제출해서 AC를 받고 넘어갔었네요.

~0:23 E (+)
차례대로 D를 봤는데... 당장 풀이가 나오진 않아서 다음 문제인 E를 잡았습니다.
빠르게 백트래킹을 짜서 AC를 받고 넘어갔습니다.

~0:30 F
F를 보자마자 이 문제가 먼저 떠올랐습니다.
서브트리 루트 기준으로 좌우 나눠서 뭔갈 하면 되겠다 싶었는데, N이 20만이라 일단 나중에 생각하기로 했습니다.

~0:50 I
G, H를 차례대로 봤지만 당장 풀이가 떠오르지 않아서 I번까지 왔습니다.
보자마자 반가웠습니다. 최근 IUPC에서 기하 문제가 많이 없길래 기하를 준비했었는데, 그게 적중했습니다.
요구하는 바도 명확해서 바로 풀려했는데... 예제가 안 돌아갔습니다.
30분 가까이 디버깅했지만, 이유를 찾지 못해 일단 넘어갔습니다.

~1:00 J (+)
문제의 J번입니다.
의도한 풀이는 2D BFS였다고 하지만, 시간을 1씩 증가시키며 매번 BFS를 돌리면 되겠다 싶어 바로 AC를 받았습니다.
문제는... 스코어보드에서 E번 다음으로 풀린 게 J가 되어, 12문제 중 5번째로 풀린 문제가 되었습니다.
이 때문에 많은 사람들이 더 쉬운 문제 대신 J를 도전했다고 들었고, 이 문제로 평균 솔브수가 떨어진 것 같다고 합니다.

~1:11 K (+1)
문제를 읽는 데 시간이 꽤 걸렸습니다.
문제를 이해하니 요구하는 건 단순한 그리디여서 확인해 봤지만... 이것도 예제가 안 돌아갔습니다.
다행히 e - s + 1 > k인 경우가 문제임을 찾아냈습니다. 예제가 없었다면 알아내는 데 최소 1시간은 썼을 것 같네요.
한번 틀린건 중간에 배열 크기를 잘못 잡고 제출했어서...

~1:33 I (+)
L은 지금은 풀 수 없음을 직감해서, 다시 I로 돌아왔습니다.
아까 짰던 게 대체 뭐가 문제인지 알 수 없어서, 처음부터 다시 짜기로 했습니다.
결과는 AC. 처음에 구현했던 거랑 똑같이 짰는데, 어디선가 오타를 냈던 것 같네요.

~1:59 D (+)
I를 해결하고 스코어보드를 확인하니 D에 제출이 몰려 있었습니다.
혹시나 내가 놓친 게 있을까 봐 문제를 다시 확인하니 '최단 거리'라는 조건을 그제야 확인했습니다.
최단 거리가 아닐 때를 가정하고 복잡하게 생각했던 거라... 문제 좀 꼼꼼히 읽을 걸 그랬네요.
처음에는 최댓값만 확인하는 DP를 짰는데 예제가 안 돌아서, 최소도 같이 보는 DP를 짜서 AC를 받았습니다.

~2:57 F (-1)
~3:10 F (-2)
남은 문제 중 정답에 가장 가까웠던 F를 잡았습니다.
풀이를 설계해 보니 "구간에서 x 이하의 값이 처음 등장하는 위치"를 O(lgN)에 찾는 문제임을 확인했습니다.
이걸 세그먼트 트리로 한 번에 O(lgN)로 짜려고 했다가... 30분 정도를 날렸습니다.
그냥 세그먼트 트리에서 이분 탐색으로 O(lg²N)에 돌아가는 풀이를 짰는데...
결과는 WA. 디버깅 이후 제출도 WA를 받습니다.

~3:17 H (+1)
F에서 흔들리다가 갑자기 H번에 비둘기집 원리가 떠올랐습니다.
m을 n개씩 끊어서 보면 n개를 모두 채우는 동작을 m/n번 한다는 걸 확인했습니다.
결국 구하는 건 m/n의 홀짝성에 따른 동작임을 확인했고, 이를 구현해 AC를 받았습니다.
한번 틀린 건 m/n의 홀짝을 직접 나눠 구하는 풀이를 제출해서 틀렸습니다. (왜 그랬지)

~4:35 G (+)
H를 풀고 나니 누군가가 G에서 AC를 받아오길래 어쩌면 풀 수도 있겠다 싶어 G를 잡았습니다.
수십 분 동안 진전이 없다가 (i + j) % 3 값이 같으면 서로 인접하지 않다는 걸 확인했습니다.
여기서 다시 막혔었는데, 그냥 개수가 가장 많은 수부터 넣으면 되지 않을까 싶었습니다.
그걸 구현하니 AC를 받았습니다. 풀고도 이게 맞나 싶어서, 다른 사람의 풀이가 궁금했던 문제였네요.

~4:38 F (-3)
~4:42 F (+3)
이때 남은 문제는 F, L이었고, 남은 시간 모두를 F에 쓰기로 했습니다.
I처럼 처음부터 다시 짜기엔 시간이 없었고 반례를 찾기 위해 가능한 모든 입력을 넣어봤습니다.
그러다 오른쪽 서브트리를 처리하는 함수에 문제가 있는 걸 확인했고, 틀린 부분도 결국 찾아냈습니다.
오른쪽을 구해야 할 위치에 왼쪽을 구하는 함수가 대신 적혀있었고, 이걸 수정해 AC를 받았습니다.
1초라서 로그제곱이 안 될 줄 알았는데, 880ms로 겨우 뚫어냈네요.

~4:59 L (-1)
L은 시간 내에 못 풀 것 같아서, 편지를 남기기로 했습니다.

---

대회 중 L번에 제출한 소스코드

좋은 대회를 준비 및 운영해 주신 운영진과 관계자 모든 분께 감사드립니다!