SCPC 2021 1차 예선에 참가했습니다 (1/3)

1차 예선 — 800/800

올해는 예년보다 문제들이 쉬워진 느낌이었습니다. 다섯 문제를 전부 풀었습니다.

제 풀이를 공유합니다.

1차 1번 – 친구들

사람이 $N \leq 100\,000$명 있습니다.

번호 $i$인 사람은 수 $D_i$를 갖고 있는데, $i + D_i \leq N$라면 $i$번 사람과 $i + D_i$번 사람은 친구입니다. 또, 친구의 친구는 친구입니다.

이 때, ‘극대 그룹’의 수를 찾아야 합니다.


친구 관계를 그래프로 생각해 봅시다. ‘친구의 친구가 친구‘라는 말을 잘 생각해 보면, 어떤 연결 요소 안의 모든 사람들은 서로 친구가 됩니다.

따라서 DFS/BFS 여러 번을 통해 연결 요소의 수를 세 주면 문제의 답이 됩니다. 또는 DSUdisjoint set union를 사용해도 됩니다. DFS/BFS를 사용하면 $\mathcal{O}\left(N\right)$만에 해결할 수 있습니다.

저는 DSU를 사용해서 풀었습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int dsu[100001];

int find(int u) {
    return dsu[u] == u ? u : (dsu[u] = find(dsu[u]));
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) dsu[v] = u;
}

void solve() {
    int n;
    cin >> n;

    iota(dsu + 1, dsu + 1 + n, 1);

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (i + x > n) continue;
        merge(i, i + x);
    }

    set<int> s;
    for (int i = 1; i <= n; i++) s.emplace(find(i));
    cout << s.size() << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

DSU를 만들 때 std::iota라는 좋은 함수를 사용하면 쉽고 빠르게 초기화할 수 있습니다. STL에 이런 함수가 있다는 게 좀 의외일까요?

1차 2번 – 이진수

길이가 $n \leq 50\,000$인 비트 문자열 $a$가 있고, 같은 길이의 비트 문자열 $b$를 다음과 같이 정의합니다. $\vee$는 OR 연산입니다.

\[b_i = \left(a_{i-t} \vee a_{i+t}\right)\]

$b$가 주어지면, 사전순으로 제일 앞서는 $a$를 구해야 합니다.


약간 헤멜 수 있는 문제였던 것 같습니다. 일단 두 가지 사실을 기반으로 생각해봅시다.

  • $b_i$가 켜져 있다면, $a_{i-t}$ 또는 $a_{i+t}$가 켜져 있어야 합니다.
  • $a_i$가 켜져 있다면, $b_{i-t}$와 $b_{i+t}$가 모두 켜져 있어야 합니다.

이제 $b_i$를 왼쪽부터 보면서, 켜져 있으면서 아직 $a_{i-t}$와 $a_{i+t}$ 모두가 꺼져 있는 $b_i$들에 대해, 그리디하게 $a$의 비트들을 켜 줍니다.

  • 오른쪽($a_{i+t}$) 비트를 켤 수 있으면 켜 줍니다. 오른쪽 비트를 켤 수 있으려면, $b_{i+2t}$가 존재하지 않거나 켜져 있어야 합니다. 이는 사전 순으로 가장 먼저 오는 $a$를 구성하기 위함입니다.
  • 오른쪽 비트를 켤 수 없다면 왼쪽($a_{i-t}$) 비트를 켜 줍니다.

생각해 보면 모든 $b_i$에 대해 둘 중 하나 이상을 켤 수 있는 경우만 입력으로 주어진다는 사실을 알 수 있습니다. 이를 그대로 구현해 주면 됩니다. $\mathcal{O}\left(n\right)$만에 해결할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

void solve() {
    int n, t;
    cin >> n >> t;

    string b;
    cin >> b;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        if (b[i] == '0') continue;
        int l = i - t, r = i + t;
        if ((l >= 0 && a[l]) || (r < n && a[r])) continue;

        int ll = l - t, rr = r + t;
        if (r < n) {
            if (rr >= n || b[rr] == '1') {
                a[r] = 1;
                continue;
            }
        }
        if (l >= 0) {
            if (ll < 0 || b[ll] == '1') {
                a[l] = 1;
                continue;
            }
        }
    }
    for (int i = 0; i < n; i++) cout << a[i];
    cout << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

1차 3번 – No Cycle

정점 $N \leq 500$개, 간선 $M+K$개의 그래프가 있습니다. $M+K$의 간선 중 $M \leq 2\,000$개는 방향이 있고, $K \leq 2\,000$개는 방향이 정해지지 않았습니다.

이 때 $K$개의 간선들의 방향을 잘 정해서, 사이클이 없는 그래프를 구성하고 싶습니다. 방향이 정해진 $M$개의 간선들만 있는 경우에는 사이클이 없는 상태입니다.

답은 $K$글자의 비트 문자열입니다. 방향이 없는 $i$번째 간선의 입력이 $\textcolor{#ff3b57}{u}$ $\textcolor{#ffb717}{v}$로 주어졌을 때, $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$로 방향을 정했다면 $0$, $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 방향을 정했다면 $1$입니다. 이 때 사전 순으로 가장 앞서는 비트 문자열을 출력해야 합니다.


사이클이 없는 방향 그래프에서, 임의의 정점 $\textcolor{#ff3b57}{u}$와 $\textcolor{#ffb717}{v}$를 고르고 그 정점을 잇는 간선을 추가한다고 생각해 봅시다. $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$로 정할 수도 있고 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 정할 수도 있습니다. 두 경우 모두가 사이클을 만드는 경우가 있을까요?

$\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$라는 간선을 추가했을 때 사이클이 생긴다는 것은, $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 가는 경로가 이미 존재한다는 사실과 동치입니다.

따라서 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$도 사이클을 만들고 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$도 사이클을 만든다면, 각각 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$라는 경로와 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$라는 경로 모두가 이미 존재해야 됩니다.

하지만 그런 두 개의 경로가 이미 존재한다면, 그 두 개의 경로만으로 사이클을 만들 수 있습니다. 이는 우리가 처음에 한 가정 — 사이클이 없는 방향 그래프 — 에 모순됩니다. 따라서 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$와 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$ 중 적어도 하나는 새로운 사이클을 만들지 않는다는 사실을 알 수 있습니다.

그러므로 이미 사이클이 없는 방향 그래프라면, 간선들을 무한정 추가해줄 수 있습니다. 그래프의 정점과 간선의 수가 작기 때문에, 간선을 추가해줄 때마다 사이클이 생기는지 생기지 않는지 확인하면서 간선을 하나씩 추가해나갈 수 있습니다.

사전 순으로 가장 앞서는 비트 문자열을 구성해야 하므로, 우선 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$를 추가한 뒤 사이클이 안 생긴다면 그대로 가져갑니다. 사이클이 생긴다면 위의 증명을 통해 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$를 추가해줄 수 있음이 보장된다는 것을 알 수 있으므로, 그렇게 해 줍니다.

사이클의 존재 여부를 판단하는 방법은 여러 가지가 있습니다. 저는 DFS로 구현했습니다. 그래프가 연결 그래프임은 보장되지 않으므로, 방문하지 않은 모든 정점에서 DFS를 시작해야 함에 유의합니다.

간선을 $K$개 추가해 주고, 추가할 때마다 DFS를 한 번 해야 하므로 $\mathcal{O}\left(K\left(N+K+M\right)\right)$의 시간이 걸립니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

bitset<501> root;
int vis[501], ans[2000];

bool dfs(int u, const vector<vector<int>> &graph) {
    // check for cycles
    if (vis[u]) return vis[u] == -1;
    vis[u] = -1;
    for (int v : graph[u]) {
        if (dfs(v, graph)) return true;
    }
    vis[u] = 1;
    return false;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    root.reset(), root.flip();

    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v);
    }
    
    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;

        // 0?
        graph[u].emplace_back(v);
        memset(vis, 0, sizeof vis);
        bool flag = true;
        for (int x = 1; x <= n; x++) {
            if (vis[x]) continue;
            if (dfs(x, graph)) {
                flag = false;
                break;
            }
        }
        ans[i] = !flag;
        if (flag) continue;
        
        // 1?
        graph[u].pop_back();
        graph[v].emplace_back(u);
    }

    for (int i = 0; i < k; i++) cout << ans[i];
    cout << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

1차 4번 – 예약 시스템

$2 \times m$개의 방이 있는 호텔이 있습니다. $m \leq 50\,000$입니다.

$n\leq 20\,000$개 그룹의 투숙객들이 호텔에 묵으려 합니다. 각 그룹의 크기는 $5$ 이상이고, 한 명이 한 개의 방에 묵습니다.

모든 투숙객들은 스트레스 지수 $w_i$를 갖고 있어서, 인접한 방에 다른 그룹의 투숙객이 있고 그 투숙객의 스트레스 지수가 $w_j$라면, 그 쌍에 대해 $w_i + w_j$만큼의 충돌이 발생합니다. 모든 쌍에 대해 충돌의 합을 최소화하고 싶습니다.

(그냥 이렇게 설명하면 끝나는 문제인데, SCPC 운영진은 디스크립션을 어렵게 쓰는 재주가 있는 걸까요?)


SCPC의 서브태스크는 보통은 만점 풀이와는 무관한 브루트포스 풀이를 요구하는 경향이 있는데, 이 문제는 서브태스크 순서대로 생각해 보면 정해 풀이까지 다다를 수 있는 문제였다고 생각합니다.

문제를 처음 읽으면 어떻게 배치해야 될지 조차 감이 오지 않지만 서브태스크가 그룹 크기가 홀수 또는 짝수인 경우로 나뉘어 있다는 점에서 착안해 아래와 같은 접근을 시작할 수 있었습니다.

서브태스크 1: 그룹이 모두 짝수인 경우

우선 그룹의 크기 $l_i$가 모두 짝수일 때의 경우, 최적의 배치가 어떻게 되는지 생각해 봅시다. 다른 그룹과 ‘닿는’ 부분이 최소화되면 좋을 것 같습니다. 그런 배치는 아래 그림과 같이, $2 \times \frac{l_i}{2}$ 직사각형들을 이어 붙인 경우가 됩니다.

이 때 핑크색으로 칠한 부분에서 충돌이 일어납니다.

그룹의 순서가 정해져 있을 때 충돌의 합을 최소화하려면, 첫 번째 그룹과 마지막 그룹에서는 제일 작은 원소 $2$개씩을 고르고, 나머지 그룹에서는 제일 작은 원소 $4$개씩을 고르면 됩니다.

다르게 생각한다면 모든 그룹에서 제일 작은 원소 $4$개씩을 고른 후, 두 개의 그룹에서만 $3$번째로 작은 원소와 $4$번째로 작은 원소 하나씩을 빼 주면 됩니다.

$i$번째 그룹에서 $j$번째로 작은 원소를 $m_{i,j}$라고 합시다. 그러면 모든 그룹을 $m_{i,3}+m_{i,4}$ 순으로 정렬한 후, $\sum_i \left(m_{i,1}+m_{i,2}+m_{i,3}+m_{i+4}\right)$에서 $m_{i,3}+m_{i,4}$가 제일 큰 두 그룹만 빼 주면 정답입니다.

서브태스크 2: 그룹이 모두 홀수인 경우

짝수인 경우와 비슷하게 배치해줄 수 있습니다.

이 경우에는 충돌이 조금 더 많이 생기긴 합니다만, 짝수의 경우와 비슷하게 접근할 수 있습니다.

우선 각 그룹마다 두 번씩 충돌이 일어나는 원소가 하나 있는데, 이를 그 그룹에서 가장 작은 원소로 둡시다. 그러면 모든 그룹에서 제일 작은 원소 $4$개씩을 고른 후, 두 개의 그룹에서만 $3$번째로 작은 원소와 $4$번째로 작은 원소 하나씩을 빼 주면 되는 것은 동일합니다만, 가장 작은 원소는 한 번 더 더해줘야 합니다.

다시 말하면 모든 그룹을 $m_{i,3}+m_{i,4}$ 순으로 정렬한 후, $\sum_i \left(\textcolor{#ff3b57}{2m_{i,1}}+m_{i,2}+m_{i,3}+m_{i+4}\right)$에서 $m_{i,3}+m_{i,4}$가 제일 큰 두 그룹만 빼 주면 정답입니다.

서브태스크 3: 짝수 그룹과 홀수 그룹이 섞여 있는 경우

위에서의 접근을 바탕으로, 크게는 $3$가지 경우로 나눠 생각할 수 있습니다.

  • 짝수 그룹과 홀수 그룹이 하나 이상씩 있다면, 맨 왼쪽 그룹과 맨 오른쪽 그룹에 짝수 그룹 하나와 홀수 그룹 하나씩이 있는 경우
  • 짝수 그룹의 개수가 $2$개 이상이라면, 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 짝수 그룹인 경우
  • 홀수 그룹의 개수가 $2$개 이상이라면, 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 홀수 그룹인 경우

3a: 맨 왼쪽 그룹과 맨 오른쪽 그룹에 짝수 그룹 하나와 홀수 그룹 하나씩이 있는 경우

먼저 홀수 그룹들을 전부 왼쪽에 배치하고, 나머지 짝수 그룹들을 전부 오른쪽에 배치합시다.

짝수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 하나와, 홀수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 하나를 골라서 빼 주면 됩니다.

3b: 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 짝수 그룹인 경우

위의 경우와 비슷합니다. 오른쪽에 있는 짝수 그룹들 중 하나를 빼다가 맨 왼쪽에 붙이면 됩니다.

짝수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 두 개를 골라서 빼 주면 됩니다.

3c: 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 홀수 그룹인 경우

이 경우는 약간 까다롭습니다.

일단 홀수 그룹 두 개를 잘 합치면 직사각형을 만들 수 있다는 점에서 착안해 아래와 같은 배치를 생각할 수 있습니다.

이 경우, 홀수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 두 개를 골라서 빼 주면 됩니다.

하지만 이런 경우는 홀수 그룹이 $4$개 이상인 경우에만 만들 수 있습니다. 홀수 그룹이 $2$개라면 어쩔 수 없이 아래와 같은 경우로 구성해야 합니다.

이 경우에는, 짝수 그룹들에서 $\sum_i \left(\textcolor{#ff3b57}{2m_{i,1}}+\textcolor{#ff3b57}{2m_{i,2}}+m_{i,3}+m_{i+4}\right)$를 해 줘야 합니다. 홀수 그룹이 $2$개인 경우에만 특수하게 처리해줍시다.

모든 경우를 고려한 코드는 아래와 같습니다. 정렬이 필요하기 때문에 $\mathcal{O}\left(n \log n\right)$만큼의 시간이 걸립니다. 사실 제일 큰 두 개 그룹만 구해도 상관없기 때문에, 잘 짠다면 $\mathcal{O}\left(n\right)$도 가능하지만요.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int a[100000];
pii p[20000];

void solve() {
    int n, m;
    cin >> n >> m;

    ll s = 0, sa = 0;
    ll oc = 0, ec = 0;

    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        for (int j = 0; j < l; j++) cin >> a[j];
        sort(a, a + l);
        ((l & 1) ? oc : ec)++;
        p[i].first = a[2] + a[3];
        p[i].second = (l & 1);
        s += (1 + (l & 1)) * a[0] + a[1] + a[2] + a[3];
        sa += 2 * a[0] + (2 - (l & 1)) * a[1] + a[2] + a[3];
    }

    sort(p, p + n, greater<>());

    if (oc && ec) {
        ll coe = 0, coo = 0, cee = 0;

        // coe: o o .. o e .. e e
        int o = 0, e = 0;
        for (int i = 0; i < n; i++) {
            if (!o && p[i].second) {
                coe += p[i].first;
                o++;
            }
            if (!e && !p[i].second) {
                coe += p[i].first;
                e++;
            }
            if (o && e) break;
        }

        // coo: o o .. o e .. e o .. o o
        if (oc >= 2) {
            o = 0;
            for (int i = 0; i < n; i++) {
                if (o < 2 && p[i].second) {
                    coo += p[i].first;
                    o++;
                }
                if (o >= 2) break;
            }
        }

        // cee: e e .. e o .. o e .. e e
        if (ec >= 2) {
            e = 0;
            for (int i = 0; i < n; i++) {
                if (e < 2 && !p[i].second) {
                    cee += p[i].first;
                    e++;
                }
                if (e >= 2) break;
            }
        }

        vector<ll> cd;
        cd.emplace_back(s - coe);
        cd.emplace_back(sa - coo);
        cd.emplace_back(s - cee);
        if (oc >= 4) cd.emplace_back(s - coo);

        s = *min_element(cd.begin(), cd.end());
    } else {
        s -= p[0].first + p[1].first;
    }

    cout << s << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

$s$는 다음의 합입니다.

\[s=\sum_i \begin{cases}m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is even}\\ 2m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is odd}\end{cases}\]

$sa$는 홀수 그룹이 $2$개인 경우 특수 처리를 해 주기 위한 값으로서 다음의 합입니다.

\[sa=\sum_i \begin{cases}2m_{i,1}+2m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is even}\\ 2m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is odd}\end{cases}\]

배열 $p$에는 모든 그룹들에 대해 홀/짝 정보와 $m_{i,3}+m_{i,4}$ 정보를 저장해 두고 정렬했습니다.

여담

이 문제는 오후 7시 33분에 한 번 수정되었습니다.

예약 시스템 문제에서 조건이 하나 빠져 있었습니다. 아래와 같이 명시했고, 제출 횟수를 20회로 늘릴 것입니다.

– 한 집합에 속한 예약자들은 모두 한 덩어리의 방들을 배정 받아야 한다. 한 덩어리의 방들이란 덩어리에 속한 어떤 방 두개에 대해서도, 덩어리에 속하고 인접한 방들을 통해서 이동이 가능하다는 의미이다.

그런 말이 쓰여 있지는 않았지만, 운이 좋게도? 당연히 연결 요소여야 최소일 것이라고 생각하고 풀었고, 문제를 맞을 수 있었습니다. 연결 요소가 아니어도 괜찮았을 경우, 다음과 같은 반례가 있습니다.

1
5 14
6 1 1 1 1 1 1
6 2 2 2 2 2 2
6 2 2 2 2 2 2
5 10 10 10 10 10
5 10 10 10 10 10

이 경우 아래와 같은 구성이 가능합니다.

이 때 답은 $84$입니다.

1차 5번 – 차이

$100\,000$개 이하의 미지수 $X_i$들에 대해 다음 쿼리들을 수행해야 합니다. 쿼리의 수는 $200\,000$개 이하입니다.

  • 1 i j d: $X_i + d = X_j$라는 조건을 추가합니다.
  • 2 i j: $X_i-X_j$를 출력합니다. 조건이 모순된다면 CF를, 주어진 조건들만으로 알 수 없다면 NC를 출력합니다.

$d$가 없다면 간단한 DSU 문제입니다. 이걸로 서브태스크 1과 3을 쉽게 해결할 수 있습니다.

DSU 트리의 간선들에 가중치가 있다고 생각한다면 서브태스크 2와 4를 해결할 수 있습니다.

우리가 DSU 쿼리를 $\mathcal{O}\left(\alpha\left(N\right)\right)$만에 할 수 있는 이유는 경로 압축path compression이라는 좋은 테크닉이 있어서입니다. $p_u$가 노드 $u$의 부모 노드라고 한다면, $u$의 루트를 구하는 함수 $\mathrm{find}$에서 경로 압축은 다음과 같이 재귀적으로 수행했습니다.

\[\mathrm{find}\left(u\right) = \begin{cases} u & \text{if } u=p_u \\ p_u \leftarrow \mathrm{find}\left(p_u\right) & \text{otherwise} \end{cases}\]

이렇게 하면 $u$에서 $u$의 루트 $r$로 가는 경로 위에 있는 모든 정점들의 부모가 아예 $r$로 바뀌어 버리게 됩니다.

현재 노드 $u$에서 부모 노드 $p_u$로 가는 비용을 $d_u$라고 합시다. 그러면 $d_u$도 비슷한 방법으로 압축해버릴 수 있습니다.

$\mathrm{find}$ 함수를 돌릴 때 $u$의 부모 노드는 $p_u$였고, $p_u$의 부모 노드는 $r$이었습니다. 따라서 $u$에서 $r$까지 가는 데는 $d_u + d_{p_u}$만큼의 비용이 필요합니다. $\mathrm{find}$ 함수에서 경로 압축을 수행하면서, $d_u$를 $d_u + d_{p_u}$로 업데이트해 주면 됩니다. 이제 가중치가 있는 DSU 트리에서도 경로 압축을 할 수 있습니다.

1번 쿼리와 2번 쿼리 모두 $\mathcal{O}\left(\alpha\left(N\right)\right)$만큼의 시간이 걸립니다. 총 시간 복잡도는 $\mathcal{O}\left(K\alpha\left(N\right)\right)$입니다.

$\alpha$는 역 아커만 함수inverse Ackermann function이며, $\alpha\left(2^{2^{2^{65536}}}-3\right)=4$ 정도로 작기 때문에 상수라고 생각해도 무방합니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int dsu[100001], conf[100001];
ll val[100001]; // [u] + val[u] = [dsu[u]]

int find(int u) {
    if (dsu[u] == u) return u;
    int pp = find(dsu[u]);
    val[u] += val[dsu[u]], dsu[u] = pp;
    return pp;
}

bool merge(int u, int v, ll x) {
    // [u] + x = [v]
    if (find(u) == find(v)) {
        if (val[u] + x != val[v]) {
            conf[find(u)] = true;
            return false;
        }
        return true;
    }

    int pu = find(u);
    x += val[u];
    int pv = find(v);
    x -= val[v];
    u = pu, v = pv;
    val[u] = val[v] - x, dsu[u] = v;
    conf[v] |= conf[u];
    return true;
}

