UCPC 2026 예선 출제 후기

이번에 전대프연의 임원을 하게 되어 출제 과정에 관여하게 되었다. 그 과정에서 내가 내고 싶은 문제를 냈다. 예선 G번 레이저 타워를 내게 되었다. 문제를 만든지 오래 되어서 출제 과정이 잘 기억이 안 난다. 그래서 짧게 작성한다. 문제는 여기에서 풀어볼 수 있다.

문제 지문

6솔브가 나온 적당히 어려운 문제이다.

 

 

이 문제를 낸 것은 적어도 1년은 되었다.

디스코드 문제 저장소를 만들었을 때 처음에 등록된 몇 문제 중 하나이다

군대에서 끄적였던 노트. 더 자세히 쓰여있는 것은 못 찾겠다

 

다른 문제들에게 출제 순서를 밀려 아직까지 세상에 안 나왔다가, 이번 ucpc에 나오게 되었다.

 

2^S의 기댓값을 구하라는 것과, 타워의 높이가 순열이라는 세팅이 조금 인위적인 것 같았다. 문제를 덜 인위적으로 만들기 위해서 S의 기댓값을 구하는 것으로 문제를 변경할까 생각했다. 하지만 S의 기댓값을 구하는 것은 매우 쉽다. [x, x+1]에서의 높이의 기댓값이 sum (N-i) * 1/2^(i+1)로 모든 x에 대해서 같기 때문이다. 

 

i번 타워가 레이저를 오른쪽으로 쏠 확률이 p_i일 때, S의 기댓값을 구하는 버전의 문제도 있다. 이건 자료구조 비빔밥이다. 현재 버전보다 별로인 것 같아서 버렸다.

Gemini와 놀기 1

 

여담으로 기존에 x의 범위가 [1, N]이었다. 그러나 재귀함수를 호출할 때 구현이 조금 까다로워지는 것 같아서 범위를 [0, N+1]으로 바꿨다.

Gemini와 놀기 2

 

나름 괜찮은 문제로 나온 것 같아서 기분이 좋다.