내가 만든 문제 내가 리뷰 - 이상한 나라의 갈톤보드

대학교를 다니며 많은 동아리에서 활동하는 사람이 있다면 나는 적은 개수의 동아리에서 깊게 활동하는 편이였다. 그 중에서 알고리즘 동아리에서 활동을 제일 많이 했는데 1학년부터 4학년까지 꾸준히 활동했으면 대학 생활과 함께 했다 말해도 무방할 것 같다. 2학년에는 멘토를 3학년에는 부회장을 4학년에는 회장을 맡았는데 동아리 운영도 물론 중요한 일이지만 그만큼 중요한 것이 대회 운영이다. 알고리즘 동아리인 만큼 학과 학생을 넘어서 전교생이 참여하는 대회를 주기적으로 열었는데 문제를 출제하고 대회를 운영하는 것이 그 당시에는 힘들었지만 지금 생각해보니 보람찬 일이었던 것 같다.

오늘은 내가 만든 문제 하나를 같이 풀어보며 리뷰를 하면 재밌을 것 같아 "내가 만든 문제 내가 리뷰"라는 주제로 글을 쓸까 한다.

한 대회에 8-10문제 정도를 출제하기 떄문에 보통 개인당 1-2 문제를 출제한다. 사실 한 문제를 출제하는 것도 최소 30시간 이상의 막대한 시간과 노력이 들어가기 때문에 적다고는 할 수 없다. 나는 총 3문제를 출제하였는데 한 문제는 난이도도 낮고 대회의 밸런스를 위해 출제한 문제라 애정이 적다. 다른 두 문제 중 처음으로 출제한 문제를 풀어보자.

https://www.acmicpc.net/problem/24527

갈톤보드라는 특정한 문제 상황에서 구슬을 떨어뜨릴 때 이상한 나라의 갈톤보드는 도착지점에 모두 같은 확률로 떨어진다. 따라서 도착지점은 떨어뜨리는 지점에서 도착할 수 있는 모든 지점의 개수를 $K$라고 할 때 $\frac{1}{K}$의 기댓값을 가진다. 결국 이 문제는 빠르게 도착지점에 기댓값을 업데이트하는 것이다.

여기서 2가지 문제를 파악할 수 있다. 첫 번째는 어떻게 빨리 K개의 도착지점에 기댓값만큼을 업데이트할지이고, 두 번째는 도착 지점의 범위를 어떻게 빨리 구할 수 있을지이다.

첫 번째 문제부터 생각해보면 사실 잘 알려진 알고리즘인 세그먼트 트리를 이용할 수 있다. 물론 세그 트리를 사용할 수도 있지만 이 문제는 오프라인 쿼리라는 특징을 가진다는 점을 이용해 IMOS법을 이용하는 것이다. 만약 [s, e]의 구간에 a라는 값을 더해줘야한다면 s번째에 a를 더하고 e + 1번째에 -a를 더한 다음 앞에서부터 뒤의 값을 더해나가면 $O(N)$에 업데이트가 가능하다. 자세한 사항은 IMOS법을 검색해보자.

두 번째 문제를 생각해보면 구슬이 떨어지는 지점의 높이와 좌우 위치를 알면 도착하는 지점의 범위를 알 수 있다. 맨 윗층은 시작 지점이 1개 두 번째 층은 2개, 세 번째 층은 3개 ... 가 반복되므로 그냥 세는법도 있지만 각 층의 누적된 높이를 배열에 넣고 이분탐색을 lower_bound로 돌리면 더 빨리 위치한 층을 알 수 있고 그 값과의 차이를 이용하여 좌우 위치또한 알 수 있다. 따라서 높이가 $H$라고 할 때 $O(logH)$만에 높이와 좌우 위치를 구할 수 있다.

내가 작성한 정답 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum[100003];
double exp_val[100003];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int H, Q, R; cin >> H >> Q >> R;
    for(int i = 1; i <= H + 1; i++) sum[i] = sum[i - 1] + i;
    while(Q--){
        ll a;
        double b;
        cin >> a >> b;
        int h = lower_bound(sum, sum + H + 2, a) - sum;
        a -= sum[h - 1];
        h = H - h + 2;
        exp_val[a] += b / h;
        exp_val[a + h] -= b / h;
    }
    for(int i = 1; i <= H + 1; i++) exp_val[i] += exp_val[i - 1];
    for(int i = 1; i <= H + 1; i++) exp_val[i] += exp_val[i - 1];

    while(R--){
        int a, b; cin >> a >> b;
        cout << exp_val[b] - exp_val[a - 1] << "\n";
    }

    return 0;
}

이 문제에서는 위치가 정해지면 도착지점이 정해진다는 관찰. 이를 구하기 위한 최적화 과정. 도착지점을 업데이트하기 위해 오프라인 쿼리라는 사실을 캐치해 구현하기 어려운 세그먼트 트리보다 IMOS법을 찾아가는 법. 모두 출제할 때 계산에 들어갔었고 개인적으로는 만족스러운 문제가 출제되었다.

내가 문제를 출제할 때 원칙이 있다. 지식만으로 풀 수 있는 단순한 문제를 내지 말자. 관찰해야 풀 수 있는 나만의 문제를 출제하자. 처음 문제를 출제할 때라 많은 어려움이 있었던 것으로 기억한다. 재밌는 아이디어의 문제를 내기 위해 열 문제가 넘게 출제할 문제의 후보로 생각했었고, 그 중 최고라고 생각한 문제를 출제하게 되었는데 나름 엄밀한 문제를 내기 위해 지문과 정답 데이터에 많은 노력을 기울였다. 특히 검수진들의 엄청난 양의 피드백이 없었다면 대회 중에 문제에 대한 질문과 최악의 경우 문제를 대회에서 제외하는 일까지 일어났을 것이다.

혹시 아직 이 문제를 풀어보지 않았고 위에 해설을 이해하지 못했다면 한 번 풀어보길 권장한다. 당연하게 솔루션을 떠올릴 수 있어야하는 문제를 당연히 떠올리는 법을 배울 수 있을 것이다.