void solve() {
    int n, q;
    cin >> n >> q;

    iota(dsu + 1, dsu + n + 1, 1);
    memset(conf, 0, sizeof conf);
    memset(val, 0, sizeof val);

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, j, d;
            cin >> i >> j >> d;
            merge(i, j, -d);
        } else {
            int i, j;
            cin >> i >> j;
            int pi = find(i), pj = find(j);
            if (pi != pj) {
                cout << "NC\n";
            } else if (conf[pi]) {
                cout << "CF\n";
            } else {
                cout << val[i] - val[j] << '\n';
            }
        }
    }

    cout.flush();
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

conf는 모순이 발생했는지 여부를 저장하는 배열입니다. find 함수가 항상 루트를 찾아주기 때문에, conf 플래그도 맨 위에만 달면 충분합니다.


긴 시간 문제 푸시느라 모두 수고하셨습니다. 라운드 2에서 만납시다!

목적지는 레이팅이 아니다

이게 무슨 해괴망측한 소리일까요?

이 글은 알고리즘 문제해결 트레이닝에 대한 사견私見입니다.


지금부터 전제를 하나 합시다.

  • 밥 먹고 알고리즘 공부만 하면 얼마나 걸릴지는 몰라도 언젠가는 코드포스 레이팅 3,000이 될 겁니다.

뭐, 세상에는 레이팅이 3,000을 넘는 괴물들도 다수 있지만 일단은 이론적으로 밥만 먹고 문제만 풀면 언젠가는 3,000에 갈 수 있다고 합시다. 사람마다 걸리는 시간은 다르겠지만요. 이를 근거로 공부한 시간 $t$에 대한 실력 $f$를 아래와 같이 모델링해 봅시다.

\[f\left(t\right) = 3\ 000 \left(1-a^t\right)\]

공부한 시간 v. 레이팅

하지만 실력은 올라가기만 하는 건 아닙니다. 어떤 날은 컨디션이 좋아서 머리가 잘 돌아가고 문제가 잘 풀릴 수도 있는 반면 어떤 날은 피곤하거나 우울하거나 뭐 물리적으로는 손가락이 아프다거나 할 수 있죠. 그렇기 때문에 조금 더 정확하게 실력을 모델링하려면 노이즈를 끼워야 할 겁니다. 대충 아래와 같은 모델은 어떤가요?

\[f\left(t\right) = 3\ 000 \left(1-a^t\right) + b \sin \left(ct\right)\]

공부한 시간 v. 레이팅 (약간 더 현실적인 모델)

좋습니다. $t$의 스케일이 얼마일지는 모르겠지만 이게 우리의 현재와 미래 실력을 대략적으로 모델링해준다고 합시다. 믿어 주세요.

하지만 제 레이팅은 계속 제자리인걸요

위 그래프에서 어떤 사람이 레이팅 1,400에서 1,600까지 가는 여정만을 한 번 살펴봅시다.

1,400 — 1,600

아마 가장 먼저 드는 생각은 이거일 거예요. ‘실력은커녕 내 그래프는 이거랑 비슷하지도 않은데…’ 맞아요. 쉽게 와닿지 않죠? 하지만 제가 여기에다 점을 몇 개 찍어볼게요.

1,400 — 1,600

… 어떤가요, 있을 법한 그래프이지 않나요? 운이 정말 나쁘다면 이런 경우도 가능할 거구요.

4연속 하락

이 그래프의 주인공은 과연 영영 파란색 닉네임을 달지 못하게 되는 걸까요? 우리는 결국에는 1,600이 될 거라는 사실을 알고 있지만, 점선을 지우고 나서 이게 자신의 그래프라고 생각한다면 정말 슬플지도 모르겠네요…

사실 저도 경험해 봤습니다

대회는 실력의 샘플링에 불과하다

여기서 중요한 관찰이 하나 있습니다.

우리가 모델링한 실력 그래프와 코드포스 레이팅 그래프 사이에는 큰 차이점이 있습니다. 우리 그래프는 연속적이지만 코드포스 그래프는 그렇지 않다는 점입니다. 이는 ‘대회’라는 시스템의 본질에서 기인합니다.


대회는 우리 실력이 지금 이 순간 어땠는지만을 알려주지, 실력을 실시간으로 알려주지는 않습니다.


이게 왜 큰 차이냐면, 코드포스 레이팅 그래프가 우리의 실력을 정확하게 말해주지 않는다는 뜻이기 때문입니다.

한 마디로, 대회는 실력의 샘플링에 불과합니다. 심지어 샘플링 주기가 짧지도 않습니다. 그래서 사실 그래프에 찍힌 점들만 보고 거시적으로 어디로 갈지 예측하는 건 불가능에 가깝습니다. 위에서는 실력 기복을 $b \sin ct$라고 퉁쳤지만 사실 그렇지도 않을 거구요.

게다가 보통 한 대회에는 문제가 6개밖에 없기 때문에, 모든 분야가 고르게 출제될 수도 없으며, 운 나쁘게 내가 자신없는 분야가 출제되어서 평소보다 못 풀 수도 있습니다. 다시 말하면 샘플링 자체도 그렇게 완벽하지는 않습니다.

문제 수 이야기가 나와서 말인데 레이팅 말고 대회에서 해결한 문제 수로 바꿔서 생각해 볼까요? 코드포스에서는 몇 문제를 풀었는지가 레이팅을 결정하는 중요 요소로 작용하죠. 하지만 푼 문제 수는 보통 한 자리 정수입니다. 굉장히 이산적인데요, 대회마다 나오는 문제의 난이도가 일정하다고 하면, 위에서 만든 실력 모델링 그래프는 대략 아래처럼 됩니다.

문제 수로 봤을 때의 그래프

똑같은 3솔브여도, C를 간신히 해결한 3솔브와 D를 다 생각했는데 시간이 약간 부족해서 못 푼 3솔브는 다를 겁니다. 여유롭게 3솔브를 하고 아깝게 4번째 문제를 못 풀었다면 적어도 간신히 3솔브를 했을 때보다는 확실히 성장했을 테지만, 결과적으로 스코어보드에 보이는 건 똑같이 세 개의 초록색이겠죠.

마지막으로, 코드포스의 레이팅 공식조차 실력을 완벽하게 표현해 주지는 못합니다. 코드포스의 공식은 마지막으로 친 대회 결과에 상당히 큰 영향을 받도록 설계되어 있습니다. 최근 5개 정도 대회만 실력을 유의미하게 반영해 주는데요, 연속적으로 운이 좋거나 나쁘면 아예 색깔이 바뀔 수도 있는 시스템이라 평소 실력을 제대로 반영해 주지 못합니다. 관련해서는 djm03178님의 Codeforces 레이팅에 관련된 글을 읽어 보면 좋습니다.

그러니까 문제를 평소보다 못 풀어도 괜찮고, 레이팅이 떨어지더라도 괜찮아요. 애초에 그게 진짜 본인의 실력은 아닐 거예요.

그래서 목적지는 레이팅이 아니다

라고 말하고 싶습니다. 바꿔 말하자면, 레이팅은 진짜 실력이 아니고, PS 실력을 키우는 것과 레이팅을 올리는 것은 비슷해 보이면서도 다르다고 생각합니다.

물론 색깔을 바꾸기 위해 알고리즘 문제해결 공부를 하는 것도 정말 멋진 일입니다. 하지만 그 과정이 정말 지치고 힘이 든다면, 레이팅은 좋은 목표가 아닐지도 모릅니다.

하지만 실력을 키우면 레이팅은 자연스럽게 올라갈 거예요. 이런 마음가짐을 가지고, 대회를 충분히 많이 치면 언젠가는 목표하는 레이팅이 될 수 있다는 희망을 갖고, 나 자신의 가능성을 믿도록 합시다.

조금 현실적인 조언

  • 업솔빙 / 문제 수를 목표로 하기 — 그래도 해결하는 문제 수는 레이팅보다 직관적이면서도 그렇게 많이 변하는 값은 아니기 때문에 목표로서 유의미하다고 생각합니다.
    문제 레이팅을 목표로 하는 것과 맥락을 같이하는데요, 대회에서 풀었던 제일 어려운 문제의 다음 번 문제를 해결하려고 시도해 봅시다. 모르겠다면 에디토리얼을 보고 인사이트를 얻어갑시다. 아까운 실수로 틀렸다면 너무 자책하지 말고 오히려 자신을 격려해 줍시다. 뼈아픈 실수일수록 반복하는 일이 적을 거예요. 궁극적으로는 대회에서 해결할 수 있는 문제 수를 늘리는 것을 목표로 합시다.
  • 문제 레이팅을 목표로 하기 — 문제 수를 목표로 하는 것과 맥락을 같이합니다.
    코드포스 대회가 끝나면 Problemset에 문제 레이팅이 공개됩니다. 목표 문제 레이팅 $r$을 정해 두고, 대회가 끝난 후 $r$ 이하의 문제들을 풀어보는 것으로 단련해 봅시다. 궁극적으로는 대회 시간 내에 $r$ 이하의 문제들을 안정적으로 풀 수 있는 것을 목표로 합시다.
  • 버추얼 컨테스트 돌리기 — 코드포스에는 끝난 대회를 가상 참가할 수 있는 기능이 있습니다. 또 가상 컨테스트 참여로 가상 레이팅을 계산할 수 있는 서비스도 있습니다. 이 서비스를 활용해 가상 컨테스트를 자주 치면 실력도 단련할 수 있고, 앞서 언급한 샘플링 주기의 문제도 어느 정도 해결할 수 있겠죠.
  • Atcoder — 일본 기반의 알고리즘 대회 사이트입니다. Atcoder는 코드포스의 레이팅 공식과 달리 현재까지 참여한 모든 대회의 퍼포먼스를 가중평균하는 식으로 레이팅을 계산하기 때문에 참가자의 평소 실력을 좀 더 잘 반영한다고 생각합니다. 게다가 문제도 코드포스보다 훨씬 깔끔하며, 시스텟이 없고, 무엇보다 시간대가 같아서 주말 오후 9시에 부담없이 참여할 수 있다는 장점도 있습니다. 강력하게 추천합니다.
  • 팀 연습 하다 오기 — 조금 더 긴 시간 동안 더 어려운 문제들에 대해서 생각해볼 수 있는 좋은 방법입니다. 새로운 인사이트를 얻을 수 있습니다.
  • 당분간 쉬기 — 너무 지쳤다면 괜찮아질 때까지 쉬어도 괜찮습니다. 알고리즘은 잊고 놀러 나가서 맛있는 거 먹고 옵시다. 금방 다시 회복할 수 있을 거예요.

알고리즘 문제해결이 여러분을 마음고생시키지 않았으면 좋겠어요. 여러분의 문제해결을 항상 응원합니다.

왜 AC RATING인가요?

solved.ac의 근간이 되는 두 가지 중요한 기능은 다음과 같습니다.

  • Baekjoon Online Judge 문제들에 난이도와 태그를 매겨서, BOJ에 있는 방대한 문제들 중 어떤 문제를 풀면 좋을지 훨씬 쉽게 고를 수 있는 수단을 제공합니다.
  • 푼 문제 수가 아닌, 푼 문제들의 난이도의 구성을 바탕으로 한 실력 지표와 이를 기반으로 한 순위 등을 제공해, 알고리즘 문제해결 학습자들에게 더 흥미로운 문제를 해결할 동기를 부여합니다.

실력 지표의 경우, 기존에는 문제를 해결할 때마다 경험치가 쌓이고, 푼 문제들의 경험치의 총 합을 기준으로 실력 지표인 티어를 결정했습니다. 이 방식은 solved.ac가 처음 만들어진 2019년 6월 6일부터 2년 가까히 이어져왔습니다만, 오는 1일부터는 새로운 실력 지표인 AC RATING으로 티어를 결정하게 됩니다. AC RATING은 아래의 합으로 결정되며, 이론적으로 3,450 이하의 정수 값입니다.

  • 푼 문제들을 난이도 순으로 내림차순 정렬했을 때, 상위 100개 문제의 난이도 값의 합 (최대 3,000)
  • CLASS에 따른 보너스 (최대 250)
  • 푼 문제 수에 따른 보너스 (최대 175)
  • 기여 수에 따른 보너스 (최대 25)

아니 잘 쓰던 경험치 냅두고 왜 이제 와서 이상한 조건의 레이팅을?이라고 생각하실까봐 레이팅제가 어떤 과정을 거쳐 탄생했는지에 대해 소개합니다.

경험치제의 문제점

기존의 경험치제를 간략하게 요약하면 이렇습니다.

  • 브론즈 5 문제를 해결하면 320점을 주도록 합니다. 어떤 문제보다 1티어 높은 문제의 경우 약 1.5배의 경험치를 주도록 합니다.
  • 브론즈 4 티어가 되려면, 브론즈 5 티어를 달성한 이후 브론즈 4 문제를 20문제 더 해결해야 하도록 합니다. 티어 $x$가 되려면, 티어 $x-1$을 달성한 후 난이도 $x$의 문제를 $n_x$개 더 해결해야 하도록 합니다.
  • 기여 한 건마다 경험치 10,000을 줍니다.

이는 여러분께서 자신의 티어와 비슷한 난이도의 문제를 해결할 것으로 기대하고 기획한 것이었습니다. 하지만 여러 부작용이 있었습니다.

단적인 예로 아무것도 해결하지 않은 사람이 루비 1 문제 하나를 풀면 그 한 문제 덕분에 바로 다이아몬드 5가 됩니다. 알고리즘 실력을 키우고 싶은지 아닌지는 제쳐두고, 티어를 올리고 싶다면 힘들게 브론즈 실버를 캐면서 차근차근 올라갈 필요 없이 어려운 문제 하나만 풀면 되는 것입니다.

보통 그런 ‘어려운 문제’는 혼자 힘으로 해결하기 상당히 어렵기 때문에 인터넷을 참고해 해결하는 경우가 많고, 해결하는 순간 경험치 구성의 대부분을 차지해 버리게 됩니다. 이제 본인 실력의 문제를 해결하는 것으로는 경험치가 1%도 오르지 않습니다.

루비 V 한 문제가 경험치의 93.4%를 차지하는 극단적인 사례.

위 유저가 해결한 문제 중 가장 어려운 문제는 루비 V이고, 그 다음은 골드 II 한 문제, 골드 III 두 문제, 골드 V 열한 문제입니다.

기존 경험치제에서 이 유저의 티어는 플래티넘 V인데, 플래티넘 V 유저가 골드 V 한 문제를 풀어서 얻을 수 있는 경험치량은 0.411%입니다.

루비 V 한 문제를 풀지 않았다면? 이 유저의 티어는 실버 I이었을 것이며, 이 경우 골드 V 한 문제는 무려 6.02%의 경험치를 줍니다. 그러면 현재 루비 V 문제 하나를 해결한 상황에서 골드 V 문제를 푸는 게 과연 매력이 있을까요? 그렇다고 플래티넘 문제들을 푸는데 많은 시간을 소비할까요?

대부분의 경우, 의욕을 잃거나 새로운 어려운 문제를 찾아 떠나게 됩니다. 이런 점을 노린 코드 카피 어뷰징이 solved.ac가 등장한 이후 상당히 빈번하게 발생했습니다. solved.ac는 알고리즘 문제해결 학습자들의 학습 동기 증진을 목적으로 하는 사이트인데, 기존 경험치제가 학습자를 다소 좋지 않은 학습 방향으로 유도한다는 생각이 들었습니다.

또한 한 문제를 풀면 경험치를 얼마나 주는지, 다음 티어로 올라가기 위해서는 총 경험치가 얼마쯤 되어야 하는지 혹은 어떤 문제를 얼마나 해결해야 하는지 알기가 어려웠다는 사소한 문제도 있었습니다. 더구나 현재 1위의 총 경험치의 자릿수는 11자리나 되어 상당히 비직관적입니다.

레이팅제의 목표

기존의 제도에는 이런 문제점들이 있었고, 이를 어느 정도 해결하기 위해 많은 고민 끝에 새로 레이팅 제도를 만들었습니다. 새 레이팅 제도의 목표는 아래와 같았습니다.

  • 실력을 정확히 측정하는 것과 동기를 불러일으키는 것 사이 어딘가에서 적당히 줄다리기합니다. 둘 다 완벽하게 되면 더 좋고요.
  • 낮은 티어의 유저들이 새롭고 다양한 알고리즘 분야를 접하는 것을 장려합니다.
  • 푼 문제가 현저히 많다고 레이팅이 현저히 높아지거나, 어려운 문제 하나가 레이팅의 대부분을 차지하게 되는 현상을 최대한 완화합니다.
  • 직관적인 값으로 보여지도록 합니다.
  • 서버가 빠르게 계산할 수 있도록 합니다.

실력 측정 vs 동기 부여

기존의 경험치제나, 새로 도입하게 되는 레이팅제나 사용자의 정확한 실력을 반영해 주기 원하시는 분들이 많았습니다. 결론부터 말하자면 정확한 실력을 가늠하는 건 불가능했기 때문에, 레이팅과 실력과의 상관관계를 높이는 것은 목표로 하지 않았고, 기존과 같이 약한 상관관계를 보이게 하는 것으로 만족했습니다.

정확한 실력을 가늠하는 것이 불가능한 이유는 BOJ가 OJ이기 때문입니다. OJ에 등록된 문제들은 이미 어딘가에서 출제되었던 문제들이고, 많은 경우 쉽게 해설을 찾아볼 수 있습니다. 반면 대회 플랫폼의 경우 매번 새로운 문제들을 주고 틀린 횟수와 해결 시간을 바탕으로 실력을 계산합니다.

따라서 OJ 쪽은 대회 플랫폼에 비해 유저의 실력을 계산하기 위해 사용할 수 있는 정보와 그 정보의 신뢰도 모두가 현저히 떨어집니다. 심지어 대회 플랫폼의 레이팅도 정확한 실력을 반영한다고는 할 수 없습니다. 대회는 실력을 샘플링하는 것에 지나지 않기 때문입니다. 수능 모의고사에서 1등급을 받은 학생이 수능에서도 같은 등급을 받을 것이라는 보장이 없듯이요…

이런 이유로 레이팅과 실력과의 대략적인 상관관계는 기존 수준으로 유지하되 새 레이팅 제도가 목표로 하는 동기 부여적 측면을 더 부각시킬 수 있는 쪽으로 기획 방향을 정했습니다.

레이팅의 뼈대

무작정 높은 난이도의 문제를 푸려고 하게 되는 이유는, 높은 난이도의 문제가 푸는 데 오랜 시간이 걸림에도 불구하고 티어 상승이라는 측면에서 상당히 매력적으로 보이기 때문입니다.

기존 경험치제에서 루비 I 문제 하나를 푸는 것은 브론즈 V 문제 약 30만개를 푸는 것과 비슷한 경험치를 줬고, 이는 문제해결에 쏟는 시간 대비 엄청난 가성비를 보여줍니다. 모든 티어에서 상당히 매력적으로 보이는 게 당연합니다. 따라서 매력을 너프하기 위해서는, 일단 문제 해결로 얻는 경험치가 난이도에 따라 기하급수적으로 올라가는 식이 아니어야 합니다.

하지만 그렇게 되면 난이도에 관계없이 문제를 많이 해결한 사람이 무조건 유리해집니다. 레이팅이 적용된 다른 OJ들이나 비슷한 구조의 게임들이 이를 막는 방법은 크게 두 가지가 있습니다.

  • 반영되는 문제 수에 제한을 둡니다. $n$문제를 반영한다면, 어떤 사용자가 난이도 $x$까지의 문제를 해결할 수 있을 때 이론적으로 받을 수 있는 최대치는 $nx$입니다.
  • 모든 문제를 반영하되 적당한 상수 $0<r<1$을 정해서 첫 문제에는 $1$을, 두 번째 문제에는 $r$을, 세 번째 문제에는 $r^2$를 곱해나가는 식으로 합니다. 어떤 사용자가 난이도 $x$까지의 문제를 해결할 수 있을 때 이론적으로 받을 수 있는 최대치는 $\frac{x}{1-r}$입니다.

두 방법은 사실상 같습니다만 첫 번째 방법은 서버가 계산하기 쉬운 대신 특정 난이도 이상의 문제를 풀지 않으면 아무리 문제를 풀어도 레이팅이 아예 오르지 않는다는 단점이 있고, 두 번째 방법은 문제를 풀면 레이팅이 계속 오르겠다는 믿음을 주는 대신(실제로는 1점 올리기는 상당히 어렵습니다) 서버가 레이팅을 계산하는 코스트가 조금 더 든다는 단점이 있습니다.

그래서 문제를 풀면 레이팅이 오르겠다는 믿음은 다른 방법으로 주기로 하고 첫 번째 방법을 택했습니다. 100문제를 해결하면 레이팅이 수렴했다고 보고, 푼 문제들을 난이도 순으로 정렬해 상위 100개 문제의 난이도 값의 단순합을 레이팅의 가장 많은 부분을 차지하도록 했습니다. 공교롭게도 solved.ac의 문제 난이도는 0부터 30까지라서 이렇게 하면 총 3,000점이 되고, 다른 대회 플랫폼들의 4자리수 레이팅과 비슷한 값이 되어 직관적이게 됩니다.

상위 100문제의 난이도 합으로 결정

여기에 문제 해결 수에 따른 보너스 레이팅을 $\left\lfloor 175\left( 1-0.995^n \right) \right\rceil$만큼 주어 약 1,200문제를 해결할 때까지 어느 문제나 해결해도 레이팅이 오른다는 믿음을 주도록 유도했습니다. 다만 실제로 믿으실지는 모르겠습니다. 믿어 주세요.

기존 기획은 이 100문제를 (5년간 출제된 OI/ICPC 문제) 50개와 나머지 문제 50개를 반영하려 했으나, 그렇게 할 근거가 부족하여 100문제를 합하는 것으로 선회했습니다.

새롭고 다양한 알고리즘 문제해결 장려

이미지
CLASS

solved.ac에는 티어 외에도 CLASS라는 실력 지표가 있습니다. 실력대별로 미리 정해진 48문제 중 20문제 이상을 해결하면 얻을 수 있습니다.

