2026 국가대표 1차 선발고사 출제 후기

이번 선발고사에 출제한 문제들의 이야기를 들어보자. 스포일러가 다수 있다.

1. 균형잡힌 수열

문제 만들기

때는 군대에 있던 시절(언제였는지는 기억 안 난다) 중국 코드포스 라운드에서 998244353개의 양산형 특이한 꼴의 개수 세기 문제들이 나오는 것을 보고 나도 날먹을 하고 싶어서(...) 특이한 꼴을 만들었다. 그것이 바로 균형잡힌 수열인데, 생각보다 양산형 문제가 아니었고 쿼리를 넣었을 때 나름 재미있게 풀려서 문제 리스트에 넣어두고 있었다. 

문제 스케치

서브태스크 만들기

OI 계열의 문제를 만들려면, 서브태스크를 만들어야 한다. $Q=0$은 당연히 들어가는 서브태스크이다. $O(NlogN)$에 푸는 것이 자명하지 않을 수 있기 때문에 $O(N^2logN)$에 문제를 푸는 서브태스크도 만들어줬다. $A_i \le 3$이면 균형잡힌 수열의 형태가 간단해진다. 길이가 $1$이거나, 길이가 $3$이고 $a_0 < a_1 > a_2$를 만족하거나, 길이가 $7$이고 $[1, 2, 1, 3, 1, 2, 1]$인 경우 밖에 없다. 그래서 $Q=0, A_i \le 3$에 대한 서브태스크를 넣었고, 정해의 일부로 들어가는 셋질을 추가해 $A_i \le 3$ 서브태스크를 추가했다. 

 

사실 나이브한 풀이가 $O(QNlogN)$ 밖에 없는줄 알고 더 서브태스크를 만들지 않았는데, 한 원소가 바뀌면 그 원소를 포함하는 길이 $2^k-1$의 구간이 최대 $2^k-1$개밖에 없다는 사실을 이용해서 쿼리당 $O(N)$에 문제를 해결하는 방법이 있다는 것을 대회 전날에 깨달았다. $Q$ 범위를 $1000$ 정도로 하는 서브태스크가 있었으면 어땠을까 하는 생각이 들었지만, $O(NQ)$와 $O(QNlogN)$은 구분하기 어려웠을 것 같기도 하다.

 

참고로, $O(NQ)$ 풀이가 bitset으로 최적화가 가능하다. 그래서 $O(NQ/64)$ 풀이가 돈다. 이 사실을 좀 더 일찍 알았다면 $Q$ 범위를 키웠겠지만, 전날에 문제에 큰 변화를 일으키면 문제에 오류가 생길 확률이 높아지기 때문에 그러지 못했다. 더 빠른 나이브 풀이를 생각하지 못한 것에 후회가 된다.

 

데이터 만들기

이 문제는 데이터 만들기가 어려웠다. 랜덤하게 데이터를 찍어내면, 긴 균형잡힌 수열이 전혀 나타나지 않는다. 그리고 긴 균형잡힌 수열이 있다고 해도, 중간에 하나의 원소만 바꿔도 균형잡힌 수열이 사라진다.

 

살짝의 꼼수를 썼는데, 균형잡힌 수열이 많은 수열 $A$를 초기에 만들고, 변형 쿼리를 줄 때 $A \rightarrow A' \rightarrow A$를 반복하는 것이다. 이러면 기존의 균형잡힌 수열이 많은 $A$가 중간에 여러 번 등장하고, 각 쿼리당 생기거나 사라지는 균형잡힌 수열의 개수가 많아진다. 틀린 풀이를 시간초과를 내는데 이러한 데이터들이 많은 도움을 줬다.

 

이런 데이터는 단점이 있다. 여러 쿼리를 한 위치에 주기 때문에, 캐시히트가 높다는 것이다. 그래서 쿼리를 여러 곳에 분산해서 주고 싶었다. 그런데 쿼리로 수열이 변형되는 과정에서도 수열에 균형잡힌 수열이 많았으면 좋겠다는 바람이 있었다.

 

