• 1차 예선 풀이

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보다 좋은 라이브러리라고 생각합니다.

• 2차 예선 풀이

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;
}