CLASS 문제들은 수준에 따라 교육적인 목적을 갖고 정해져 있습니다. 예를 들어,

  • CLASS 1는 프로그래밍 혹은 알고리즘 문제해결 입문자가 풀어보면 좋을 만한 문제들로 구성했습니다.
  • CLASS 2는 코딩 테스트나 프로그래밍 대회 등에서 자주 등장하는 주제들 중 초심자가 이해하고 구현하기 쉬운 주제들로 구성했습니다. (브루트포싱, 기초 수학, 정렬, 큐, 스택, 덱)
  • CLASS 3은 CLASS 2에서 등장한 주제들을 전부 이해하고 나서 시도하면 좋을 만한 주제들로 구성했습니다. (그래프, 그래프 탐색, 힙, 우선순위 큐, 다이나믹 프로그래밍 등)
  • CLASS 4는 CLASS 3과 비슷하지만 더 어렵다고 느껴지는 주제들을 담았습니다. (백트래킹, 최단 경로 문제, 어려운 구현, 어려운 다이나믹 프로그래밍, 어려운 그래프 문제 등)

낮은 CLASS 문제들은 ‘단계별로 풀어보기’와 비슷한 구성으로 초심자가 가면 좋을 만한 길을 추천해 주는 것을 목표로 했습니다. 이를 더더욱 권장하기 위해 레이팅에 CLASS 보너스를 추가했습니다. 다만, 새 레이팅과 실력과의 괴리가 생길 것을 감안해 낮은 티어에서는 CLASS 보너스가 매력적으로 보이지만 높은 티어에서는 CLASS 보너스의 유무가 랭킹에 큰 차이를 주지 않도록 다음과 같이 정했습니다.

  • CLASS 1, 2: +25점
  • CLASS 3, 4, 5: +50점
  • CLASS 6~: +10점

CLASS 6부터는 주로 프로그래밍 대회에만 등장하는 어려운 주제들을 다루고 있습니다. 또한 CLASS 6 이상을 취득할 수 있는 실력의 사람이라면 CLASS 5 정도는 쉽게 취득할 수 있고, 굳이 CLASS 문제를 해결하지 않더라도 실력을 늘릴 방법을 많이 알고 있을 것이라고 생각했기 때문에 CLASS 6 이상에서의 레이팅 보상은 랭킹에 크게 영향을 미치지 않는 방향으로 결정했습니다.

레이팅 컷

레이팅에 따른 티어는 크게 두 가지 요소를 고려해 정했습니다.

  • 티어 $x$의 유저 입장에서 티어 $x+1$로 가기 위한 과정에서의 경험은 적절한가
  • 티어에 따른 유저 비율이 어떻게 변화할 것인가

특히 새로운 레이팅 제도에서는 상위 100문제를 반영하고 있는데, 알고리즘 공부를 막 시작한 입장에서는 100문제를 해결하는 것부터 버거울 수 있겠습니다. 따라서 ‘몇 CLASS이길 기대하는가?’와 더불어 낮은 티어의 경우 ‘몇 문제를 해결하는 것을 기대하는가?’를 고려했습니다. 예를 들자면

  • 기존 경험치제의 브론즈 구간에서는 실력에 맞는 문제를 약 30문제 정도를 해결하는 것을 기대했습니다. 새로운 레이팅제에서는 CLASS 1~2를 해결하는 여정을 고려하여 레이팅 컷을 정했습니다.
  • 골드 구간부터는 100문제 이상 해결을 기대하고, 상위 100문제에서 기대하는 난이도 평균을 고려했습니다. 예컨대 골드 III 유저는 평균적으로 클래스 2~3에 실버 II에서 골드 V 수준의 문제를 쉽게 해결할 수 있을 것으로 생각했습니다. 클래스 5를 달아 레이팅 100~150을 챙기고, 클래스 5를 풀면서 골드 상위~플레 하위 문제들에 익숙해져 상위 100문제를 그렇게 구성한다면 어느새 플래티넘이 되어 있을 것입니다.
  • 이론적인 레이팅 만점은 3450이지만 루비 구간의 문제들이 부족하고 상위 100문제가 이미 다이아몬드와 루비로 꽉 차 있는 상황에서 더 어려운 루비 문제를 해결하는 것 자체가 상당히 어려운 과정임을 감안해 루비 구간은 촘촘하게 나눴습니다.

그렇게 하면서도 레이팅 컷이 직관적인 수가 되도록 했습니다 – 브론즈 30, 실버 200, 골드 800, 플래티넘 1600, 다이아몬드 2200, 루비 2700. 이렇게 각각의 티어에서 많은 고민 끝에 레이팅 컷을 정했습니다.

새 레이팅 컷

플래티넘, 골드, 실버, 브론즈가 각각 상위 10%, 33%, 67%, 100%가 되는 것이 이상적이라고 생각하고 있습니다만, 당시 레이팅 공식이 공개되지 않았음을 고려해 기존보다 약간 더 어렵게 설정했습니다. 레이팅 공식이 공개되는 것이 유저 비율에 영향을 미칠 수 있어서입니다.

레이팅 vs 기존 실력 지표

(왼쪽) 새 티어와 코드포스 레이팅의 상관관계, (오른쪽) 기존 티어와 코드포스 레이팅의 상관관계

신규 레이팅제에서, 코드포스 아이디가 존재하는 상위 569명을 대상으로 코드포스 레이팅과 새 티어를 비교한 결과 기존 티어에 비해 상관관계가 약해졌습니다만, 기존과 같이 어느 정도의 상관관계는 유지하는 양상을 보였습니다. Inversion count도 기존 148,135회에서 161,462로 증가했습니다. 기존 경험치제의 문제점을 해결하기 위해 실력과의 상관관계를 다소 희생했으나, 여전히 어느 정도 유의미한 상관관계를 가진다고 해석했습니다.

극복해야 할 과제

새로운 레이팅제도 완벽하진 않습니다. 대표적으로 1,200문제를 해결해 문제 수 보너스 175점을 모두 받은 유저의 경우, 새 레이팅제에서는 상위 100문제보다 낮은 난이도의 문제를 해결하는 것의 의미가 없어집니다. 충분히 흥미로운 문제가 있을 수도 있지만요. 또한 CLASS 보너스 레이팅을 산입하는 것이 좋은 선택인가에 대한 논의도 있었습니다.

이런 부분들에 대해서는 레이팅제로 운영해보면서 어떻게 개선할 수 있을지에 대해 고민해 보기로 했습니다. 길라잡이 컨텐츠를 잘 만드는 것 등 레이팅 공식 외적으로도 개선할 수 있는 부분이 있을지도 모르겠습니다.

티어를 어떻게 결정할지를 정하는 것은 solved.ac 전체를 통틀어 가장 어려운 기획입니다. 그만큼 수많은 고민 끝에 만들어진 기획인데, 고민한 만큼 긍정적으로 정착하면 좋겠습니다.


이후 계획

제가 직장인이 되었고 또 여러가지 일들로 바빠지다 보니 solved.ac에 새로운 컨텐츠를 만들 시간이 상대적으로 부족해졌습니다. 현재 계획하고 있는 것들은 이렇습니다.

  • 백엔드 리팩터링(~6월). 프론트엔드에 이어 백엔드입니다. 현재 백엔드는 PHP인데, 유지보수가 너무 어려운 상황이라 Express로 다시 짜고 있습니다. solved.ac를 처음 만들 시절엔 이렇게 커질 줄 몰랐으니까 어쩔 수 없는 것 같습니다. 프로젝트를 시작할 때부터 기반을 잘 닦읍시다.
  • 길라잡이(~9월).
  • 투표 개편(~9월).

앞으로도 많은 관심과 기대 부탁드리겠습니다!

Prop `className` did not match

Next.js + styled-components에서 Prop `className` did not match가 발생하는 이유와 해결 방법

작년 가을에 solved.ac 프론트엔드를 Typescript로 리팩터하면서 당황스러운 경험을 했습니다. 사이트 내의 아무 링크나 클릭해서 다른 페이지로 가면 스타일시트가 전부 깨지는 것이었습니다.

콘솔을 열어 보니 다음과 같은 에러가 뜹니다.

Warning: Prop `className` did not match. Server: "sc-xxxxxx xxxxx" Client: "sc-yyyyyy yyyyy"

오류에서 알 수 있듯이 서버와 클라이언트에서 클래스네임이 일치하지 않아서 발생한 오류임을 알 수 있습니다. Next.js는 SSRServer-side Render을 도와주는 프레임워크입니다. SEO검색 엔진 최적화 등을 위해 처음 페이지를 로드할 때는 서버에서 렌더해 오지만, 페이지에서 링크를 클릭해 다른 페이지로 넘어갈 때는 CSR로 페이지를 렌더합니다. SEO와 속도 두 가지를 해결해 주는 프레임워크죠.

그럼 서버와 클라이언트는 기본적으로 같은 로직을 공유할 텐데 왜 이런 일이 일어나는 걸까요?

babel-plugin-styled-components가 없어서

첫 번째 이유는 babel-plugin-styled-components가 없어서입니다. 이 Babel 플러그인은 환경과 상관없이 일관된 className을 생성(consistently hashed component classNames between environments)해 줍니다. 헐 그럼 styled-components는 이 플러그인 없으면 기본적으로 className 생성을 ‘환경’에 의존한다는 뜻인가요 네 그렇습니다.

styled-components는 styled 함수로 만든 컴포넌트마다 generateId 함수를 이용해 유일한 식별자를 생성하는데요, 함수에서 확인할 수 있다시피 전역 카운터를 하나 두고 컴포넌트 하나를 처리할 때마다 증가시켜 가면서 생성됩니다.

위의 방법으로 식별자를 생성하면 어떤 일이 일어날 수 있을까요? 컴포넌트가 생성되는 순서에 따라 같은 컴포넌트이더라도 다른 식별자가 붙을 수 있게 됩니다! CSR에서는 상관없겠지만 SSR과 CSR을 같이 활용하는 경우 서버와 클라이언트가 컴포넌트를 생성하는 순서에 따라 식별자가 달라질 수 있습니다. babel-plugin-styled-components는 이런 식별자 생성 과정을 정규화해 줍니다.

다음과 같이 해결할 수 있습니다.

1. 플러그인 설치:

npm i --save-dev babel-plugin-styled-components

2. 프로젝트 루트의 .babelrc 편집(없을 경우 생성):

{
  "plugins": ["babel-plugin-styled-components"]
}

3. Next.js를 사용 중인 경우 이곳의 _document.js를 복붙해 오세요.

그래도 안 돼요

이 포스트의 핵심입니다.

solved.ac의 경우에는 저걸 다 했는데도 안 되길래 몇 달 내내 이거 고치려고 삽질을 했습니다. Typescript로 리팩터링하기 전엔 없던 문제였는데 Typescript를 들고 오면서 생긴 오류라, 뭐가 문제인지 찾아보다가 커스텀 테마 타입 정의 때문이라는 걸 알았습니다.

solved.ac 프론트엔드 코드에는 SolvedTheme라는 타입이 있고, 여기에 테마 정의를 넣습니다.

interface SolvedTheme {
  defaultFonts: string
  codeFonts: string
  background: string
  textColor: string
  textColorInverted: string
  textSecondaryColor: string
  border: string
  borderColor: string
  tableHeaderBackground: string
  tableBackground: string
  footerBackground: string
  primaryColor: string
}

기존의 경우 styled-components로 만든 컴포넌트에서는 이를 아래와 같은 식으로 활용해 왔습니다.

const TopBarContainer = styled.div`
  position: fixed;
  width: 100%;
  height: 48px;
  line-height: 48px;
  background: ${({ theme }) => theme.background};
  border-bottom: ${({ theme }) => theme.border};
  top: 0;
  left: 0;
  z-index: 10000;
`

Javascript에서는 문제가 없는 코드이지만 Typescript에서는 컴파일 에러가 납니다. theme의 타입이 위에서 정의한 SolvedTheme가 아닌 styled-components에 내장된 DefaultTheme이기 때문입니다.

우선 이 문제를 해결하기 위해 열심히 구글링을 했고, styled-components를 아래와 같이 제 타입 정의로 감싼 뒤 이렇게 만들어진 새로운 styled를 여기저기 import 해 와서 사용했습니다. import styled from '../styles/Themes' 같은 식으로요.

import * as styledComponents from 'styled-components'
import { ThemedStyledComponentsModule } from 'styled-components'

const {
  default: styled,
  css,
  createGlobalStyle,
  ThemeProvider,
  ThemeConsumer,
  keyframes,
} = styledComponents as ThemedStyledComponentsModule<SolvedTheme>

export { css, createGlobalStyle, keyframes, ThemeProvider, ThemeConsumer }
export default styled

그런데 이렇게 정의해 버리면 babel-plugin-styled-components가 의미가 없어집니다. babel-plugin-styled-components는 import 경로가 ‘styled-components’인 경우에만 작동하기 때문인데요.

옵션에서 바꿀 수 있어 보이지만 깔끔한 해결책은 아닌 거 같고, 대신 styled.d.ts를 새로 만들고 여기에서 DefaultThemeSolvedTheme으로 두면 됩니다. 그러면 위의 문제를 해결하면서 커스텀 테마의 타입 정의도 사용할 수 있습니다.

import 'styled-components'
import { SolvedTheme } from './Themes'

declare module 'styled-components' {
  export type DefaultTheme = SolvedTheme
}

일반적인 원인은 아닐지 모르겠지만, 제가 영문도 모르고 몇 달간 고생한 걸 다른 분들이 겪지 않았으면 하는 마음에서 제 사례를 소개했습니다.

참고한 리소스

이른바 명예로운 자가격리를 당한 거지

2020년 회고

강변북로 사진
서강대교에서 찍은 강변북로

올해부터 블로그에 1년 단위로 뭘 했는지 회고를 써 보기로 했습니다. 나중에 잊어버리면 슬프잖아요.

애초에 애인도 친구도 없어서 약속 없는 핑계를 코로나 때문이라고 둘러댈 수 있는 좋은 한 해였습니다. 이른바 명예로운 자가격리를 당한 거죠. 저희 집에서 가장 가까운 박쥐 동굴 방향으로 하루에 세 번 절하고 있습니다.

그래도 코로나가 12월에는 끝나있을 줄 알았는데 그것도 아니더라구요. 일일 확진자 수 최고치 연일 갱신 중이고 저는 집에서 재택근무를 하고 있습니다. 엇 그래도 이제 직장은 있군요 다행이에요

소프트웨어 개발

solved.ac

이미지
살아남았다

올해는 solved.ac 개발에 꽤 집중했습니다. 올해 솔브드에 새로 생긴 큼직한 기능들은 다음과 같습니다.

  • 문제 정렬. (2월) 문제 목록에서 문제 순서를 쉽게 정렬할 수 있습니다.
  • 고급 검색. (2월) 문제 제목뿐 아니라, 맞은 사람 수, 문제 레벨, 내가 푼 문제 등에 필터를 걸 수 있고, AND, OR 등의 연산자를 이용해 검색하는 것이 가능해졌습니다. 검색 쿼리 문법을 직접 만들고, 이를 해석하는 파서 등도 만들었습니다.
  • 프로필 배경. (2월) 프로필을 배경으로 꾸밀 수 있게 되었습니다.
  • 라이벌. (4월) 다른 유저를 라이벌로 등록하고, 라이벌들과 나의 순위를 볼 수 있습니다.
  • 프로필 사진. (5월) 프로필 사진을 올릴 수 있게 되었습니다.
  • 화이트리스트제 종료 및 베타 종료. (6월 5일) 지금은 상상하기 힘들지만, 6월 이전에는 솔브드를 사용하려면 제게 이메일을 보내서 화이트리스트에 등록되어야 했습니다. 6월부터는 기존처럼 크롤링 및 파싱을 하는 방식에서 BOJ에서 유저 정보를 직접 받아오는 방식으로 바뀌어서, 누구나 사이트를 사용할 수 있게 되었습니다.
  • 코드 교환. (8월) 리딤 코드를 입력해 배경과 프로필 뱃지 등을 교환할 수 있게 되었습니다.
  • 자동 갱신. (11월) 이것도 지금은 상상하기 힘들지만, 11월 이전에는 문제를 풀고 나서 프로필에 있는 ‘갱신’ 버튼을 직접 눌러줘야 했습니다. 지금은 문제를 푸는 즉시 경험치가 반영되기 때문에 굳이 갱신 버튼을 누를 필요가 없습니다.

이제 BOJ와의 통합 작업도 거의 마무리되어 solved.ac에 굳이 들어오지 않고도 BOJ에서 solved.ac 문제 난이도와 태그 정보를 확인할 수 있게 되었습니다. 또한, 길라잡이 등의 새로운 기능들이 공개를 앞두고 있습니다. 내년에도 잘 부탁드려요!

Javascript 프레임워크의 세계로

solved.ac의 소스 코드는 원래 대부분 PHP로 되어 있었습니다. 프론트엔드 코드가 복잡해지면서 유지보수에 무리가 갔고, PHP의 특징적인 여러 요소들 때문에 코드 베이스가 PHP인 이상 추가적인 무언가를 개발하기는 힘들겠다 싶었습니다.

그래서 컴포넌트를 만들고 재사용하기 좋다고 들은 React로 무작정 프론트엔드 포팅을 시작했습니다. 검색엔진 최적화도 해야 해서 SSR을 지원해 주는 Next.js도 같이 사용했고요.

당시에는 리액트에 대해 하나도 몰랐지만 지금은 현업에서 매일 사용하고 있을 정도로 익숙해지기 쉬운 프레임워크라고 느낍니다. 진작에 이걸 왜 안 했지? 싶을 정도로요. 참고로 리액트를 쓰기 이전에는 제가 만들었던 사이트들은 아무 프레임워크도 사용하지 않고 오직 vanilla JS로만 돌아갔습니다.

이후에는 Typescript도 적용해 프로젝트를 리팩터했습니다. 타입 추론이 상당한 개발 효율을 가져다주는 것을 체감할 수 있었습니다. 가령 기존에는 API response에 대한 타입 정의가 없어서(게으르게도 명세도 딱히 해 두지 않았었습니다), 필드나 타입을 헷갈려서 오류가 발생하거나 개발 속도가 느렸었는데, 지금은 타입 정의를 열심히 만들어서 제 human error로 오류가 발생할 수 있는 가능성을 대폭 줄였습니다. 되게 기본적인 거지만 나름 뿌듯했던 경험이라 소스 코드를 첨부해 공유해 봅니다.

type SolvedPageContext = NextPageContext & GlobalProps

export type SolvedPage<
  P = { siteTitle?: string[] },
  IP = P
> = NextComponentType<
  SolvedPageContext,
  IP & { siteTitle?: string[] },
  P & { siteTitle?: string[] }
>

export default SolvedPageContext

이렇게 정의하면 페이지의 Props의 타입 정의가 어떤지에 따라 getInitialProps에서 반환해 줘야 하는 타입이 결정됩니다. 아래 페이지의 경우 props.result의 타입이 Problem[]으로 정해져 있기 때문에 ProblemList에서 렌더 로직을 짜기가 상당히 편해집니다. 에디터 연동은 두말할 것도 없구요.

type Props = SolvedApiResponse<SearchProblems>

const LevelProblems: SolvedPage<Props> = (props) => {
  // ...
  return (
    <PageLayout>
      <h1>
        <TierMark value={level} locked={false} showName={true} />
        {caption ? ` — ${caption}` : null}
      </h1>
      <ProblemSortController
        currentSort={newQuery.sort}
        currentDirection={newQuery.direction}
      />
      <div>
        <ProblemList
          result={props.result}
          page={page}
          keys={['id', 'title', 'solved_count', 'average_try']}
        />
      </div>
    </PageLayout>
  )
}

LevelProblems.getInitialProps = async (ctx) => {
  // ...
  try {
    const response = await SolvedApi<SearchProblems>(token).get(
      '/search/problems.json',
      {
        params: {
          query: queryString,
          page: +(page ?? 1),
          sort: sort ?? ctx.currentSettings?.problem_sort_by,
          sort_direction:
            direction ?? ctx.currentSettings?.problem_sort_direction,
        },
      }
    )
    return {
      siteTitle: ['문제', '레벨', levelName(+(level ?? 0))],
      ...response.data,
    }
  } catch (e) {
    // ...
  }
}

여하튼 이런 식으로 기존에 PHP로 짜여 있었던 프론트엔드를 몇 달에 걸쳐 전부 React + Typescript + Next.js로 다시 짰습니다.

안타깝게도 백엔드는 아직도 PHP로 되어 있습니다. 현재는 길라잡이를 만들면서 백엔드도 Node + Express로 다시 구현하려는 계획을 갖고 있습니다. 완료되면 solved.ac에서 PHP 코드를 찾아보기 힘들게 되겠네요.

취업

넥하

위의 개발 경험 덕분에 6월 중순부터 넥슨컴퍼니 산하의 엔진스튜디오에서 일하게 되었습니다. 회고를 쓰고 있는 지금 시점으로 입사한 지 벌써 반 년이 넘었네요.

게임회사지만 제 주 업무는 웹 프론트엔드 엔지니어입니다. 사내외 여러 서비스의 개발을 맡아 하고 있습니다. 어떤 서비스라고 말하긴 그렇지만 아마 이 글을 읽고 계신 분들 중 적지 않은 분들께서 제가 작업했던 서비스를 이미 사용해 보셨을 겁니다. 😉

이미지
서버는 오로라

여담으로, 회사에서 매달 넥슨캐시를 일정량 지급하는데 쓸 데가 딱히 없어서 메이플스토리를 시작했습니다. 이제 모라스 코앞이네요. 12월 30일에 모라스에 갔습니다. 어쩌다 보니 받는 것보다 많이 결제하고 있지만 결제한 만큼 월급으로 돌려(?)주니 괜찮지 않을까라고 생각하고 있어요..


대회 프로그래밍

코드포스

올해는 그토록 염원하던 오렌지를 드디어 갔습니다.

2100

근데 레이팅이 딱 2100점입니다.

근데 이 어려운 걸 한 번 더 해냅니다.