더 생각을 해봤는데, 쿼리 처리 시 $A_p$ 값이 많이 변하면 전후 모두 위치 $p$를 포함하는 균형잡힌 수열이 많기 힘들다. 그래서 $A_p$ 값을 바꾸지 않는 쿼리($A_p = A_p$)를 넣어 TLE를 유도했다! 따라서 균형잡힌 수열이 많은 수열 $A$를 초기에 만들고, 변형쿼리로 그냥 $A_p = A_p$를 줘서 TLE를 유도할 수 있다는 것을 알아냈다. 하지만 이런 테스트케이스는 쿼리 이전과 이후의 값의 변화가 없으면 쿼리를 무시하는 최적화에 무력해지기 때문에, 기존 $A$의 모든 원소에 100을 곱하고 쿼리를 줄 때마다 $A$의 원소의 일의 자리와 십의 자리를 임의로 바꿔주는 데이터를 만들었다. 이러면 수의 상대적인 위치는 변하지 않지만, 그 사실을 알기 쉽지 않기 때문에 고능한 데이터를 만들 수 있었다. 덕분에 매우 빨라보이는 $O(NQ)$를 막을 수 있었다.

 

별해

내 풀이는 셋을 사용해 각 길이의 균형잡힌 수열의 위치를 찾아내 로그가 붙었지만, 그냥 재귀적인 방법으로 균형잡힌 수열의 위치를 찾으면 로그가 사라진다는 것을 검수진 중 한 분이 찾아주셨다. 그래서 $O((Q+N)logN)$의 풀이가 완성된다. 이걸 일찍 떠올렸으면 bitset이나 simd와 같은 풀이들을 제거할 수 있었을 것 같은데, 아쉬움이 남는다.

 

대회장

적당히 쉬운 문제 포지션으로, 많이 풀렸다. 마지막 서브태스크를 제외하고 대부분의 사람이 풀었으니, 실질적인 점수가 36점인 쉬운 문제라고 생각한다.

 

2. 격자 트리

문제 만들기

군대에서 휴가 전날에 할 것이 없어 문제를 만들고 있었다. 이진트리를 격자판 위에 올리고 싶은데, 그냥 올리라고 하면 쉬울테니 중간에 직사각형을 쿼리로 줘서 해당 직사각형 내부에 정점이 없도록 트리를 격자판 위에 올리는 문제를 만들고 있었다.

문제 스케치

 

트리를 적당히 반으로 나눠서 절반은 왼쪽에 최대한 붙이고, 절반은 오른쪽에 최대한 붙이면 된다는 생각을 했었다. 그런데 문제가 생각보다 잘 풀리지 않았고, 직사각형이 없는 경우에도 굉장히 어렵다는 사실을 깨달았다. 문제 조건에 각 리프의 깊이가 같다는 조건을 추가하고, 직사각형 쿼리를 제거해서 풀기 시작했다. (현재 문제의 서브태스크 3과 같은 문제이다)

 

현재 서브태스크 3에 해당하는 문제의 필요충분조건은 대략 짐작을 했는데, 증명을 할 방법이 떠오르지 않았다. "가장 왼쪽에 트리를 붙이기"와 같은 전략은 생각보다 어려웠고, 오랜 시간 고민을 하게 되었다. 그러다 서브트리가 각 층에서 포함하는 최소 너비를 dp로 저장할 수 있고(너비 수열이라고 하자), 두 너비 수열을 합칠 수 있다는 것을 깨달았다. (합치는 과정이 자명하지 않은 것이, 합쳐진 너비 수열에서 나오는 임의의 껍질에 대해 자식의 너비 수열에 대한 껍질을 분리해낼 수 있어야 한다) "가장 왼쪽으로 트리를 넣는다"라는 직관을 포기해야만 나올 수 있는 이 풀이가 너무 아름다웠다. 더 생각을 해보니 경로의 길이를 고정하는 것이 아니라 일정 값 이상으로 하는 조건으로 바꿔도 문제가 성립했고, small to large를 섞으면 $O(Nlog^2N)$에도 풀렸다.

 

