UCPC 2026 본선 후기

당연히 본선에 나갔다.

---

대회 전

 

토요일 날 인턴을 수행하던 현풍에서 대전으로 겨우겨우 올라간 뒤 기숙사에서 잤다. 경북대 교환학생 갔을 시절엔 937번 타면 10분 만에 동대구역에 갔는데 여기는 같은 대구광역시에 급행8번 한 시간 겨우 타야 '편성이 적은' 서대구역에 도착할 수 있으니 어렵다. 

 

대전역에 도착한 후엔 유성온천이 궁금해서 하러 갈려 했다가 시간이 안되서 접고 버거킹을 먹은 뒤 특구1을 타고 KAIST 기숙사에 도착했다. 꽤 신식 건물인 비슬빌리지 & 경북대의 누리관과 비교하니 구식 느낌이 좀 많이 났고 거의 럭키진리관? 첫 번째는 공용샤워실 & 공용화장실이고 두 번째는 도어락이 고장나서 문이 안잠긴다는 거였다. 그래도 에어컨은 빵빵하게 틀 수 있어서 며칠동안 자기엔 좋은 곳이었다.

 

중간에 동아리 회장이 방에 놀러오기도 했고 뭐 여러 가지 일도 했지만 그리고 잤다.

---

대회 당일

10시 쯤에 대회장(정근모컨퍼런스홀)에 도착하니 Jane Street, HRT, Citadel에서 부스를 열고 기념품을 주고 있었다. 대충 도장을 다 찍어가니 빵 추첨으로 튀고구마를 줘서 먹고 대회장에 들어갔다.

 

노트북과 마우스는 내 맥북과 매직 마우스가 징발되었고, 멀티탭과 거리가 좀 있어서 보조배터리로 충전 준비를 했다. 다행히도 배터리 관리를 잘해서 중간에 컴퓨터가 꺼지는 일은 없었다. 

---

본선 타임라인

 

내가 EFGH를 잡았다. 나중에 난이도 커브가 공개되니 못풀만 한 문제들이었다.

 

L$($+0:30$)$

스코어보드를 보다가 내가 잡았다. 처음에는 약봉지가 문자열 형태로 주어질 때 BLDBLD...로 먹을 수 있는지 묻는 문제인 줄 알았는데 코드 다 짜고 출력을 해서야 알게 되었다. 그래서 대충 그리디로 짜니 AC

 

B$($+1:30$)$

매우 긴 숫자 N에 대해서 11로 나눈 나머지를 S라고 하자. 이때 숫자 a를 다른 숫자로 바꿀 수 있다면 나머지 변화는 ${-a, -a + 1, \cdots, -1, 0, +1, \cdots, 9 - a}$가 되고, 그렇다면 나머지 변화량의 개수는 총 10개이다. 즉, 홀수 자리 또는 짝수 자리에 배정된 숫자가 하나 $($a.....abab 또는 bab.....ab$)$여야 하며 a와 b는 각각 $S - 1$과 $10 - S$여야 한다. 그러므로 $f(S)$를 정의한 후 $f(B) - f(A) + ck(A)$를 정의하면 해결. Python으로 짜서 시간초과가 2번이나 났다.

 

C$($+3:40$)$

이건 내가 안풀어서 풀이를 모른다. 나머지 두 팀원이 같이 푼 걸로 안다.

 

D$($+4:01$)$

1번 트리를 루트로 두면 계층적인 구조가 나오며 어떤 parent 노드를 $X$라 하고 그 노드의 자식을 $x_1, x_2, \cdots$, 그리고 자식 노드들의 subtree 크기를 $S_{x_1}, S_{x_2}, \cdots$라고 하자. 그렇다면 $S = 1 +  \sum \limits_i S_{x_i}$이다.

 

여기서 $\mathbf{E}[x_i]$을 '$x_i$를 방문하기 전에 최초 방문할 노드들의 개수들의 기댓값'이라고 하자. 그렇다면 $\mathbf{E}[x_1]$의 값은 '부모 노드에서 기댓값 + 먼저 방문할 기댓값'으로 적절히 계산 가능하다.

 

---

결과

 

 

47등했다.