+0

이 사람은 대체 뭐 하는 사람일까요? 대체 어떻게 했던 걸까요?

오렌지 수문장

그래프가 딱 2100에 걸쳐 있습니다.

오렌지가 되니까 Div 1 이외에서는 레이팅 변동이 일어나지 않습니다. 근데 Div 1은 자주 열리지도 않고, 열리는 날에는 제가 뭔가 바빠서 매번 못 치게 되더랍니다. 뭐 한마디로 게을러진 거죠. 복학할 때 적의환향하겠다던 시프트는 대체 어디로 가고? 다시 열심히 쳐야겠어요.

대회 개최

이미지
보셨나요? 저의 15 연속 검수!

UCPC 2020을 개최하고, 많은 대회에서 검수 및 출제를 했습니다.

  • 진짜 최종 구데기컵 2 – 출제, 검수
  • UCPC 2020 (전대프연 여름 대회) – 운영 총괄, 출제, 검수, 조판
  • SUAPC 2020 (신촌지역 연합 여름 대회) – 출제, 검수, 조판
  • 신촌지역 연합 캠프 2020 – 검수
  • SNUPC 2020 (서울대학교) – 검수
  • Uni-CODE 2020 (UNIST) – 검수, 조판
  • SPC 2020 (서강대학교) – 검수, 조판

알고리즘 문제 제작과 검수, 프로그래밍 대회 진행 프로세스에 대해 과도할 정도로 많은 것들을 배울 수 있었던 한 해였습니다. 특히 글을 잘 쓰는 법을 배울 수 있었어요. 기회가 되면 SUAPC/SPC 출제/검수 후기도 작성해 보고 싶습니다.

대회 참가

여러 대회에 참가했으나 올해는 다소 부진했습니다.

  • ICPC Asia-Seoul 2020 National First Round – 팀 Redshift로 출전, 5/12솔브 #36
    • 풀이를 옳게 생각했던 건 3문제나 더 있었는데.. 강의실 키보드 탓을 했습니다.
  • SCPC 2020 – Finalist, 172/1000
    • 4번 문제가 되게 풀릴 거 같이 생겼길래 3시간동안 4번 문제만 잡다가 결국 못 풀고 망했습니다. 점수를 긁읍시다 여러분.

팀 연습 때는 NxxRC 8~10솔브 밀고 다녀서 잘하겠지 싶었는데 막상 한국 예선에서 저런 성적이 나와서 당황스러웠습니다. 개인 연습 부족인 거 같네요.

…적의환향 할 수 있을까요?

스터디 진행

Sogang ICPC Team에서 연초에 아래 주제들을 다루는 스터디를 진행했습니다.


그래픽 디자인

많은 프로그래밍 대회 운영에 참가하면서, 자연스럽게도 관련 포스터를 만들게 됐습니다.


프로그래밍 대회 문제들에 들어가는 그래픽도 많이 만들었습니다.


solved.ac 공식 SNS 계정이 생기면서 정사각형 모양의 그래픽도 만들었습니다.

solved.ac 웹 디자인은 포토샵이나 일러스트를 켜서 하지 않고 CSS로 직접 하기 때문에 따로 목업 디자인 같은 건 따로 없습니다.

아쉽게도 예전처럼 개인작을 만들거나 할 여유는 없었네요.


이외에

휴학하고 회사 다니면서 아무것도 안 한 줄 알았는데 정리해 보니까 뭔가 한 게 꽤 있었네요. 건강검진에서 많이 쉬라는 소리를 들어서 내년 목표는 바쁘지 않게 한 해를 보내는 것으로 해야겠습니다.

이미지
갤럭시 노트20 울트라 5G

휴대폰을 갤럭시 노트 20으로 바꿨어요. 흰색이 정말 예쁘길래 흰색으로 샀는데 잘한 선택인 거 같아요. 5G폰이지만 5G가 너무 안 터진다는 소리가 많아서 5G를 쓰지 않기 위해 자급제로 샀습니다. 근데 정작 노트에서 가장 중요한 기능이라고 할 수 있는 S펜은 자주 안 쓰게 되더라구요. 왼쪽에 달려 있어서 그런가..

라프텔

저어어엉말 오랜만에 애니메이션을 열심히 봤습니다. 넷플릭스도 열심히 봤습니다. 베스 하먼을 보고 체스 세트를 샀어요. 근데 잘 못 두는 거 같네요.

이미지
신도림역 출발열차 (특징: 신도림에서 출발함)

신도림역 출발열차의 존재를 알고 삶의 질이 올라갔어요.

이미지
츄니즘

세가의 리듬게임 ‘츄니즘’이 한국에 정식 발매되어서 휴가 쓰고 한주 내내 다녀왔어요.

이미지
서강대교에서 찍은 여의도

자전거를 유난히 많이 탔던 해였던 거 같기도 하네요. 특히 학교에서 놀거나 문제 풀다가 or 상수역 오락실에서 놀다가 서강대교 건너서 집에 따릉이 타고 자주 왔는데, 이제는 코로나 시국이 심해져서 자전거 타고 밖에 돌아다니기도 눈치 보이게 되었어요. 코로나가 없던 시절이 너무 그립네요..


솔브드 백엔드 Node.js 포팅도 마치고 싶었고, 그림도 그릴 줄 알게 되면 좋겠다 싶었고, 코드포스 레드도 가고 싶었고, 되게 하고 싶었던 게 많았어요. 다 못 이뤄서 올해 별로 한 게 없었던 줄 알았는데.. 정리해 보니까 이런 시국 속에서도 올해 되게 뭔가 많이 했었네요 😅 제가 너무 하고 싶은 게 많았나봐요. 좀 한가하게 살아도 되겠습니다. 건강검진에서도 많이 쉬라는 소리를 들었구요.

이 정도면 올해 나름 잘 보냈네요. 신년 목표도 한 해 적당히 잘 보내는 걸로 해야겠습니다. 새해 복 많이 받으세요~ 🔔

UCPC 2020을 개최했습니다

UCPC 2020 개최 후기

기회가 되어 올해 전국 대학생 프로그래밍 대회 동아리 연합전대프연 회장을 맡아 UCPC 2020을 개최했습니다. 2019 서강대학교 프로그래밍 대회에 이은 두 번째 대회 운영입니다.

전대프연은 알고리즘 문제해결을 좋아하는 25개 대학교의 26개 동아리의 연합이고, UCPC는 전대프연에서 매년 개최하는 프로그래밍 대회입니다. 보통 가을에 열리는 국제 대학생 프로그래밍 경시대회 한국 리저널의 연습 격 대회로 시작해서, 지금은 국내에서 열리는 프로그래밍 대회 중에서 커뮤니티 대회로는 가장 큰 규모를 갖고 있습니다.

왜 하겠다고 했나요?

대회를 코디네이트하는 건 힘듭니다. 그래서 선뜻 총대를 매겠다고 나서는 경우는 드물고, 실제로 3년 전엔 대회가 안 열린 적도 있었습니다. 4월이 되어도 아무도 대회 총괄을 하려는 사람이 없어 올해는 제가 열어보겠다고 했습니다. 저는 당시 휴학 무직 백수로 즐겁게 하루종일 뒹굴뒹굴 감자칩 먹으면서 매일 컴퓨터랑 눈싸움이나 하고 있었는데, 아마 휴학하고 있지 않았다면 상당히 바빴을 테니 나서지도 않지 않았을까 싶습니다.

인수인계를 받자마자 대회 기획을 시작하고, 출제자를 모집했습니다. 그러나 올해는 큰 문제가 있었습니다. 경우에 따라 기획의 근간이 바뀔 수도 있는 아주 큰 문제였습니다. 바로..

준비되지 않은 우리 앞에 성큼 다가와 버린 코로나 시대

코로나 큐

2020년을 살아가는 여러분께서는 모두 마음 속에 우선순위 큐 하나쯤을 갖고 계실 겁니다. 바로 코로나 시대가 끝나면 할 일이라는 이름의 우선순위 큐입니다. 저는 벌써 원소가 120개를 넘어가려고 합니다. 코로나 끝나면 여행 가야지, 코로나 끝나면 맛집 탐방 다녀야지, 코로나 끝나면 못 봤던 친구들 만나서 밥 먹어야지, … 분명 4월즈음에만 해도 큐가 이렇게 커질 거라고는 생각하지 못했습니다. 상황이 괜찮아질 줄 알았으니까요.

UCPC도 마찬가지였습니다. 대회가 열릴 7월즈음에는 상황이 괜찮아지겠지-라는 막연한 기대가 있었습니다. 그래서 오프라인으로 대회를 진행하려고 계획했습니다. 오프라인으로 개최하는 것이 좋은 이유를 나열해 보자면:

  • UCPC는 프로그래밍 대회 동아리 회원들의 교류와 경쟁의 장을 목표로 하고 있습니다.
  • 부정행위 검사가 힘듭니다. 참가자가 다른 팀 코드를 베꼈는지는 쉽게 알 수 있습니다. 하지만, 예를 들어, 3인 팀 대회인 UCPC에서 4인 이상의 팀원이 코드를 작성한다던가, (진짜 정말 극단적인 예시로) 대회 중에 tourist에게 문제 해법을 물어보고 이를 이용해 해결하는 등의 부정행위는 막기 힘드며 검사하는 것도 거의 불가능에 가깝습니다.
  • UCPC와 같은 규모의 대회에는 운영비가 많이 필요합니다. 그래서 스폰서의 도움이 절실합니다. 하지만 온라인으로 진행할 경우 오프라인으로 진행하는 것보다 스폰서에게 후원에 대한 메리트를 어떻게 줄 수 있을지 생각해내고 이를 어필하는 것이 상대적으로 어렵습니다.

반면 온라인으로 개최하는 것도 나름의 장점이 있습니다.

  • 예산에서 대관료를 고려할 필요가 없어집니다.
  • 대회장에 오지 않아도 됩니다. 지방에서 서울로 올라와서 참가하시는 분들의 경우 대회 참여를 위해 만 하루를 잡고 참가하시는 경우가 흔하다고 들었습니다. 이런 모든 비용을 절감할 수 있습니다.

분명 온라인 대회로 진행해서 얻을 수 있는 장점들도 있지만, 오프라인 대회로 개최하는 것의 장점이 훨씬 크리티컬했기에 할 수만 있다면 오프라인으로 진행하고 싶었습니다.

그러나 모두가 아시는 대로…

…하루 10명대였던 확진 판정은 갑자기 다시 30명, 40명, 80명이 되었고, 오프라인 대회로 개최할 경우 스태프가 방역을 책임질 수 없겠다는 생각이 들어 오프라인 개최를 포기하게 되었습니다.

정작 이 글을 쓰고 있는 시점에서는 일일 확진자가 100명 넘게 발생하고 있네요.

온라인이기 때문에 할 수 있는 것을 하기

그래서 할 수 있는 거라도 최대한 재밌게 해 보기로 했습니다. 일단 위에서 오프라인 대회의 장점으로 언급되었던 것들을 온라인으로 어떻게 살릴 수 있을지에 대해 먼저 고민해 봤습니다.

  • 교류와 경쟁의 장 제공 – 기존에 대회장에서 하던 풀이 방송과 스코어보드 방송을 Twitch 온라인 방송을 통해 진행하기로 합니다. 물리적인 공간보다는 덜하겠지만, 실시간 댓글을 통해 교류할 수 있게 됩니다.
  • 스폰서 어필 – 온라인 방송 중 방송 화면의 공간을 일부 활용해 스폰서 로고를 지속적으로 노출합니다. 스튜디오가 구해진다면 후원 세션을 참가자들이 가장 많이 볼 시간대인 대회 종료 직후 ~ 문제 해설 전에 진행합니다.

부정행위에 대한 고민이 가장 많았습니다. 대략 다음과 같은 의식의 흐름을 거쳤습니다.

  • 웹캠이 있으면 부정행위를 막을 수 있을까?
    • 웹캠이 있다고 해도 스크린에 카카오톡 같은 걸 띄우면 충분히 부정행위를 할 수 있지 않을까? 그럼 스크린 녹화도 필요할까?
    • 스크린 녹화를 하더라도 다른 장비가 있으면 충분히 부정행위를 할 수 있지 않을까?
    • 애초에 참가팀 50팀이 동시 접속할 수 있는 화상 채팅 서비스가 존재할까?
    • 존재한다고 하든 안 하든 우리가 그 화면을 전부 모니터링할 수 있는 여력이 있을까?
  • 웹캠은 힘들 것 같으니 카피 체크를 하자
    • 팀 간의 복붙은 막을 수 있겠지만 4명 이상이 한 팀으로 친 경우는 어떻게 막을 수 있을까?
    • 4명 이상이 한 팀으로 치지 않았더라도, 예를 들어 누군가 대회 중에 대회 문제를 random Codeforces red한테 물어봐서 푼다면? 어떻게 막을 수 있을까?
    • 그 코드는 언제 다 읽을까?
  • 결국 어떻게 해도 부정행위를 막을 수는 없는 거 아닌가?
  • 근데 어차피 부정행위 해서 높은 점수 받고 못 보던 사람이 스코어보드 위에 있는 상황이 발생하면 다 티나지 않을까?

결론은 PS 커뮤니티를 믿고 코드 카피 체크 이외의 별도의 부정행위 검사를 하지 않는 것으로 났습니다. 커뮤니티 대회였기에 가능했던 결정이었습니다. 큰 상금이 걸린 기업 대회였다면 이런 상황에서 상당히 곤란했을 것입니다.

인터넷 방송

Twitch Sports: Getting Started | Twitch Blog
인터넷 방송 플랫폼 트위치

그렇게 결정하고 나니 인터넷 방송이 대회 기획에서 출제와 검수를 제외한 가장 중요한 요소가 되었습니다. 프로그래밍 대회에 많이 참여해 보셨고 (무려 ICPC 월드 파이널!) 관련 스트림도 자주 하시는, 세계적인 인기를 자랑하는 월클(World Class) 스타 정재헌Gravekper님께 참여해주실 수 있는지 여쭸고, 흔쾌히 승낙해 주셔서 함께 온라인 방송을 기획하게 되었습니다.

방송에서 뭘 다루면 좋을지, 방송을 언제부터 켜면 좋을지, 화면은 어떻게 구성하면 좋을지 등등을 대회 직전까지 열심히 논의했습니다. 인터넷 방송에는 문제 풀이, 스코어보드, 후원 세션은 필수로 들어가야 했고, 이외에 대회에 참여하는 사람들도, 참여하지 않는 사람들도 모두 볼 수 있다는 점을 감안하면서 대회 종료 전에 뭘 하면 좋을까를 고민했습니다. 이에 온라인 방송이 있는 다른 대회들을 참고했습니다.

  • ICPCIOI는 대회 중에 실시간 스코어보드와 문제 해설을 보여줍니다. ICPC 방송은 생각보다 재밌습니다. 그래서 사실 제가 하고 싶었던 이상에 가까웠던 방송 형태이긴 하나, 온라인 대회이고 웹캠 사용을 포기했기 때문에 화면에 보여줄 수 있는 게 없었고, UCPC 방송은 대회 참가자들도 볼 수 있는 방송이었기에 문제 해설도 보여줄 수 없었습니다.
  • 반면 Google Hash Code 방송은 참가자들이 대회 중에 시청할 수 있습니다. 그래서 대회 시작 전후에만 방송을 하고, 대회 중에는 아무것도 보여주지 않습니다.

하지만 대회 중에 아무것도 보여주지 않으면 심심하기 때문에 간단히 스코어보드를 띄워 두기로 결정했습니다.

문제 풀이와 후원 세션도 걱정이었습니다. 지금까지 UCPC 풀이는 출제자가 강단에 나와 슬라이드를 보여주는 식으로 진행했고, 후원 세션도 마찬가지였습니다. 근데 올해는 어쩌죠?

다행히 감사하게도 작년에 이어 고려대학교 SW중심대학사업단에서 장소를 제공해 주셔서, 고려대학교 정보대학의 대형 강의실 하나를 스튜디오로 사용할 수 있었습니다. 기존처럼 출제진이 강단에서 슬라이드로 발표하고 이를 카메라로 찍어 방송할 수 있었습니다.

출제와 검수

코로나 시대가 되어도 프로그래밍 대회에서 변하지 않는 것은 바로 출제와 검수입니다. 올해는 제가 여름에 회사에 갈 걸 우려해 대회 준비를 일찍 시작했습니다. 출제진은 우리나라 최대의 알고리즘 문제해결 커뮤니티인 BOJ Slack에서 모집했고, 이후에 추가로 call for tasks를 통해 문제 공모를 받았습니다. 올해는 공모받은 문제가 많아 출제진 풀이 상당히 컸습니다.

슬랙

기획을 포함해 모든 소통은 Slack으로 진행했습니다. Slack의 (무료 버전의) 최대 단점은 메시지가 10,000개 이상 쌓이면 이전 메시지들은 하나씩 못 보게 된다는 것인데요, 마침 코로나로 인해 Slack에서 3달간 무료로 Standard Plan을 제공해 주고 있어서 고민 없이 사용했습니다.

문제마다 하나의 채널을 만들어 최대한 맥락을 잃지 않고 대화할 수 있도록 했습니다. 또한 대회 전반적인 공지를 올릴 #general 채널, 인터넷 방송을 기획할 #broadcasting 채널, 컨테스트 도중 생기는 라이브 이슈에 대응할 #contest-finals / #contest-preliminaries 채널 등을 필요에 따라 주제 단위로 만들어 활용했습니다.

Zapier

특히 박수찬tncks0121님의 도움을 받아, Slack과 Zapier 연동을 사용해 call for tasks로 메일을 받으면 메일 내용을 자동으로 Slack 채널에 포워딩해 주도록 설정할 수 있었습니다. 다만 Zapier의 문제인지 후술할 UCPC 메일서버 문제인지는 모르겠지만 메일이 몇 개 누락되는 경우가 생겼습니다. 이런 경우엔 제가 UCPC 메일함에서 직접 공모받은 문제를 출제 채널에 배달해야 했습니다.

구글 드라이브

출제/검수 현황과 문제 자료 관리 등에는 Google Drive를 사용했습니다. G Suite에 제공되는 기능인 공유 드라이브를 적극적으로 활용했습니다.

출제

대회 분위기 정하기

출제 초기에는 예선과 본선 각각의 적절한 난이도 커브를 결정해 주는 것이 중요합니다. 문제들이 너무 쉬우면 대회 중에 문제를 전부 해결하는 팀은 대회가 끝날 때까지 할 게 없어서 심심해지고, 반대로 너무 어려우면 문제들에 압도당한 팀들이 좌절하게 되기 때문입니다. 그래서 먼저 난이도 커브를 정하고, 이에 맞춰서 어떤 문제를 내야 할지, 문제 풀에서 어떤 문제는 사용하고 어떤 문제는 사용하지 말아야 할지 등을 결정할 수 있습니다. 작년 서강대 대회 출제 후기에서 언급했던 것이기도 합니다.

UCPC 2020 출제 현황 시트 – 블로그 글의 이해를 돕기 위해 연출되었습니다

이와 관련해 작년 UCPC와 올해 UCPC의 가장 큰 차이는 문제의 난이도를 가늠할 수 있는 수단인 solved.ac의 존재였습니다. 서울 리저널의 난이도 분포를 참고해서 문제 풀에 있는 문제들의 난이도들을 각자 가늠해 보고, 예선과 본선 중 어느 쪽에 사용할지 플로우를 잘 돌렸습니다. 또한 시트에 추가적으로 알고리즘 분류를 적어 넣어, 한 분야에 너무 치우친 컨테스트가 되지 않도록 문제 배치를 잘 해주었습니다. 다만 검수 과정에서 난이도와 분류 정보를 보는 것은검수에 악영향을 끼칠 수 있어서 해당 시트는 출제진만이 편집했고, 검수 현황 시트를 따로 만들어 두었습니다.

문제 난이도를 가늠하는 현장

Call for tasks로 공모받은 문제들도 이렇게 출제진끼리 난이도를 가늠해 보고 대회에 필요하리라 생각된 문제들을 채용했습니다. 공모받은 문제들과 내부에서 출제한 문제들이 많아서 아쉽게도 사용할 수 없게 된 문제가 많았습니다.

디스크립션과 데이터 작성

Polygon

데이터의 무결성을 최대한 보장하기 위해 디스크립션 작성을 제외한 모든 작업은 Polygon에서 testlib을 사용해 진행했습니다. Polygon 서버가 다소 불안정해서 조마조마한 상황이 몇 번 있었고, 패키지 전체를 자주 백업했습니다.

solved.ac Overleaf

문제지는 solved.ac 서버에 올라가 있는 비밀의 시크릿 프린세스 self-hosted Overleaf에서 작업했습니다.

디스크립션데이터 작성에 있어서는 대회 참가자가 문제 디스크립션을 이해하거나 기타 문제에서 중요하지 않다고 생각되는 이슈들을 해결하는 데 시간을 소비하지 않도록 하게 하기 위해 다음 원칙에 따라 UCPC 출제 컨벤션을 만들고 이를 최대한 지키려 노력했습니다.

  • 일부러 디스크립션을 이해하기 어렵게 하는 컨셉의 문제가 아닌 경우, 디스크립션은 한 번만 읽어도 이해할 수 있을 정도로 이해하기 쉬워야 하며, 디스크립션이 문제 해결을 방해해선 안 됩니다.
    • 같은 맥락에서 어려운 수학 기호 및 개념은 가능할 경우 최대한 사용하지 않습니다. 갓 고등학교를 졸업한 사람이 봐도 이해할 수 있는 수준이어야 합니다. 이를테면, ‘$A$의 모든 원소들의 제곱의 합’이라고 적을 수 있는 것을 굳이 ‘$\sum_{a\in A} a^2$’라고 적지 않습니다.
    • 글과 문자가 쉽게 구분되면서 문자가 글을 읽는 데 방해가 되는 일이 없도록 해야 합니다. 따라서 모든 문자는 기울임꼴로 작성하고, 수식에는 띄어쓰기를 잘 하며, 기호는 정확한 것을 사용해야 합니다.
  • 입출력 변수의 범위는 입출력 섹션에 한꺼번에 명시하는 것이 가장 좋습니다.
  • 데이터는 무결해야 합니다. 명시한 형식과 다른 데이터가 있어서는 안 되며, 입력 데이터에 대한 정답이 아닌 데이터가 출력 데이터로 되어 있어서는 안 됩니다.
  • 생소한 입출력 방법 등으로 참가자가 고생하는 일이 없어야 합니다. 특히 EOF로 출력의 끝을 명시하는 입력 데이터들이 그렇습니다.