2025 IOI call for task에 이 문제를 투고했다. 서브태스크의 개수를 늘리기 위해 각 경로의 길이가 고정되어 있는 경우에 system of difference equation을 사용하는 $O(N^3)$ 풀이도 추가하고, 트리를 구성하는 서브태스크도 추가해 모든 경로의 길이 최소가 $1$인 경우 (이때는 깊이가 리프의 개수인 트리를 구성할 수 있다)의 서브태스크도 만들었다. 그러나 "격자 트리"라는 대상이 비직관적이고, system of difference equation이라는 서브태스크가 ioi에 나오기에 예쁘지 않다는 평을 받고 반려되었다. 그리고 당시 경로 길이가 고정인 서브태스크의 필요충분조건은 system of difference equation의 그래프에서 음수 사이클의 여부를 가지고 증명했기 때문에 "필요충분조건을 유추해서 푸는 서브태스크"에 불과했다.

 

선발고사에 낼 때는 서브태스크를 변형했다. 안 좋은 평가를 받았던 system of difference equation 서브태스크를 제거했다. 구현을 줄이기 위해 트리 구성 서브태스크를 버렸다. 그리고 결정적으로 경로 길이가 고정인 서브태스크의 새로운 증명을 완성했다. 그렇게 해서 지금 형태의 문제가 완성되었다.

데이터 만들기

이 문제 데이터 만드는데 굉장히 고생을 했다. 간선의 길이가 길어지면 단순히 리프의 최대 깊이가 정답이 되고, 그렇다고 간선의 길이가 짧아지면 리프 개수가 정답이 된다. 서브태스크 3은 리프의 깊이들이 모두 같아야 하기 때문에, 데이터를 열심히 만들어야 했다.

 

일반적으로 랜덤하게 트리를 만드는 방법은, $i$번 정점의 부모를 $0$번부터 $i-1$번 중 적당한 랜덤 분포를 골라 정하는 것이다. 그러나 우리가 만들고 싶은 트리는 각 정점은 자식이 $0$개 또는 $2$개이어야 했다. 따라서 새로운 방법이 필요했다.

 

$\frac{N-1}{2}$개의 정점은 리프가 아니다. 정점 개수가 $\frac{N-1}{2}$개이고 각 정점의 자식 개수가 $2$개 이하이도록 트리를 구성한다. 이후에 $\frac{N+1}{2}$개의 정점을 각 노드의 자식으로 추가해 리프가 아닌 모든 정점의 자식이 $2$개가 되도록 한다.

 

자식이 $2$개 이하인 트리는 어떻게 만들까? 기존의 정점을 (2 - 자식 개수)번 담은 컨테이너에서 랜덤하게 정점을 골라 부모로 삼으면 된다. 컨테이너 크기가 $t$라면, $0$과 $t-1$ 사이의 임의의 분포를 사용해 인덱스를 고르고, 컨테이너에 있는 인덱스번째 정점을 고르면 된다. 컨테이너로는 fenwick tree가 적당하다. 이제 random한 tree를 만들 수 있게 되었다.

 

Subtask 3은 조금 다른 방식을 사용해야 하는데, 모든 정점의 깊이가 같아야 하기 때문이다. 모든 리프 정점을 $x+y=k$에 고정하고, 부모를 랜덤한 방향으로 정해서 정답이 yes인 트리를 만드는 generator을 만들었다. no를 만드는 것은 좀 어려운데, 너비 수열을 적당히 재귀적으로 쪼개주는 방식을 선택했다. (적당히가 어려운 부분이다)

 

ㄹㅈㄷㅋㅋ

 

generator를 엄청 만들었다. 좀 힘들었다. 대회 전날에 검수진이 데이터를 추가해줘서 고마웠다. 

별해

마지막 서브태스크를 small to large가 아니라 dynamic segment tree를 사용해서 푸는 별해가 존재한다. 정확히 어떤 풀이인지 이해하지 못했지만, 구현이 어려워보였다.

대회장

최상위권 학생들이 균형잡힌 수열과 멋진 구간 2를 풀고 이 문제를 계속 붙잡고 있는 것을 볼 수 있었다. 아마 서브태스크마다 주는 점수가 커서 그런 것 같다. 1명이 만점, 2명이 68점, 2명이 39점을 받은 것을 보면 적당히 어려운 상위권 문제였다고 생각한다.

 

마무리

앞으로도 재미있는 문제들을 많이 만들고 싶다.