또한 디스크립션을 굳이 Polygon에서 작업하지 않은 이유가 있다면, BOJ의 문제 출제 플랫폼인 BOJ Stack의 존재 때문입니다. BOJ에서 대회를 개최하기 때문에 대회 전에 문제들을 전부 BOJ로 옮겨야 하는데요, 대회 직전에는 디스크립션 수정이 잦습니다. 근데 Polygon에서 디스크립션을 관리하게 되면 어차피 만들어야 하는 문제지에서도 디스크립션을 수정해야 하고, BOJ Stack에서도 디스크립션을 수정해야 합니다. 또한 BOJ Stack에서는 LaTeX을 최대한 쓰지 말아달라고 하기 때문에 TeX로 작성한 문제들을 전부 HTML로, 이를테면 $1 \leq N, M \leq 200\ 000$ $1 \leq N, M \leq 200\ 000$과 같은 식은 1 ≤ N, M ≤ 200 1 &le; <em>N</em>, <em>M</em> &le; 200 000으로 다시 포맷해야 하는데, 이는 생각보다 상당히 고통스럽습니다. 이런 공수를 줄이고자 Overleaf에서만 디스크립션을 관리했습니다.

물론 HTML로 포맷하는 공수조차 줄이고자 그냥 모든 문제에 TeX을 사용했습니다. 이렇게 할 경우 Overleaf에서 Stack으로 문제 본문을 복사+붙여넣기 하면 세팅이 끝납니다. 참 쉽죠.

문제 삽화가 그려지는 과정

문제와 해설에 사용될 그림의 경우, 그림을 요청하는 채널을 따로 만들어서 출제진의 요청을 받고 제가 그림을 열심히 제작했습니다.

마지막으로 정해는 ICPC 경향에 맞춰 C++과 Kotlin(또는 Java)으로 모두 작성했고, 해당 언어들로 문제를 해결 가능함을 보장했습니다.

검수

문제 초안이 완성되면, 문제를 검증하게 됩니다. 주로 다음과 같은 항목들을 검증해야 합니다.

  • 데이터와 디스크립션의 포매팅이 올바르고well-formed 무결한지 (UCPC 컨벤션을 지키는지)
  • 출제자의 풀이가 완벽한지
  • 출제자가 의도하지 않은 풀이로 풀리지는 않는지, 출제자가 의도하지 않은 풀이로 풀렸다면 그 풀이도 정답으로 허용할 것인지

검수진은 바로 위와 같은 항목들을 꼼꼼히 확인하는 역할을 합니다. 출제진들 사이의 교차 검수crosschecking 이외에도 외부 검수진을 모셔 와 검수를 진행했습니다.

검수의 흔적

참가팀들이 틀린 방법으로 접근할 것 같은 풀이(‘사풀이’라고도 합니다)를 미리 예상하고, 이를 적절히 막습니다. 방법은 여러 가지입니다. 예를 들어,

  • 어떤 자연수 $N$이 소수인지 판별해야 하는 문제에서, $N=1$이 입력으로 들어오는 경우를 제대로 처리하지 못하는 코드들을 틀리게 하기 위해 $N=1$인 데이터를 준비할 수 있습니다. (예외 처리 데이터)
  • 혹시라도 고려하지 못한 경우가 있을 수 있으니 랜덤에 의존해 제작한 일반적인 데이터를 추가로 더 준비할 수 있습니다.
  • 아예 틀린 방법으로 문제를 해결하는 코드가 준비한 데이터를 운좋게 전부 통과하는 경우가 있다면, 틀린 방법으로 풀면 틀리거나 시간 초과를 받는 데이터를 준비할 수 있습니다. (반례 데이터)
  • 출제자가 의도한 풀이보다 훨씬 쉬운 풀이로 풀리는 경우 시간 제한을 조정하거나 문제에 등장하는 상수들의 제한을 조정할 수도 있습니다. 의도한 풀이로 접근하면 풀리지만 의도하지 않은 풀이로 접근하면 시간 초과를 받도록 적절히 제한을 조정합니다.

등과 같은 과정을 거쳐 문제를 완벽하게 만들었습니다.

다들 모여

이 참가자는 WA를 받고 생존한 후에 다른 참가자를 소환합니다.

재작년과 작년의 참가 조건이 마음에 들었고, 그대로 유지했습니다. 석박통합과정 학생의 참가 조건만 명확하게 정했습니다.

  • 3명이 1개 팀으로 참가해야 함
  • 학부생이라면 재학과 휴학을 불문하고 참가 가능
  • 대학원생이라면 석사과정 또는 석박통합 2년차까지 참가 가능
  • 다른 학교 구성원끼리 팀을 이루어 참가 가능

수상 경력에 따라 제한 조건을 둘까도 생각해 봤는데, UCPC는 역시 한국 최강자전의 컨셉인 것도 있는 것 같아 딱히 두지 않았습니다. 총 299팀이 예선대회에 참가를 신청해 주셨습니다.

매년 하던 것처럼 Google Forms를 이용해 참가 신청을 받고 GMail을 통해 공지사항을 전송했는데, 대회 규모가 커지면서 이 방법을 계속 사용하기엔 다소 무리가 있는 것 같다는 생각을 했습니다.

  • 참가자 중 메일 주소에 오타를 낸 참가자들이 몇몇 계셨습니다. 실제 예시로, nvaer.comnaver.com, gamil.comgmail.com, kaist.co.krkaist.ac.kr 등으로 도메인에 오타를 낸 메일 주소들을 확인할 수 있었고, 제 수작업으로 고쳤습니다. 도메인 오타는 어찌저찌 고칠 수 있는데 @ 앞 부분에는 과연 오타가 없었을까요? 이메일 인증에 기반한 서비스를 사용하거나, 이를 직접 구현해야겠다고 느꼈습니다.
  • 예선 계정 정보 메일 299개를 하나하나 작성해 보냈습니다. 또한 GMail에 일일 전송 메일 수 제한이 있다는 사실을 이 대회 운영하면서 처음 알았습니다. 이 때 대량 자동 메일 전송 시스템을 구축했어야 했는데, 그러지 못했던 것이 후술할 예선대회 대참사로 이어집니다.

예산 확보

출제자 분들과 검수자 분들께 노력에 대한 합당한 대우를 드리고, 참가자 분들께 상을 드릴 수 있도록 예산을 정했습니다. 온라인 대회였기 때문에 장소나 비품, 식사 등에 대한 고려는 할 필요가 없다고 생각했으나.. 오산이었습니다. 온라인 방송을 할 장소와 장비가 필요했고, 상품이 있다면 상품을 배송할 비용도 필요했습니다. 대관료와 장비, 배송비 등을 종합해 보니 온사이트로 치뤄진 예년 예산만큼은 못해도 상당히 무거운 예산이 나왔습니다.

감사하게도 대회를 열겠다고 하자마자 케니소프트, 알고스팟, 스타트링크, 그리고 고려대학교 SW중심대학사업단에서 후원 의사를 보내 주셨습니다. 이후에도 여러 개발 기업에 무작정 메일을 보냈고(…) 마인즈랩네이버 D2에서 출제와 검수 비용을 지원해 주셨습니다. 대단히 감사합니다! (solved.ac의 경우 사실상 제 개인 후원이기 때문에 논외로 합니다)

온라인 대회여서 기존의 후원 세션을 기존처럼 진행할 수 없어 어떻게 어필할 수 있을까 고민했습니다만, 오히려 온라인 대회이고 공개된 온라인 방송으로 대회를 진행하기 때문에 굳이 참가자가 아니더라도 대회 방송을 볼 수 있고, 따라서 알고리즘 문제해결에 대한 충분한 관심이 있는 시청자들에게 기업을 홍보할 수 있다는 점을 어필하기로 했습니다.

사실 출제와 검수는 이전에 서강대 대회를 총괄해 본 적이 있었기에 어느 정도 익숙한 부분이었습니다. 하지만 서강대 대회는 학과 사업이어서 후원사를 구할 필요가 없었던 반면 UCPC의 경우에는 우여곡절이 많았고, 실수도 했습니다.

가장 큰 실수는 후원 조건을 명확하게 정하지 못했고, 또 이를 후원사에 제대로 공유하지 못했던 것이었습니다. UCPC에서는 홍보 기업 발표 세션을 진행하는데, 온라인 방송으로 홍보 세션을 진행하면 참가자들이 도중에 방송을 이탈해 효과가 반감될 것을 우려하여 후원 조건 금액을 높게 정했습니다. 그러나 죄송하게도 다른 바쁜 일들에 정신이 팔린 제 불찰로 인해 이를 공유받지 못한 후원사가 계셨습니다. 다음 대회부터는 이번 일을 반면교사로 삼고, 가능하다면 파이콘의 예처럼 후원 조건을 합당하고 명확하게 정하고 홈페이지에 공지하며 후원사와 긴밀히 소통할 수 있도록 해야겠습니다.

후원 기업들에 다시 한 번 무한한 감사를 드립니다.

예선 방송 리허설(7월 23일): 폭풍전야

대회 전에 리허설을 통해 방송 진행 계획을 구체화했습니다. 운영진들과 함께 안암의 명물 고고 인디안 쿠진에서 카레를 먹고, 대회 중 스튜디오로 사용될 고려대학교 정보대학 강의실에 숭고한 연합대회가 진행되는 도중 급습해 모여 강의실의 배치와 장비 등을 확인하고, 인터넷 속도는 방송을 송출하기에 충분한지, 강의실 구조 상 풀이 and/or 후원 세션은 어떻게 하면 좋을지 논의했습니다. 관련해서는 가장 고민을 많이 하신 재헌님의 UCPC 2020 방송 후기를 참고하시면 좋습니다.

OBS가 브라우저 화면을 겹쳐 띄워 둘 수 있다는 것을 이용해 기획한 대로 제가 대회 직전(당일 새벽 3시까지!)에 React로 간단하게 방송 씬을 만들었습니다. 코드는 여기 올라와 있습니다.

예선(7월 25일): 이 곳이 어둠의 기운으로 가득차 곧 무슨 일이 일어날 듯 합니다

방송 씬을 만드느라 날을 새고 10시에 고려대에 도착해서 세팅을 시작했습니다. 운영진들은 과연 올솔이 몇 팀이나 나오고 언제 제일 먼저 나올까 내기를 합니다.

막상 대회 시간이 다가오니까 대회 진행 플랫폼인 BOJ가 500 Internal Server Error와 502 Bad Gateway 에러를 뱉기 시작합니다. 어…? 이대로는 대회를 정상적으로 진행할 수 없겠다 싶어 대회 시작을 14:10으로 10분 연기했습니다.

그런데 좀 잠잠해지나 싶더니 14:07쯤 되니까 같은 현상이 다시 일어나는 거였습니다. 10분을 더 연기할까 고민하고 있던 찰나, BOJ Stack도 먹통이 되었습니다. 대회 정보는 BOJ Stack이라는 관리 페이지에서 수정해야 합니다. BOJ Stack이 접속이 막히면 운영진도 대회 시간을 수정할 수 없습니다.

Media Tweets by Haachama Sukidesu (@Haachama_Suki) | Twitter

’14:20에는 괜찮아지겠지? 그럼 종료 시간을 10분쯤 연장해야겠다’고 생각했습니다. 서버는 비웃기라도 하듯 계속 접속을 거부했습니다.그런 와중에 UCPC 관련 메일 아래에 적혀 있던 제 전화번호로 참가팀들의 전화가 걸려오기 시작했습니다. 운영진도 대회 서버에 접속할 수 없는 상황임을 알려 드렸습니다.

이제는 대회를 어떻게 할지 빠르고 공정하게 결정해야 했습니다. 특히 여러 지역에서 모여서 대회를 치기 위해 스터디룸을 빌리는 팀이 많다고 알고 있어, 이 분들의 피해가 최소화되도록 하려면 어떻게 해야 하나 고민했습니다. 그 와중에 대회 사이트에서 문제 제목을 읽은 팀이 있다는 제보를 받았습니다. 문제 제목을 읽은 팀이 있었다는 것은 문제를 읽은 팀이 있었을 수 있다는 뜻도 되므로 신중하게 결정해야 했습니다.

정말 다행히도 이번 UCPC는 온라인 대회였기에 공간의 제약을 받지 않았고, 본선에 몇 팀이 출전하더라도 수용할 수 있었습니다. 그래서 아예 기업 대회 Qualification 라운드의 형식으로 본선 커트라인을 명시하고 시간을 대폭 연장하기로 결정합니다. 그리고 단체 메일을 보냈습니다.

그런데, 감사하게도, 구글이 제가 아이패드(구글 계정 입장에서는 ‘새로운 기기’)로 대량의 메일을 보내려는 시도를 감지하고 전대프연 계정을 차단시켰습니다. 제가 회장이 되면서 바꾼 비밀번호로는 로그인이 안 됐고 이전 비밀번호로 인증을 받아야 했는데, 무려 제 전전전임 회장께서 설정하신 비밀번호였습니다. 당장 연락을 드렸지만 회신을 무작정 기다릴 수도 없는 상황이었어서, 제 개인 메일으로 단체 공지와 문제지를 전송했습니다. 이 때가 오후 3시였습니다.

서버 상황은 오후 4시를 즈음하여 개선되었고 코드를 제출할 수 있는 상황이 되었습니다. 예선대회에서도 해설과 스코어보드 공개를 할 예정이었고, 이를 위해 출제진들이 모여 있었으나, 안타깝게도 이후 방송은 진행하지 못했습니다. 여러모로 아쉬웠습니다. 예선 당일 서버 사고가 일어났던 이유는 여기에서 읽을 수 있습니다.

결과적으로 본선 진출 팀은 총 170팀이 되었고 의도치 않게 역대 최대 규모의 본선이 되었습니다. 컷을 5문제로 잡았으면 좋았겠다는 의견도 많았으나 안타깝게도 결정 당시에는 출전 팀들의 실력을 가늠하기 힘들었습니다.

본선도 규모가 예선 못지않게 커져버렸고, 본선대회에서도 같은 일이 되풀이되면 안 되었기에 만반의 준비를 했습니다. 우선 스타트링크와 함께 이런 일이 일어난 원인을 분석하고 당시 일어났던 상황이 재발되지 않게 하기 위한 기술적 조치를 취했습니다. 본선도 BOJ에서 치루는 것으로 결정했으나, 혹시 모를 사태에 대비하기 위해 UCPC 운영진도 DOMjudge 서버를 직접 구축해 대비했습니다.

본선(8월 1일):

이미지
대회 본부

정말 다행이게도 본선대회는 아무 문제 없이 순조롭게 잘 진행되었습니다.

서버 대비와 별개로 본선대회를 위해 준비한 것들이 몇 개 더 있었습니다. 그 중 가장 눈여겨볼만했던 건, 대회 중에도 공지했던 바 있지만, 이번 UCPC는 스코어보드 공개의 재미를 위해 프리즈 기준을 다소 특이하게 잡았던 것이었습니다.

프리즈 시간은 대회 종료 60분 전이었으나, 프리즈 시간과 관계없이 어떤 팀이 9문제를 해결한 순간 이후 그 팀의 모든 제출이 비공개되는 식이었습니다. 이를 위해 BOJ에서 스코어보드를 제공하지 않고 scoreboard.ucpc.me라는 별도의 사이트에 스코어보드를 띄웠습니다. 박수찬tncks0121님께서 운영자 스코어보드의 모든 제출을 $n$초마다 가져와서 가릴 건 가리고 공개 스코어보드에 보여주는 파이썬 스크립트를 짜 주셔서 가능했던 일이었습니다.

풀이는 원래 라이브로 방송하려 했으나, 풀이 슬라이드가 대회 중에 완성되기도 했고, 진행을 비교적 여유롭게 하기 위해 녹화방송으로 바꿔 진행했습니다. 풀이 슬라이드가 방송에서 사용한 것과 공개된 것이 다른데, 방송에서의 풀이 슬라이드는 출제진이 생각한 난이도 순서대로 문제가 정렬되어 있고, 공개된 풀이 슬라이드는 A, B, C.. 순입니다. 특별한 이유가 있다면 공개 슬라이드에서는 풀이가 필요한 문제를 더 빨리 찾게 하기 위함이었습니다.

본선 해설 및 스코어보드 공개 영상

본선대회를 성공적으로 종료하고 저를 제외한 운영진은 고기를 맛있게 먹으러 갔다고 합니다. 저는 안타깝게도 당일 너무 피로해서 그냥 집에 와서 곯아떨어졌습니다. 비극적인 엔딩이네요.

어땠나

힘들지만 의미있는 경험이었다고 말하면 식상할까요?

힘들었던 것들

전대프연 회장을 하는 것은 힘든 일이라고 익히 들어서 알고 있었지만 구체적으로 어떤 게 힘든 일인지는 잘 몰랐습니다. 이제 대략 알게 되었습니다.

  • 후원사를 구하기가 상당히 힘들었습니다. 온라인이어서 더 그랬습니다. 올해 ICPC도 후원 사정이 좋지 않다는 걸 생각하면 어디나 비슷한 것 같습니다. 그래서 개인적으로 옆 나라 리저널의 후원 사정이 꽤 부러웠습니다.
  • 상금 처리라던가 참가 상품을 택배로 보내야 했던 것도 힘든 점 중 하나였습니다.
  • 6월 말에 넥슨코리아 엔진스튜디오에 산업기능요원으로 입사하게 되었습니다. 6월까진 무직 백수여서 몰랐는데, 대회 코디네이팅과 왕복 3시간의 출퇴근 생활을 병행하는 것은 체력적으로 상당히 힘든 일이었습니다. 회식 도중에 나와서 대회 개최를 준비했던 적도 있습니다.
  • 이외에는, 참가자 등록이 번거로웠습니다. 특히 재학증명서와 휴학증명서 등을 일일이 확인하는 작업이 너무 번거롭고 힘들었습니다.
후원사 구하기와 재학증명서 처리는 사천왕 중에서도 최약체…

그렇지만 저는 온사이트 대회를 준비했던 건 아니었기 때문에 다른 해보다는 비교적 쉽게 준비한 것이 아닌가 싶습니다.

놓쳤던 것들

대회 중에 발생한 이런저런 예외적인 상황들에 대해 제대로 and/or 빠르게 대처하지 못했던 게 아쉬웠습니다. 앞서 언급했던 것들만 다시 언급하자면, 가령…

  • GMail은 하루 발신 제한량이 있었고, 제가 shiftpsh.com과 ucpc.me 도메인으로 발신하기 위해 개인적으로 월정액을 내고 사용했던 메일서버에도 마찬가지로 하루 발신 제한량이 있었습니다.
  • 사소하게는 call for tasks 메일 계정과 Slack을 연동시켜 주는 Zapier 스크립트가 간헐적으로 동작하지 않는 문제가 있어서 공모받은 문제를 확인하지 못할 뻔 하기도 했습니다.
  • 이메일 주소를 이메일 확인 등의 방법으로 검증하지 않아 메일 전송 과정 중에서도 누락되는 메일들이 발생했습니다. Google Forms를 사용하는 대신 직접 대회 등록 사이트를 만들었다면 좋았을 것입니다. 위의 이유와 맞물려 메일을 자동으로 발송해 주는 시스템이 있었다면 더 좋았을 것입니다.
  • 대회 서버가 다운되었을 때 의논할 시간이 부족한 상황에서 대회 진행 형식을 결정해야 했습니다. 이런 상황이 발생했을 때는 미리 어떻게 하면 좋겠다는 계획을 세웠더라면 참가자들의 피해와 스트레스를 줄일 수 있었을 것입니다.
  • 방송 계획과 대본을 미리 짜놓지 못해 다소 매끄럽지 못하게 진행된 것 같아 아쉬웠습니다.
  • (이건 예외적인 상황은 아니었고, 제가 정신없어서였지만) 제 불찰로 후원사와의 소통이 제대로 진행되지 못한 부분이 있었고, 안타깝게도 이로 인해 다소 불미스러운 일이 발생했습니다.

UCPC는 이제 예선 기준으로 참가 인원 1,000명을 바라보고 있을 정도로 커진 대회입니다. 코딩 테스트 열풍으로 인해 알고리즘 문제해결 및 경쟁 프로그래밍 입문자들이 갈수록 많아지고 있고, 이런 기조가 사그라들지 않는 한 대회 규모는 계속 커질 것으로 생각됩니다. 이런 규모의 대회라면, 이런 규모의 대회에서 일어날 수 있는 갖가지 상황들을 미리 파악하고 숙고하여 대비하는 것이 옳겠다고 뒤늦게 느낍니다.

그럼에도 좋았던 것들

우여곡절도 많았지만 전대프연으로써는 처음 시도했던 온라인 대회를 성공적으로 마무리할 수 있어서 뿌듯합니다. 코로나 시국도 프로그래밍 대회는 이기지 못했네요. 😎

대단하고 멋진 분들과 함께 최고의 커뮤니티 대회를 만들 수 있어서 즐겁고 뿌듯했습니다. 온라인 대회여서 안타깝게도 참가자 분들과는 만나지 못했지만요.

그래서 회장 1년 더 하나요?

이 팀은 사실 시프트를 제외한 레드시프트 팀인데, 제가 대회 같이 안 치고 혼자 운영하러 가서 삐진 나머지 이름을 이렇게 지었나 봅니다

사실 UCPC 2020 직후에도 SUAPC에서 운영과 출제를 했고, 신촌 캠프 대회와 SNUPC에서도 검수 및 조판으로 참여했습니다. UCPC에서 얻은 경험과 리소스가 상당히 많은 도움이 되었습니다.

운영진 16콤보

하지만 내년에도 회장을 할지는 잘 모르겠습니다. 일단 이제 직장에 다니고 있기도 하고, 무엇보다 결정적으로 휴학생 팀으로 나간 ICPC 2020 인터넷 예선에서 너무 처참한 성적을 받았기 때문입니다.

여러 대회를 운영하고 출제하고 검수하느라 바빴고, 게다가 solved.ac 개발로도 바빴던 나머지 제가 문제해결 연습을 할 시간이 부족해져서라고 생각했고, 지금은 다시 팀 연습도 하고 코드포스도 자주 나가고 BOJ 문제도 열심히 풀고 있습니다. 내년 대회에는 참가자로서 참여하고 싶습니다. 복학할 때 적의환향赤衣還鄕해서 레드시프트 이름값 해야죠.

이런 현실이… 이런 현실이 있단 말이냐?

결론은 내년 전대프연을 이끌어 주실 분을 모십니다. 뭐 없으면 어쩔 수 없고…

마치면서

전대프연과 UCPC에 특별한 관심을 갖고 지원해 주신 고려대학교 SW중심사업단, 마인즈랩네이버 D2, 그리고 알고스팟구종만님과 케니소프트박현민525hm님께 깊은 감사를 드립니다. 특히 예선 서버 문제로 새벽 코딩을 불사하며 끝까지 이슈 해결을 위해 수고해 주신, 전대프연의 초대 회장이자 이제는 스타트링크최백준baekjoon님께 각별한 감사를 드립니다.

검수는 물론 대회 운영 전반에 있어서 기술적으로 많은 도움을 주신 박수찬tncks0121님, 훌륭한 문제를 출제해 주신 김동현kdh9949님, 김창동sait2000님, 나정휘jhnah917님, 노영훈Diuven님, 모현ahgus89님, 문창현ckdgus2482님, 반딧불79brue님, 배근우functionx님, 심유근cozyyg님, 이동관windflower님, 이상헌evenharder님, 이종영moonrabbit2님, 정기웅QuqqU님, 조창민Ronaldo님, 그리고 열정적으로 검수해 주신 류호석rhs0266님과 홍은기pichulia님께 진심으로 감사의 말씀을 드립니다.

이외에도 대회 막바지에 운영에 큰 도움을 주신 공인호inh212님, 김영현kipa00님과, 실험적인 형태의 대회임에도 대회 진행자를 흔쾌히 맡아 주신 정재헌Gravekper님께도 대단히 감사드립니다.

마지막으로, UCPC 2020에 참가해 주신, 알고리즘 문제해결을 사랑해 주시는 참가자 여러분께 감사드립니다.


대회 리소스

다른 프로그래밍 대회를 개최하시는 데 도움이 될 수 있도록 UCPC 2020에서 사용된 자료들을 인터넷에 공개했습니다.

오픈소스

  • ucpcc/ucpc2020-site UCPC 2020 대회 사이트
    Jekyll로 제작한 정적 사이트입니다. 대회 공지사항 등을 적기 위해 만들었습니다.
  • ucpcc/problemsetting-guidelines UCPC 디스크립션 작성 및 포매팅 컨벤션
    UCPC 문제 제작을 위해 수립한 컨벤션입니다. 일관적인 데이터와 디스크립션 작성에 도움을 줄 수 있습니다.
  • ucpcc/ucpc2020-description-layout UCPC 2020 문제지 레이아웃
    마개조된 olymp.sty입니다. 2019 서강대학교 프로그래밍 대회 문제지 레이아웃을 바탕으로 제작했습니다.
  • ucpcc/ucpc2020-solutions-theme UCPC 2020 솔루션 Beamer 테마
    Beamer와 함께 사용할 수 있는 테마입니다.
  • ucpcc/ucpc2020-broadcast-scene UCPC 2020 방송 씬
    OBS가 씬에 웹 브라우저를 사용할 수 있다는 사실에 착안하여 React로 제작한 16:9 방송 씬입니다.

공유 문서

  • UCPC 2020 문제 출제 현황 시트
    대회 운영에 활용했던 출제 현황 시트 레이아웃입니다. 운영 당시 그대로의 시트는 아니고, 이해를 돕기 위해 체크박스 상황은 연출했으며 미사용 문제들은 다른 곳에서 사용될 수 있으므로 관련 정보를 지웠습니다. 사용하고자 하실 경우 파일 > 사본 만들기를 누르면 수정 가능한 사본을 만들어 사용해 주세요.

다른 글

SCPC 2020 2차 예선에 참가했습니다 (2/3)

2차 예선 – 750/1,000점

2차 예선에서 1, 2, 3, 5번을 풀어서 1,000점 만점에 750점을 받았습니다.

4번 문제보다 5번이 구현이 쉬워 보여서 5번을 먼저 해결했습니다. 이후 부분 점수를 보니 1번 + 2번 + 3번 + 4번 + 5번 47점 = 747점이었고, 이는 1번 + 2번 + 3번 + 5번 = 750점보다 적은 점수여서, 27위 안에 들었음을 확신하고 4번을 느긋하게 건들어 보다가 포기했습니다.

제 2차 1, 2, 3, 5번 풀이를 공유합니다. 4번 문제는 구현하지 않아서, 대략적인 아이디어만 갖고 있습니다.

2차 1번 – 실력 맞추기

각각 $N \leq 300\ 000$명의 멤버가 있는 A팀과 B팀이 있습니다. 멤버들은 각각의 실력 값을 갖고 있습니다. 이 때, A의 멤버를 최대 한 명까지 교체해서, A팀의 멤버 한 명과 B팀의 멤버 한 명씩을 매칭했을 때 전체 매칭의 실력 차의 합이 최소가 되게 하고 싶습니다.


두 가지 관찰을 할 수 있습니다.

  • A팀에서 멤버 교체가 일어나지 않는 경우에는, A팀의 실력 값과 B팀의 실력 값을 각각 정렬해서 큰 순서대로 한 명씩 매칭해주는 것이 최적임은 자명합니다.
  • 한 명을 교체하는 경우에는, 어떻게 교체하더라도 어떤 B팀 멤버가 있어서 그 멤버의 실력과 같도록 교체해 주는 것이 무조건 이득입니다. 그리고 이 경우 새롭게 매칭된 멤버들의 실력 차는 $0$입니다.

따라서 A팀에서 한 명을 교체한다기보다는, A팀과 B팀에서 한 명씩을 제외하고 나머지를 적절히 매칭하는 것을 생각할 수 있습니다. 이를 해결하기 위해 A팀과 B팀을 각각 정렬해 두고, 다음과 같은 다이나믹 프로그래밍을 생각할 수 있습니다.

  • $dp\left(i,0\right)$: A팀과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
    따라서 $dp\left(i,0\right) = dp\left(i-1,0\right) + \left|A_i-B_i\right|$입니다.
  • $dp\left(i,1\right)$: A팀 한 명을 제외하고, A팀의 $\left[0, i\right]$과 B팀의 $\left[0, i – 1\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
    따라서 $dp\left(i,1\right) = \min\left\{ dp\left(i-1,0\right), dp\left(i-1,1\right) + \left|A_i-B_{i-1}\right| \right\} $입니다.
  • $dp\left(i,2\right)$: B팀 한 명을 제외하고, A팀의 $\left[0, i – 1\right]$과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
    따라서 $dp\left(i,2\right) = \min\left\{ dp\left(i-1,0\right), dp\left(i-1,2\right) + \left|A_{i-1}-B_i\right| \right\} $입니다.
  • $dp\left(i,3\right)$: A팀과 B팀 중 각각 한 명씩을 제외하고, A팀과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
    따라서 $dp\left(i,3\right) = \min\left\{ dp\left(i-1,3\right), dp\left(i-1,1\right), dp\left(i-1,2\right) \right\}$입니다.

이를 전부 계산하고 나면, 정답은 $dp\left(n,0\right)$과 $dp\left(n,3\right)$ 중 작은 쪽이 됩니다. 저는 1-based index를 사용해 구현했습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

int a[200001], b[200001];
ll dp[200001][4];

const ll inf = 1e18;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;

        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + n);

        dp[1][0] = abs(a[1] - b[1]);
        dp[1][1] = 0; // ignore a[i - 1]
        dp[1][2] = 0; // ignore b[i - 1]
        dp[1][3] = 0;

        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + abs(a[i] - b[i]);
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1] + abs(a[i] - b[i - 1])); // ignore a[i - 1]
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][2] + abs(a[i - 1] - b[i])); // ignore b[i - 1]
            dp[i][3] = min({dp[i][1], dp[i][2], dp[i - 1][3] + abs(a[i] - b[i])});
        }

        cout << min(dp[n][0], dp[n][3]) << endl;
    }

    return 0;
}

2차 2번 – 고구마

고구마 $N\leq 300\ 000$개가 일렬로 길게 연결되어 있습니다. 각 고구마의 가격은 $-10^{12} \leq A_i \leq 10^{12}$로 정해져 있습니다. 음수는 상품가치가 없어 발생하는 처리 비용입니다.

$M$만큼의 예산이 있어, 연결되어 있는 고구마 덩어리를 적절히 잘라 중간 덩어리를 사 가려고 합니다. 덩어리의 크기는 중요하지 않으나, 한 덩어리만 사갈 수 있습니다. 이 때 고구마를 적절히 잘라서, 예산 $M$을 넘지 않으면서 최대한 비싸게 사가고 싶습니다.

요약하면, 최대 구간합maximum subarray sum 문제인데, 합이 $M$보다 작거나 같으면서 최대한 큰 경우를 찾아야 합니다.


제한조건 때문에, 선형 시간에 최대 구간합 문제를 해결하는 Kadane’s 알고리즘은 사용할 수 없습니다. 다만 최대 구간을 구해야 한다는 점에서 구간합 배열prefix sum array을 이용해 접근해볼 수 있습니다.

구간합 배열 $P$를 만든 후, 현재 보고 있는 인덱스가 $i$라면, $P_i-P_j \leq M$이면서 $j < i$에 대해 $P_i-P_j$의 최댓값을 구해 주면 됩니다. 이는 std::set 자료 구조에 이전 인덱스까지의 구간합들을 전부 집어넣고, $\mathcal{O}\left(\log n\right)$이 걸리는 std::set::lower_bound을 사용해 쉽게 해결할 수 있습니다. 이유는 모르겠지만 저는 대회 당시에는 std::set::upper_bound를 사용해 구현했습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;

        int n;
        ll m;
        cin >> n >> m;

        set<ll> s;
        s.emplace(0);
        ll mx = 0, prf = 0;
        for (int i = 0; i < n; i++) {
            ll x;
            cin >> x;
            prf += x;
            s.emplace(prf);
            ll v = *s.upper_bound(prf - m - 1);
            mx = max(mx, prf - v);
        }

        cout << mx << endl;
    }

    return 0;
}

2차 3번 – 아르바이트

안타깝게도 디스크립션이 정확히 기억나진 않는데요, $N \leq 200\ 000$ 크기의 배열 $A$가 주어지고, 특정 인덱스의 값을 바꾸는 연산을 $Q\leq 2\ 000$번 하려고 합니다. 이 때 각각의 연산마다 $A$의 길이 $K \leq \min\left\{200,N\right\}$의 모든 부분 배열의 구간합에 대해, 이들의 중앙값을 구해야 합니다. 단 가능한 부분 배열의 개수가 짝수 개라면, 중앙에 있는 두 값 중 더 큰 값을 구해야 합니다.


계속 변화하는 중앙값을 구해야 하는 문제로 BOJ 1572번이 있습니다. 이 문제의 경우 저는 크기가 같은 std::multiset을 두 개 만들어 두고, 한 쪽의 집합의 모든 원소가 다른 쪽의 집합의 모든 원소보다 작도록 유지해두는 방식으로 해결했습니다. 제 1572번 소스 코드는 여기에서 볼 수 있습니다.

원래 배열에 대한 생각은 접어 두고, 구간합들이 저장된 배열이 있다고 생각해 봅시다. 원래 배열에서 한 개의 원소가 바뀌면 구간합 배열에서는 최대 $K$개의 원소가 바뀝니다. $K \leq \min\left\{200,N\right\}$라는 조건 때문에, 전부 나이브하게 처리해 줘도 최대 $KQ \leq 400\ 000$번밖에 바뀌지 않으니 위와 같은 방법으로 열심히 짜면 맞을 수 있을 것이라 생각했고, 시간 초과를 받았습니다.

std::multiset의 삽입/삭제 연산의 복잡도는 $\mathcal{O}\left(\log n\right)$이지만, 상수가 크기 때문에 사용에 주의를 요합니다. 상수 커팅을 위해 다소 특이할 수 있는 세그먼트 트리를 생각해내 해결했습니다.

BOJ 1572번의 해법과 비슷하게, $mxt$와 $mnt$라는 세그먼트 트리를 각각 만들었습니다. $mxt$는 최댓값 세그먼트 트리, $mnt$는 최솟값 세그먼트 트리이며, 항상 $\max mxt \leq \min mnt$가 되도록 관리합니다. 그런데 이렇게 관리하려면, 만약 $\max mxt > \min mnt$일 때 $mxt$의 최댓값을 $mnt$의 최솟값과 바꿔 줘야 하고, 또한 특정 인덱스 $i$에 대해 값 업데이트도 가능해야 합니다.

이를 위해 트리의 노드에는 최대/최솟값과, 그 최대/최솟값이 들어 있는 배열에서의 인덱스를 저장하도록 했습니다. 또한, 랜덤 액세스를 쉽게 하기 위해, 두 세그먼트 트리의 크기는 $N-K+1$로 고정해 두고, 노드에 저장된 값이 $-1$인 경우 이 트리의 이 인덱스에 값이 존재하지 않음을 의미하도록 했습니다.

정해인지는 잘 모르겠습니다. 어떻게 잘 하면 느리게 갱신lazy propagation하는 테크닉을 섞어서 좀 더 빠르게 할 수도 있을 것 같기도 한데, 아래 코드도 만점을 받아서 더 이상 생각을 하지 않기로 했습니다.

들리는 말로는 크기 $NK$의 펜윅 트리로도 해결할 수 있다고 합니다. 하긴 펜윅이 빠르긴 빠르니까요.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

struct node {
    int i, v;

    node() : i(0), v(0) {}

    node(int i, int v) : i(i), v(v) {}

    bool operator<(const node &rhs) const {
        return v < rhs.v;
    }
};

node mnt[524288], mxt[524288];
int a[200001], val[200001], vals[200001];
ll prf[200001];
int tn, mxs, mns;

node minimum() { return mnt[1]; }

node maximum() { return mxt[1]; }

node argmin(const node &lhs, const node &rhs) {
    if (lhs.v == -1) return rhs;
    if (rhs.v == -1) return lhs;
    return min(lhs, rhs);
}

node argmax(const node &lhs, const node &rhs) {
    if (lhs.v == -1) return rhs;
    if (rhs.v == -1) return lhs;
    return max(lhs, rhs);
}

void setn(int i, int v, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e && s == i) {
        mnt[x].v = v;
        return;
    }
    if (i <= (s + e) / 2) {
        setn(i, v, x * 2, s, (s + e) / 2);
    } else {
        setn(i, v, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

void setx(int i, int v, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e && s == i) {
        mxt[x].v = v;
        return;
    }
    if (i <= (s + e) / 2) {
        setx(i, v, x * 2, s, (s + e) / 2);
    } else {
        setx(i, v, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
}

void update(int i, int dx, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e) {
        if (mxt[x].v != -1) mxt[x].v += dx;
        if (mnt[x].v != -1) mnt[x].v += dx;
        return;
    }
    if (i <= (s + e) / 2) {
        update(i, dx, x * 2, s, (s + e) / 2);
    } else {
        update(i, dx, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

void init(int x = 1, int s = 0, int e = tn - 1) {
    if (s == e) {
        mnt[x].i = mxt[x].i = s;
        if (s >= tn / 2) {
            mxt[x].v = -1, mnt[x].v = vals[s];
            mns++;
        } else {
            mnt[x].v = -1, mxt[x].v = vals[s];
            mxs++;
        }
        return;
    }
    init(x * 2, s, (s + e) / 2);
    init(x * 2 + 1, (s + e) / 2 + 1, e);
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

bool exchange() {
    const auto mx = maximum(), mn = minimum();
    if (mx.v <= mn.v) return false;
    // set mntree
    setn(mn.i, -1);
    setn(mx.i, mx.v);
    // set mxtree
    setx(mx.i, -1);
    setx(mn.i, mn.v);
    return true;
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;

        int n, k, q;
        cin >> n >> k >> q;
        tn = n - k + 1;

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            prf[i] = prf[i - 1] + a[i];
        }

        for (int i = k; i <= n; i++) {
            val[i - k + 1] = prf[i] - prf[i - k]; // [1, n - k + 1]
            vals[i - k] = val[i - k + 1];
        }

        init();
        while (exchange());

        cout << minimum().v << ' ';
        while (q--) {
            int i, v;
            cin >> i >> v;
            int d = v - a[i];
            for (int j = max(0, i - k); j < min(i, tn); j++) {
                update(j, d);
            }
            while (exchange());
            cout << minimum().v << ' ';
            a[i] = v;
        }
        cout << endl;
    }

2차 4번 – 안전운전

도로의 왼쪽, 오른쪽 경계와 운전 경로가 주어집니다. 도로 정보와 운전 경로는 선분들로 이루어져 있으며, 각각 $x$축 또는 $y$축과 평행합니다. 이 때, 운전 경로 중 특정한 가로선 하나 이하에 대해, 그 이후의 경로를 적절히 선대칭시켜서, 도로 안에 포함된 운전 경로의 세로선들의 길이의 합이 최대가 되게 하고 싶습니다. 단, 선대칭 이후의 도로 경로가 더 길어져서는 안 됩니다.


좌표 압축 후 위에서부터 아래로 내려오면서 스위핑 or 1차 4번과 비슷한 식의 세그먼트 트리를 이용하면 풀릴 거라고 생각했습니다. 하지만 1, 2, 3, 5번을 해결한 시점에서 이미 2차 예선 26위 이상임이 확정되었기 때문에 구현하다 포기했습니다.

2차 5번 – 삼각형의 거리

꼭지점 $N \leq 300$개의 단순다각형simple polygon이 있습니다. 오목할 수도 있습니다. 이 다각형의 꼭지점들을 이어 전부 삼각형으로 분할하고자 합니다.

어떤 삼각형에서 다른 삼각형과 맞닿은 변만을 통해 이동한다고 할 때, 삼각형 간의 거리를 정의할 수 있습니다. 예를 들어, 현재 삼각형과 맞닿아 있는 삼각형까지의 거리는 1이 됩니다. 처음 주어진 다각형을 잘 분할해서, 두 삼각형 사이의 최대 거리가 최소가 되도록 하고 싶습니다.


이 문제의 Small 셋의 경우, 다각형이 볼록다각형이므로 ICPC 2019 Korea Regional J번과 같은 문제입니다. 실제 대회에서 제가 First Solve로 해결했던 문제라 기억에 잘 남아 있던 것이 도움이 되었습니다.

다각형의 삼각 분할은 모든 노드의 $\deg \leq 3$인 트리로 나타낼 수 있습니다. 삼각 분할을 트리로 나타냈을 때, 이 트리의 지름을 최소화하는 문제가 됩니다.

주어진 도형을 어떤 대각선 하나로 자르면, 그 대각선 오른쪽에 만들어질 삼각형은 대각선 왼쪽에 만들 삼각형과 무조건 이어집니다. 이걸 바탕으로 2차원 다이나믹 프로그래밍을 생각해볼 수 있습니다. 현재 $i$번째 점 $P_i$부터 $j$번째 점 $P_j$까지만을 사용해 만든 도형이 있고, $\overline{P_iP_j}$는 어떤 다른 삼각형과 맞닿아있다고 생각해 봅시다. 한 쪽이 뚫려 있는 다각형이라고 생각하면 됩니다. 아래 그림의 핑크색 부분이 되겠네요.

이제 $dp \left(i,j\right)$를 핑크색 도형을 어떻게 잘 삼각분할했을 때 $\overline{P_iP_j}$에서 다른 삼각형까지의 최단 거리라고 정의합시다. 그러면 모든 $i<k<j$에 대해, 삼각형 $P_iP_jP_k$가 원래 다각형 안에 포함되는 경우 그 삼각형으로 분할한 뒤 재귀적으로 DP 문제를 해결할 수 있겠습니다.

따라서 $P_iP_jP_k$가 삼각형이 되는 모든 $i<k<j$들의 집합을 $K_{ij}$라 하면, 최단 거리는 $\overline{P_iP_k}$ 쪽에서 오거나 $\overline{P_kP_j}$ 쪽에서 오는 두 가지 경우가 있으므로, $dp\left(i,j\right)$는 다음과 같이 구할 수 있습니다.

\[dp\left(i,j\right)=\begin{cases} 0 & \textrm{if } i+1=j \\ \min_{k \in K_{ij}} \left\{ dp\left(i,k\right),dp\left(k,j\right) \right\}+1 & \textrm{otherwise} \end{cases}\]

하지만 이걸로는 트리의 지름을 구하기엔 역부족입니다. 왜냐하면, 이 다이나믹 프로그래밍의 경우 $\overline{P_iP_k}$에서 $\overline{P_iP_j}$ 쪽으로, $\overline{P_kP_j}$에서 $\overline{P_iP_j}$ 쪽으로 가는 건 고려하고 있지만, $\overline{P_iP_k}$에서 $P_iP_jP_k$를 거쳐 다시 $\overline{P_kP_j}$ 쪽으로 나가는 경로는 고려하지 못하고 있기 때문입니다.

점화식을 다시 정의해 봅시다. 어떤 값 $d$가 있어서, $dp_d \left(i,j\right)$를 다음과 같이 정의합니다.

\[dp_d\left(i,j\right)=\begin{cases} 0 & \textrm{if } i+1=j \\ \min_{k \in K_{ij}} \left\{ dp_d\left(i,k\right),dp_d\left(k,j\right) \right\}+1 & \textrm{if } dp_d\left(i,k\right)+dp_d\left(k,j\right) \leq d \\ \infty & \textrm{otherwise}\end{cases}\]

이제 이 점화식을 이용해 $dp_d\left(0,n-1\right)$를 구했고 그 값이 $\infty$가 아니라면, 트리의 지름이 $d$ 이하가 되도록 다각형을 삼각 분할할 수 있다는 뜻이 됩니다. 이제 이분 탐색으로 $d$의 최소값을 결정할 수 있습니다.

다이나믹 프로그래밍 한 번에 $\mathcal{O}\left(n^3\right)$이고, $0 \leq d \leq n-3$이므로 총 $\mathcal{O}\left(n^3 \log n\right)$만에 문제를 해결할 수 있습니다. 어떤 대각선이 오목다각형 안에 있는지 아닌지 판정하는 방법은 여러 가지가 있으나 문제의 포커스는 이게 아닌 것 같으므로 스킵하도록 합시다.

대회가 끝나고 안 사실인데 이 문제를 해결하는 논문이 있었다고 합니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

struct point {
    int x, y;

    point() : x(0), y(0) {}

    point(int x, int y) : x(x), y(y) {}

    point operator*(const int &rhs) const {
        return {x * rhs, y * rhs};
    }

    point operator+(const point &rhs) const {
        return {x + rhs.x, y + rhs.y};
    }

    point operator-(const point &rhs) const {
        return *this + (rhs * -1);
    }
};


int ccw(const point &a, const point &b, const point &c) {
    point bb = b - a, cc = c - a;
    ll t = (ll) bb.x * cc.y - (ll) cc.x * bb.y;
    return t ? (t > 0 ? 1 : -1) : 0;
}

bool intersects(const point &la, const point &lb, const point &ma, const point &mb) {
    if (ccw(la, lb, ma) * ccw(la, lb, mb) != -1) return false;
    if (ccw(ma, mb, la) * ccw(ma, mb, lb) != -1) return false;
    return true;
}

point A[300];

const int inf = 1e8;

int dp[300][300], dg[300][300];

bool diag(int i, int j, int n) {
    if (i > j) swap(i, j);
    if (dg[i][j] != -1) return dg[i][j];
    if (i == j || i + 1 == j) return dg[i][j] = false;
    if (i == 0 && j == n - 1) return dg[i][j] = false;

    for (int v = 0, u = n - 1; v < n; u = v++) {
        if (intersects(A[i], A[j], A[u], A[v])) return dg[i][j] = dg[j][i] = false;
    }

    point V1 = A[(i + 1) % n] - A[i], V2 = A[(i + n - 1) % n] - A[i], V3 = A[j] - A[i];
    ll a = (ll) V1.x * V2.y - (ll) V1.y * V2.x;
    ll b = (ll) V1.x * V3.y - (ll) V1.y * V3.x;
    ll c = (ll) V3.x * V2.y - (ll) V3.y * V2.x;
    bool in = (a >= 0 && b >= 0 && c >= 0) || (a < 0 && !(b < 0 && c < 0));
    if (!in) return dg[i][j] = dg[j][i] = false;
    return dg[i][j] = dg[j][i] = true;
}

int f(int i, int j, int d, int n) {
    if (i + 1 == j) return dp[i][j] = 0;
    if (!(i == 0 && j == n - 1) && !diag(i, j, n)) return dp[i][j] = inf;
    if (dp[i][j] != -1) return dp[i][j];

    dp[i][j] = inf;

    for (int k = i + 1; k < j; k++) {
        if (!(i + 1 == k || diag(i, k, n))) continue;
        if (!(k + 1 == j || diag(k, j, n))) continue;
        if (f(i, k, d, n) + f(k, j, d, n) > d) continue;
        dp[i][j] = min(dp[i][j], max(f(i, k, d, n), f(k, j, d, n)) + 1);
    }

    return dp[i][j];
}

bool sat(int d, int n) {
    memset(dp, -1, sizeof dp);
    return f(0, n - 1, d, n) != inf;
}

int g(int x) {
    if (x == 3) return 0;
    if (x == 4) return 1;
    if (x == 5) return 2;
    return g((x + 1) / 2) + 2;
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;

        int n;
        cin >> n;

        memset(dg, -1, sizeof dg);

        for (int i = 0; i < n; i++) {
            cin >> A[i].x >> A[i].y;
        }

        if (n == 3) {
            cout << 0 << endl;
            continue;
        }

        int l = g(n), h = n - 3;
        while (l < h) {
            int m = (l + h) / 2;
            if (sat(m, n)) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        cout << l << endl;
    }

    return 0;
}

회사 프로젝트에서 KaTeX를 한 번 사용해 본 이후로 제 블로그의 모든 수식을 KaTeX로 바꾸고 있습니다. 렌더 속도가 훨씬 빨라졌고, 모바일에서 수식 자동 줄바꿈이 잘 됩니다. 개인적으로는 여러 면에서 MathJax보다 좋은 라이브러리라고 생각합니다.

SCPC 2020 1차 예선에 참가했습니다 (1/3)

1차 예선 – 600/800점

1차 예선에서 1, 2, 3, 4번을 풀어서 800점 만점에 600점을 받았습니다. 부분 점수는 못 받았습니다.

다음 날 수술이 있었고, 4번까지 풀고 나니 새벽이어서 5번은 안 풀고 잤습니다. 전체적으로 디스크립션이 난해한 느낌이라 안타까웠습니다.

제 1차 1, 2, 3, 4번 풀이를 공유합니다.

1차 1번 – 다이어트

A 식당과 B 식당이 있고, 이 식당에는 각각 $N \leq 50\ 000$개의 메뉴가 있습니다. 이 메뉴들의 칼로리 값들이 주어집니다. $K$일동안 매일 A에서 한 끼를, B에서 한 끼를 먹을 때, 하루에 먹은 칼로리의 양의 최댓값이 최소가 되게 하고 싶습니다.


A 식당에서의 최대 칼로리의 음식을 순서대로, B 식당에서 최소 칼로리의 음식을 순서대로 $K$일간 하나하나 그리디하게 매칭해 주면 됩니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

int a[200000], b[200000];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        int n, k;
        cin >> n >> k;

        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        for (int i = 0; i < n; i++) cin >> b[i];
        sort(b, b + n);
        int mx = 0;
        for (int i = 0; i < k; i++) mx = max(mx, a[i] + b[k - i - 1]);
        cout << mx << '\n';
    }


    return 0;
}

1차 2번 – 카드 게임

$N \leq 3\ 000$개의 카드가 쌓여 있는 두 덱 X와 Y가 있습니다. 각 카드에는 $K \leq 3\ 000$ 이하의 양의 정수가 적혀 있습니다. 두 명이 번갈아 카드를 가져가는데,

  • 꼭 한 개의 덱을 선택해서 위에서부터 한 장 이상을 가져가야 하며,
  • 가져간 카드의 합이 $K$ 이하여야 하고,
  • 마지막으로 카드를 가져가는 사람이 집니다.

내 턴에 덱 X에 $i$장의 카드가, 덱 Y에 $j$장의 카드가 남아 있는 상태를 $\left(i,j\right)$라고 한다면, $N$과 $K$가 정해져 있는 게임에 대해 중간 상태로 가능한 경우는 총 $\left(N+1\right)^2$개입니다. 각각의 상태에서 두 플레이어가 각각 최선의 방법으로 플레이했을 때 내가 반드시 이기는 경우와 반드시 지는 경우의 갯수를 세고 싶습니다.


Grundy number를 바로 떠올릴 수 있겠지만, 아쉽게도 마지막으로 카드를 가져가는 사람이 지는 게임(misère)이기 때문에 Grundy를 쓸 수 없습니다. Grundy로 접근하기 전에 ‘이게 1차 예선 2번에 나올 수 있을 만한 지식인가?’를 생각해 볼 필요가 있습니다.

대신 다이나믹 프로그래밍으로 접근할 수 있습니다.

  • 현재 상태 $\left(i,j\right)$에서 내가 어떤 덱에서 얼마나 많이 가져가더라도 다음 플레이어가 이기는 상태만 나온다면, 현재 상태는 내가 지는 상태입니다.
  • 그렇지 않다면, 내가 특정한 동작을 하면 다음 플레이어가 지는 상태를 만들 수 있습니다. 이런 경우 현재 상태는 내가 이기는 상태입니다.

따라서, DP 테이블을 만들어둔 후 가져간 카드의 합이 $K$ 이하가 되도록 X에서 하나씩, Y에서 하나씩 가져가면서 다음 플레이어가 이기는 상태가 있는지 확인해 주면 됩니다. 이 계산을 $\left(N+1\right)^2$개에 대해 하므로, $\mathcal{O}\left(N^3\right)$입니다.

$N \leq 3\ 000$이므로 Large 셋을 풀기에는 불충분합니다. 이는 Prefix sum을 이용해 $\mathcal{O}\left(N^2\right)$로 최적화할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

int x[3010], y[3010], xp[3010], yp[3010], xi[3010], yj[3010];
bitset<3010> dp[3010];
int prs[3010][3010];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        memset(dp, 0, sizeof dp);
        dp[0][0] = true;

        int n, k;
        cin >> n >> k;

        for (int i = 1; i <= n; i++) {
            cin >> x[i], xp[i] = x[i] + xp[i - 1];
            int v = xp[i] - k - 1;
            int ii = upper_bound(xp, xp + i, v) - xp;
            xi[i] = ii;
        }
        for (int j = 1; j <= n; j++) {
            cin >> y[j], yp[j] = y[j] + yp[j - 1];
            int v = yp[j] - k - 1;
            int jj = upper_bound(yp, yp + j, v) - yp;
            yj[j] = jj;
        }

        int a = 0, b = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                int xc = (prs[i][j + 1] - prs[xi[i]][j + 1] - prs[i][j] + prs[xi[i]][j]);
                int yc = (prs[i + 1][j] - prs[i + 1][yj[j]] - prs[i][j] + prs[i][yj[j]]);

                dp[i][j] = ((i - xi[i]) - xc) || ((j - yj[j]) - yc);
                dp[0][0] = true;
                (dp[i][j] ? a : b)++;
                prs[i + 1][j + 1] = dp[i][j] + prs[i][j + 1] + prs[i + 1][j] - prs[i][j];
            }
        }

        cout << prs[n + 1][n + 1] << ' ' << (n + 1) * (n + 1) - prs[n + 1][n + 1] << endl;
    }


    return 0;
}

1차 3번 – 사다리 게임

$N \leq 1\ 500$개의 세로선과 $K \leq 2\ 000$개의 가로선이 있는 사다리가 있습니다.

$M \leq 100\ 000$개의 쿼리가 들어옵니다. $\left(i,j\right)$의 형태입니다. 위의 $i$번 위치에서 시작해서 아래의 $j$번 위치에서 끝나도록 가로선을 적절히 없애 사다리를 조작하고 싶은데, 가로선을 최소한으로 없앴을 때 몇 개 없애야 하는지를 구해야 합니다.

Kotlin Heroes: Episode 4의 E번 문제와 상당히 비슷합니다.


가로선들이 그래프의 간선들이라고 생각하고 접근해서 최단 거리 문제로 해결했습니다.

$u$와 $v$를 잇는 가로선이 있다면, 가로선을 무시하는 경우($u \rightarrow u$, $v \rightarrow v$)를 가중치 $1$로, 무시하지 않는 경우($u \rightarrow v$, $v \rightarrow u$)를 가중치 $0$으로 하여 간선 $4$개로 만들어 줍니다.

정점은 $N$개를 처음에 만들어 주고, 가로선을 하나 처리할 때마다 가로선의 끝점에 각각 하나씩, 총 $2$개를 더 만들어 줍니다. 이렇게 그래프를 구성하면 노드는 총 $N+2K \leq 5\ 500$개가 됩니다.

이렇게 하면 각 시작점마다 Dijkstra 혹은 0-1 BFS를 돌리는 것으로 각 종점까지의 최단거리를 구하면, 그것이 시작점에서 종점까지 가면서 제거해야 하는 가로선의 개수의 최댓값이 됩니다. 이 방법을 이용해 쿼리 값들을 전부 전처리해둔 후, 쿼리가 들어오는 대로 전처리된 값들을 출력해 주려고 합니다.

만들어 준 그래프의 정점은 $N+2K$개, 간선은 $4K$개이므로 0-1 BFS의 경우 한 번에 $\mathcal{O}\left(N+K\right)$, Dijkstra의 경우 한 번에 $\mathcal{O}\left(K \log K\right)$입니다. 이를 모든 시작점에 대해 한 번씩 돌려주면 0-1 BFS의 경우 $\mathcal{O}\left(N^2+NK\right)$, Dijkstra의 경우 $\mathcal{O}\left(NK \log K\right)$만에 해결할 수 있습니다. 저는 그냥 Dijkstra로 해결했습니다.

DP로도 해결할 수 있다고 합니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

pii seg[2000];
int last[1500], dist[1500][1500], dtemp[9000];
bitset<9000> vis;

void dijk(int s, const vector<vector<pii>> &graph) {
    memset(dtemp, -1, sizeof dtemp);
    vis.reset();
    priority_queue<pii> pq;
    dtemp[s] = 0;
    pq.emplace(0, s);
    while (pq.size()) {
        int u = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (dtemp[u] < d) continue;
        if (vis[u]) continue;
        vis[u] = true;
        for (const auto &kv : graph[u]) {
            int v = kv.first, c = kv.second;
            if (dtemp[v] == -1 || dtemp[u] + c < dtemp[v]) {
                dtemp[v] = dtemp[u] + c;
                pq.emplace(-dtemp[v], v);
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        memset(dist, -1, sizeof dist);

        int n, k, q;
        cin >> n >> k >> q;

        vector<vector<pii>> graph(n);
        for (int i = 0; i < n; i++) last[i] = i;

        for (int i = 0; i < k; i++) {
            cin >> seg[i].first >> seg[i].second;
            seg[i].first--, seg[i].second--;
        }

        for (int i = 0; i < k; i++) {
            const auto &l = seg[i];
            int gn = graph.size();
            graph[last[l.first]].emplace_back(gn, 1);
            graph[last[l.second]].emplace_back(gn + 1, 1);
            graph[last[l.first]].emplace_back(gn + 1, 0);
            graph[last[l.second]].emplace_back(gn, 0);
            last[l.first] = gn;
            last[l.second] = gn + 1;
            graph.emplace_back();
            graph.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            graph[last[i]].emplace_back(graph.size(), 0);
            last[i] = graph.size();
            graph.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            dijk(i, graph);
            for (int j = 0; j < n; j++) dist[i][j] = dtemp[last[j]];
        }

        int s = 0;
        while (q--) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            s += dist[u][v];
        }
        cout << s << endl;
    }

    return 0;
}

1차 4번 – 범위 안의 숫자

0에서 9까지의 숫자 $n \leq 50\ 000$개로 이루어진 문자열 $t$가 주어집니다. 길이가 $k \leq \min\left\{9,n\right\}$인 부분 문자열들을 수라고 생각하고, 모두 수직선 위에 둡니다.

이 때, 여기서 최대 한 글자까지를 1로 바꿔서, 어떤 정수 $a$에 대해 길이가 $m \leq 10^9$인 구간 $\left[a,a+m\right]$ 안에 속한 수의 개수의 최댓값이 최대가 되게 하고 싶습니다. 이 때의 최댓값을 구해야 합니다.


일단 $k$가 커봐야 $9$고, $n$도 그렇게 크지 않아서, 문자 하나를 1로 바꿀 수 있다는 것을 배제하고 생각하면 이 문제는 스위핑으로 해결할 수 있습니다. 부분 문자열의 값을 $x_i$라고 하면, 선분 $\left[x_i,x_i+m\right]$들을 수직선 위에 깔아 두고 가장 많이 겹쳤을 때의 선분의 갯수를 구하면 됩니다.

이제 문자 하나를 1로 바꿀 수 있는 경우를 생각해봅시다. ‘문자 하나를 1로 바꾸는 것’이라는 행위에서 관찰 가능한 특별한 성질은 딱히 없다고 느꼈습니다. 다만, 문자 하나를 1로 바꾸면 다시 만들어줘야 하는 선분의 개수는 $9$개에 불과하다는 사실에 집중했습니다.

만약 다이나믹하게 선분을 제거하고 추가할 수 있는 스위핑이 있다면, 모든 위치의 숫자를 하나하나 1로 바꾸고 되돌리는 행위를 한다고 해도 추가/제거는 $\mathcal{O}\left(kn\right)$번만 일어나므로 시간 안에 해결할 수 있을 것 같습니다.

다행히도 그런 스위핑은 존재하는데요, 최댓값을 구하는 연산과 구간에 덧셈을 하는 연산(lazy propagation 등)을 수행 가능한 세그먼트 트리로 가능합니다.

다만 인덱스가 꽤 크기 때문에 다이나믹 세그먼트 트리를 구현하거나, 가능한 값들을 전부 좌표 압축한 후 처리하는 방법을 사용해야 합니다. 저는 후자로 구현했습니다. 총 시간 복잡도는 $\mathcal{O}\left(kn \log kn\right)$입니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [t] [c] [s] */

ll tree[1048576 * 2], lazy[1048576 * 2];

int c;

void _propagate(int x, int s, int e) {
    if (!lazy[x]) return;
    tree[x] += lazy[x];
    if (s != e) {
        lazy[x * 2] += lazy[x];
        lazy[x * 2 + 1] += lazy[x];
    }
    lazy[x] = 0;
}

ll _maximum(int x, int s, int e, int l, int r) {
    _propagate(x, s, e);
    if (l > e || r < s) return 0;
    if (l <= s && e <= r) return tree[x];
    int m = (s + e) / 2;
    return max(_maximum(x * 2, s, m, l, r),
               _maximum(x * 2 + 1, m + 1, e, l, r));
}

void _update(int x, int s, int e, int l, int r, ll dv) {
    _propagate(x, s, e);
    if (l > e || r < s) return;
    if (l <= s && e <= r) {
        tree[x] += dv;
        if (s != e) {
            lazy[x * 2] += dv;
            lazy[x * 2 + 1] += dv;
        }
        return;
    }
    int m = (s + e) / 2;
    _update(x * 2, s, m, l, r, dv);
    _update(x * 2 + 1, m + 1, e, l, r, dv);
    tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
}

ll maximum(int l, int r) {
    return _maximum(1, 0, c - 1, l, r);
}

void update(int l, int r, ll dv) {
    _update(1, 0, c - 1, l, r, dv);
}

ll zip(ll x, const vector<ll> &a) {
    return lower_bound(a.begin(), a.end(), x) - a.begin();
}

ll v[50000], v1[50000][10];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        ll n, k, m;
        cin >> n >> k >> m;
        string t;
        cin >> t;

        // init values
        vector<ll> ps;
        ll curr = 0, mod = 1;
        for (int i = 0; i < k; i++) mod *= 10;
        for (int i = 0; i < k; i++) curr *= 10, curr += t[i] & 15, curr %= mod;
        for (int i = k; i <= n; i++) {
            v[i - k] = curr;
            ps.emplace_back(curr);
            ll l = curr, r = 0, p = 1;
            for (int j = 0; j < k; j++) {
                v1[i - k][j] = (l / 10 * 10 + 1) * p + r;
                ps.emplace_back(v1[i - k][j]);
                l /= 10, r += (curr / p) % 10 * p, p *= 10;
            }
            if (i == n) break;
            curr *= 10, curr += t[i] & 15, curr %= mod;
        }
        int ts = ps.size();
        for (int i = 0; i < ts; i++) ps.emplace_back(ps[i] + m);

        sort(ps.begin(), ps.end());
        ps.erase(unique(ps.begin(), ps.end()), ps.end());

        memset(tree, 0, sizeof tree);
        memset(lazy, 0, sizeof lazy);
        c = ps.size();
        // query
        for (int i = 0; i <= n - k; i++) {
            update(zip(v[i], ps), zip(v[i] + m, ps), 1);
        }

        ll mx = maximum(0, ps.size() - 1);

        for (int i = 0; i < n; i++) { // replace i-th number to 1
            // remove
            for (int j = 0; j < k; j++) {
                if (i - k + j < 0 || i - k + j > n - k) continue;
                update(zip(v1[i - k + j][j], ps), zip(v1[i - k + j][j] + m, ps), -1);
            }
            if (i <= n - k) {
                update(zip(v[i], ps), zip(v[i] + m, ps), -1);
            }
            // add
            if (i - k >= 0) {
                update(zip(v[i - k], ps), zip(v[i - k] + m, ps), 1);
            }
            for (int j = 0; j < k; j++) {
                if (i - k + 1 + j < 0 || i - k + 1 + j > n - k) continue;
                update(zip(v1[i - k + 1 + j][j], ps), zip(v1[i - k + 1 + j][j] + m, ps), 1);
            }
            // query
            mx = max(mx, maximum(0, ps.size() - 1));
        }
        cout << mx << endl;
    }

    return 0;
}

solved.ac 화이트리스트 관련 입장 (5/8)

안녕하세요, solved.ac 운영자 박수현입니다. 여기는 운영 블로그는 아니고 개인 블로그입니다만 솔브드에는 글을 적기 마땅한 곳이 없어 여기에 적기로 했습니다.

solved.ac는 작년 7월에 클로즈 베타를 시작해 지금 시점으로 10개월째 가동되고 있습니다. 화이트리스트제 클로즈 베타의 형태로 사이트를 운영한 이유들은 아래와 같습니다.

  1. 사이트 초기에는 난이도가 붙어 있었던 문제들이 너무 적었고(서강대에서의 기여~2,000건), 제대로 된 난이도 기준이 없었기에 많은 사람들이 합리적이라고 생각할 수 있는 난이도 기준의 방향을 만들어가기 위해
  2. 스타트링크는 BOJ 스크레이핑을 공식적으로 허용하지 않고 있기 때문에, 사이트의 존재를 유지하기 위해 스크레이핑하는 유저의 수를 줄일 필요가 있어서

하지만 많은 사람들이 이 사이트를 통해 문제풀이에 재미를 붙이면 좋겠다고 생각했었고 그런 생각에서 난이도 조회만은 화이트리스트에 없더라도 누구나 할 수 있게 열어두었습니다.

이후 BOJ와의 통합이 결정됨에 따라 (2)의 영향이 줄어들어 화이트리스트를 천천히 늘려나갔습니다. 현재는 15,342명의 사용자가 화이트리스트에 등록되어 있습니다. 베타를 막 시작했을 8월의 3,517명과 비교하면 5배 가량 늘어난 것입니다.

그러나 개인 화이트리스트의 부작용이 있어 개인 화이트리스트 신청을 3월부터 중단하게 되었습니다. 아래와 같은 일들 때문입니다.

  • 개인 화이트리스트의 티어 조건을 맞추기 위해 다른 사람의 소스 코드를 베껴 제출하는 일이 빈번하게 일어났습니다. solved.ac와 BOJ 모두 이런 행위를 허용하고 있지 않으며, solved.ac는 이런 사례가 발견되는 대로 해당 유저를 화이트리스트에서 삭제했습니다.
  • 개인 화이트리스트 스크레이핑의 부담이 커졌습니다. solved.ac의 현재 사이트 구조는 단체 화이트리스트 스크레이핑이 훨씬 효율적으로 동작하도록 되어 있습니다.

악의적인 사용자들의 소스 복사/붙여넣기 행위에 대한 신고가 늘어서, 제가 개인 화이트리스트 제도를 만들지 않았다면 처리하지 않았어도 될 요청들을 처리하게 되어 저뿐만 아니라 스타트링크가 다른 기능들을 개발할 시간을 뺏기게 되었습니다. 통합 작업이나 새로운 기능을 개발하는 데 시간을 쏟는 편이 통합을 기다리는 사용자들에게 훨씬 이득이 될 것이라는 판단 하에 개인 화이트리스트를 더 이상 받지 않겠다는 결정을 했습니다.

이후 일부 BOJ 이용자 분들께 여러 비난과 질책(대체로 공정하지 않다는 의견들인 것 같습니다)을 받았고, 고심 끝에 남겨두었던 단체 화이트리스트도 오는 5월 16일을 마지막으로 더 받지 않으려 합니다. 다만 BOJ와 통합이 완료되면 화이트리스트와 상관없이 누구나 사이트를 이용할 수 있게 될 예정이므로 조금만 더 기다려 주시기를 부탁드립니다.

감사합니다.


추가로 아래는 사이트에 관해 자주 해 주시는 질문들과 그에 대한 제 답변입니다.

통합되면 어떤 점이 좋은가요? – 통합되면 베타가 끝납니다. 화이트리스트가 없어지고 누구나 로그인을 할 수 있게 됩니다. 지금은 유저와 단체마다 일정 갱신 주기가 있지만 통합 이후에는 문제를 푸는 즉시 경험치가 반영되도록 할 계획입니다.

연봉 얼만가요? / 얼마 받고 일하나요? – solved.ac는 전적으로 제 개인 프로젝트이며 기부금 이외에 뭔가를 받고 있는 것은 없습니다. 다만 운영 비용은 스타트링크에서 지원받고 있습니다.

API를 제공할 예정이 있나요? – 예정은 있습니다만 우선순위는 높지 않습니다. 주된 이유는 documentation을 작성할 시간이 부족하기 때문입니다. solved.ac의 컨텐츠를 이용해 뭔가를 만들고 싶으시다면 solved.ac 사이트 자체를 크롤링하는 것보다는 플러그인 소스 코드 역공학을 통해 undocumented API 엔드포인트를 알아내 활용해 주시기 바랍니다.

소스 코드 카피로 화이트리스트 신청이 반려 / 화이트리스트에서 삭제되었습니다. 통합 후 사이트를 정상적으로 이용할 수 있나요? – 로그인은 가능해지지만, solved.ac 운영 규칙에 따라 통합 후에도 65,535일간 경험치가 0으로 고정됩니다.

2019 ICPC Asia Seoul Regional에 다녀왔습니다

[mathjax]

ICPC regional 본선으로는 두 번째고, 서울 본선으로는 첫 번째입니다. 아이러니게도 첫 번째 리저널 본선은 2019년 방콕 리저널이었습니다.

2018년에는 제가 1학년이었고, 코드포스 레이팅도 블루였고, 결정적으로 알고리즘 문제해결 자체를 시작한 지 채 1년이 안 되었을 때였기 때문에 그냥 ‘대회가 이렇게 돌아가는 거구나~’를 느끼기 위해 귀여운 새내기 동기들과 같이 나갔었는데요, 겨울에 코드포스로 나름의 하드 트레이닝을 해서 레이팅을 2000까지 끌어올린 뒤 올해는 수상을 목표로 준비하게 되었습니다. 따라서 ICPC를 진지하게 준비해본 건 올해가 처음이었고 예선부터 본선까지의 준비 기록을 한 번 정리해 보려 합니다.

팀 연습

팀 연습이라는 것을 해 본 적이 없는 저였기 때문에 팀원들에게 예전에 어떻게 했냐고 물어봤는데, 기억이 어렴풋했던 것 같습니다. 그래서 제가 어떻게든 진행을 해 봤습니다.

날짜와 장소 정하기

팀 연습은 조금 늦게 시작했던 것 같습니다. 개강하고 나서(적어도 9월에) 3명이 모두 참가할 수 있도록 날짜와 시간을 잡았습니다. 장소는 학회 아니면 PC방, 시간은 매주 2회 오후 7시 반이었습니다.

서강대학교의 경우 컴퓨터공학과 실습실 4곳을 스터디 학회들(ICPC Team, Release, CSPC Lab, CNU)이 각각 관리하는데, 실습실에 수업이 없을 경우에는 컴퓨터공학과 학생들이 자유롭게 사용할 수 있도록 되어 있습니다. 실습실을 학과에서 정해진 개방 시간 이외에 개방하는 것은 학회 자율이기 때문에 저녁 7시 30분에 연습을 시작해 새벽 12시 30분까지 문제를 풀고 에디토리얼까지 보고 집에 갈 수 있는 나름 좋은 환경이었습니다. 다만 실습실에 수업이 있는 날에는 PC방에서 연습을 해야 했는데, 가격도 가격이었지만 시끄러운 환경에서 머리 쓰는 건 나름 고역이었습니다. 뭐 어쩔 수 없었지요.

플랫폼 정하기

연습은 처음엔 Codeforces Gym에서 Virtual contest에 참가하는 방식으로 하다가 언젠가부터 BOJ 그룹의 연습 기능을 이용하게 되었습니다.

Codeforces Gym

Codeforces Gym은 Ghost라는 기능을 제공합니다. 실제 대회의 제출 기록을 스코어보드에 반영한 것인데, 실제로 해당 대회에 참가했다면 순위가 어땠는지를 가늠할 수 있다는 것이 장점인 것 같습니다. 다만 팀 연습 초기에는 제가 셋을 고를 때 너무 쉬운 셋이나 너무 어려운 셋만 골라서 별로 의미가 없었고, 그래서 오히려 스코어보드를 보고 스트레스를 받지 않기 위해 + 쉬운 문제를 빨리 찾아내는 훈련을 하기 위해 BOJ로 옮겼습니다.

BOJ 그룹 연습. 당연히 연습 중에 solved.ac는 껐습니다.

BOJ 연습 기능은 정말 간단하기 때문에 딱히 설명할 건 없는 듯 합니다. 연습 시간을 설정하고 문제를 미리 등록해 두면 됩니다. 물론 스코어보드는 그룹 내부 인원이 해당 시간에 연습에 참여한 것밖에 안 나옵니다. 쉬운 문제를 못 찾겠다면 대회 진행 1~2시간 후에 대회 공식 사이트에서 최종 스코어보드를 띄워놓는 식으로 연습했습니다. 좋은 방법은 아니었던 것 같습니다.

셋 고르기

역시 저는 ICPC 리저널에 대한 지식이 전무했기 때문에 처음에는 말 그대로 아무거나 골라 풀었습니다. 첫 두 팀 연습은 ICPC 리저널 셋이 아니었습니다. 첫 번째는 사설 대회였고 두 번째는 KAIST RUN 대회였던 것으로 기억합니다.

뭔가 제가 고른 셋이 전부 엄청 쉽거나 아니면 엄청 어렵다 보니까 이대로는 안 되겠다 싶어서 인터넷에서 여러 글을 찾아봤습니다. 이후로는 koosaga님의 내가 문제풀이를 연습하는 방법에서 ICPC-style 부분을 많이 참고했고, 유럽 리저널 특히 NWERC 위주로 골라 풀었습니다. Subregional은 너무 쉬웠고, regional 위주로 골라 풀었던 게 가장 적절한 난이도였던 것 같습니다. BOJ 슬랙에서 추천받은 셋들도 풀었습니다.

그렇게 대회까지 총 13셋 정도를 풀었습니다. 개인적으로는 봄부터 연습을 시작했더라면 어땠을까 하는 후회도 없지 않습니다.

전략 세우기

혼자 나가는 대회가 아니다 보니 연습을 거듭할수록 누가 어떤 문제를 언제 풀지 스케쥴링하는 것도 상당히 중요하다는 걸 느꼈습니다. ‘분명히 이건 우리가 풀 수 있는 문제였는데 왜 못 풀었지?’ 같은 현상이 연습 중반까지 자주 일어났습니다. 대표적으로

  • 풀이는 맞는 거 같은데 자꾸 틀렸던 경우
  • 완벽한 풀이를 생각했는데, 다른 팀원이 디버깅을 하느라 시간이 다 가서 코드로 옮기는 것조차 하지 못했던 경우

가 있었습니다.

맞왜틀

첫 번째 경우에는 단순한 실수일 가능성이 크기 때문에, 보통 온사이트 대회에서는 코드 인쇄를 신청하고 다른 팀원이 다른 문제를 푸는 게 일반적입니다. 하지만 저는 그런 걸 몰랐고 더군다나 PC방에서는 인쇄가 안 되었기 때문에… PC방 모니터가 크다는 점을 이용해, 왼쪽에서는 다른 팀원이 다른 문제를 풀었고 오른쪽에서는 제 코드를 띄워 놓고 눈으로 디버깅했습니다. 온사이트에서 인쇄가 가능하다는 걸 빨리 알았으면 좋았을 것 같습니다.

두 번째 경우는 스케쥴링의 문제였습니다. 예를 들면 ‘나 E, F, H 풀이 생각났어!’인데 누군가 J를 계속 디버깅을 하는 케이스인 건데, J 때문에 E, F, H에 병목현상이 생겼습니다. 따라서 틀린 솔루션을 디버깅하는 것보다 확실한 솔루션을 짜는 쪽으로 우선순위를 뒀습니다. 그리고 컴퓨터는 한 명만 쓸 수 있기 때문에 최대한 컴퓨터 자리를 공석으로 두지 않도록 했습니다. 이렇게 전략을 짜니 ‘풀 수 있었는데 못 푼 문제’가 많이 줄었습니다.

실패로부터 배우기

마지막으로, 대회가 끝나면 에디토리얼을 꼭 읽었습니다. 우리가 알고 있는 테크닉이었는지, 알고 있었다면 어떤 걸 잘못해서 틀렸는지 분석했고, 모르고 있었다면 이런 테크닉도 있구나 하고 새로운 기술을 알아갔습니다. 모르던 테크닉이나 실수가 많았던 테크닉은 팀노트에 작성했습니다. 정작 대회에서는 팀노트가 필요없었던 것 같습니다만…

연습이 끝나고 풀지 못한 대회 문제들을 풀어보는 걸 업솔빙upsolving이라고 하는데, 에디토리얼을 다 읽고 어디서 틀렸는지 토론하다 보면 새벽 1시가 훨씬 넘었고, 낮에 다시 학교에 와야 했기 때문에 안타깝게도 무리였습니다. 여건이 된다면 이후 연습에서는 업솔빙까지 꼭 해보고 싶었습니다.

예선

예선은 가족같은 분위기의 학교에서 진행했습니다. 무려 학회 실습실. 항상 오던 곳이라 편안하게 칠 수 있을 줄 알았으나 서버 상태가 메롱이어서 편안하게 못쳤습니다. 여하튼.

예선 스코어보드

예선에서는 6문제를 빠르게 풀었습니다.

I. Registration (3분, shiftpsh): 2013년부터 꾸준히 나와 오고 있는 문제입니다. 아이디와 비밀번호를 출력하면 됩니다. 대회 시작 직후에 여기저기서 ‘야 등록 어딨어’ 같은 소리가 들렸던 거 같은데 제출 서버가 맛이 가서 의미가 없었습니다. 다들 등록 제출하느라 이런 거겠지 하고 생각했으나…

B. Balanced String (14분, semteo04): \(2^{\left\lfloor\frac{n+1}{2}\right\rfloor}\)를 계산하는 쉬운 문제였습니다. 쉬운 문제였는데 서버가 맛이 가서 실제로 푼 시각보다 5분쯤 늦게 제출하게 되었습니다.

H. Four Squares (24분, shiftpsh): 라그랑주의 네 제곱수 정리를 풀어본 적이 있어서 금방 짰습니다.

C. Byte Coin (32분, lvalue): 쉬운 그리디여서 금방 짰습니다. 역시 채점 서버 때문에 제출이 몇 분 늦어졌습니다.

L. Two Machines (73분, semteo04): 냅색 DP였습니다. 냅색이라는 건 알았는데 제가 풀이가 갑자기 생각이 안 나서 저는 못 짜겠다고 선언했습니다.

D. Canal (117분, shiftpsh): 제가 고민중이었는데, semteo04가 이분 탐색이라고 하길래 multiset을 믿고 짰습니다. 이 문제는 대회 서버 때문에 대회가 끝나고 나서도 한두시간 동안 채점 결과를 받아보지 못했는데, multiset이 터졌다는 다른 팀의 증언을 듣고 상심하고 여의도 불꽃놀이나 보면서 심신을 안정시키기로 했습니다.

서강대에서 서강대교까지는 그렇게 멀지 않기 때문에 학교에서 아무 생각 없이 서강대교까지 걸어가서 불꽃을 혼자 구경했습니다. 서강대교에 도착하기 직전에 채점 결과가 공개되었는데, 이 때 D가 맞았다는 걸 알게 되어 안도했습니다. 프리즈 전에는 9등이었다고 합니다.

이미지
프리즈 전 스코어보드

Convex hull trick이라는 걸 알고도 못 푼 J가 너무 아쉬웠는데, 팀노트 코드를 베끼려고 보니 팀노트에 적혀 있던 코드가 그냥 특공대 솔루션이었습니다. 이후 본선에는 보완해 들고 갔는데 본선에는 CHT 안 나오더라고요. 너무하네

A가 LR flow인 걸 몰랐던 것도 아쉬웠습니다. 근데 어차피 서버 나가서 코드를 더 짰어도 문제를 더 맞았을 확률은 희박했을 거라고 생각합니다.

빨리감기해서…

본선 전날

본선은 온사이트 대회고, 온사이트 대회에 가면 인터넷에서나 볼 수 있었던 많은 분들을 뵐 수 있기 때문에 전날에는 수다 떠느라 안타깝게도 따로 연습은 못 했습니다.

한양대학교의 Twitter HLD 팀, POSTECH의 JonMatTaeng 팀과 함께 대회 전날 저녁식사를 했습니다. 레스토랑 이름이 기억이 안 나는데 꽤 맛있었습니다. 서강대 앞에도 점포 내줘요.

연세대/이화여대 상권에 뭔가 다 몰려 있어서 서강대생들은 뭘 먹거나 뭘 하려면 신촌 쪽으로 내려가야 하는데, 여기도 건대 상권에 거의 다 몰려 있어서 아마도 세종대생들도 건대 쪽으로 내려와야 하는 게 아닐까 하는 생각을 했습니다. 제 생각이 맞다면 서강대와 세종대가 의외로 이런 비슷한 점이 있는 거 같습니다. 서강대가 학교 규모는 훨씬 작지만…

다음날 대회가 아침에 있어서, 근처 호텔에서 묵었습니다. 가고 싶은 공연이 있었지만 대회 일정 때문에 신청을 못 했는데, 알고보니 묵던 호텔 바로 옆 건물에서 하더랍니다. 나한테 왜 그래

본선

일단 일어나서 초콜릿 도핑을 많이 했습니다. 빼빼로데이 시즌이길래 페레로 로쉐 2+2 행사를 하고 있었는데 사재기해 둘걸 그랬네요…

팀원 중 한 명은 본선대회일에 쳐야 하는 시험 때문에 숙소에 안 오고 학교에서 공부를 하다가 늦잠을 잤습니다. 다행히도 택시아저씨께서 존경스러운 속도로 운송(?)해 주셔서 실격은 면했습니다.

본선 스코어보드

본선에서는 7문제를 풀었습니다. 개인적인 목표가 7문제였는데 달성해서 상당히 기뻤습니다. 추가로 C와 J를 처음으로 풀었습니다.

J. Triangulation (11분, shiftpsh, First to solve): A가 상당히 쉬운 문제였어서 lvalue가 바로 솔루션을 생각해내 구현을 시작했는데, 제가 J를 보다가 그림 하나를 그려보고…

이미지
J번 풀이 (재연)

…이게 다른 어떤 문제보다 구현이 훨씬 더 쉬울 거 같아서 인터셉트해 제출했습니다. 아이디어를 빨리 생각해내서 운좋게 퍼스트 솔브를 했습니다. 서버 이슈가 없어서 다행이라고 생각했습니다.

이미지
순간 1등

J를 푼 직후 아주 잠시동안 1위였습니다. 스크린샷을 찍어 뒀고 대회가 끝난 뒤 휴대폰으로 컴퓨터 화면을 찍었습니다.

A. Fire on Field (13분, lvalue): 구현하라고 하는 걸 구현하면 되는 쉬운 문제였습니다. 제가 J를 짜려고 인터셉트했을 때 A 코드도 거의 다 짜여져 있던 상태였으므로 바로 제출해 맞았습니다.

L. What’s Mine is Mine (36분, semteo04): 간단한 유형의 DP라서 semteo04가 금방 풀었습니다.

I. Thread Knots (47분, shiftpsh): 그림만 봐도 이분 탐색의 냄새가 나는 문제였습니다. 바로 뚝딱 짰습니다.

B. Gene Tree (103분, semteo04): Tree DP라는 건 알았는데 제곱이 섞여 있어서 식이 괴랄하게 나왔습니다. 제가 식을 열심히 전개하면서 ‘이렇게 분해해서 생각하면 되지 않을까?’ 같은 식의 말을 했더니 semteo04가 뭔가 생각난 듯 열심히 구현했고, 제출해서 맞았습니다.

H. Strike Zone (164분 +2, semteo04): Kadane’s와 세그먼트 트리를 잘 섞으면 되지 않을까 싶어서 일단 제가 짜서 두 번 제출했는데 틀렸습니다. 알고 보니 KOI 2014 중등부의 금광 문제와 똑같은 문제였습니다. lvalue와 저는 정보올림피아드 준비/출전 경험이 없어서 몰랐지만 경험이 있던 semteo04가 제 코드를 버리고 새로 짜 순식간에 맞췄습니다.

C. Islands (204분 +6, lvalue, First to solve): 남은 문제 중에 풀만한 문제가 없어서 lvalue가 잡았는데, 솔직히 왜 맞았는지 아직도 아는 사람이 없습니다. 풀이가 맞는 게 맞는지 아니면 데이터가 약한 건지…

K번 Washer는 뭔가 3차원을 다루는 거 같아서 제가 3차원 벡터 연산하는 코드를 짜고 있었는데, 대회 15분 전에 ‘평면으로 잘라서 \(\binom{100}{3}\times 2^3\) 브루트포싱하면 되지 않을까?’라는 생각이 들어서 그 방향으로 구현했으나 WA를 계속 받았습니다. BOJ에 데이터가 올라온 후 제가 같은 방법으로 다시 구현해서 제출했더니 AC를 받아서 너무 안타까웠습니다. 아마 외적을 잘못 구현했거나 출력 포맷을 잘못 지켰던 것 같습니다…

최종 순위는 팀 랭킹 15위, 학교 랭킹 8위였습니다. 서강대학교가 학교 순위가 1자리수였던 건 2015년(6위) 이후 4년만이라 결과는 만족스러웠습니다. 색깔과 닉네임을 붙여서 팀명을 지으면 수상한다는 전설도 지켰습니다(2017년 BlueJoker, 2015년 PurpleNoon).

개인적으로는 제가 푼 게 많지 않아서 + K를 결국 풀지 못해서 조금 아쉽긴 했습니다. 그래도 제가 어시스트를 많이 했으니 괜찮지 않았을까 싶어요 ..?

스코어보드를 시상식 이후에 공개하는 게 아쉬웠습니다. 꼭 이렇게 해야 했나… 그래도 본선대회 운영은 전반적으로 만족스러웠고(특히 CLion이 있었다는 점에서!), 다과와 저녁은 맛있었습니다. 감사합니다.

Image result for take my money
Take my money

사실 해외 리저널에 참가비가 있다는 건 방콕 대회 때문에 알았는데, 오히려 우리나라가 특이하게 참가비가 없었던 것이었습니다. 내년부터는 참가비가 생긴다는데, 참가비는 얼마든지 괜찮으니 예선 서버 이슈같은 문제만 되풀이되지 않았으면 좋겠습니다.

당분간 휴학할 예정이라 다음에는 2022년 혹은 2023년 리저널에 참가하게 되지 않을까 싶습니다. 팀명처럼 진짜 레드 만들어 와서 월드 파이널에 꼭 한 번 나가보고 싶네요!

수고하셨습니다. 🎈