SCPC 2022 본선 풀이

 

 

 

SCPC 2022 2차 대회가 9월 3일 오후 1시부터 4시간동안 진행되었다.

SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다.

이 게시글에서는 해당 문제의 풀이를 다룬다.

불일치도

요약

$0$이상 $1$ 이하의 실수 $N$개가 주어집니다. 이 중 $L$이상 $R$이하인 것의 개수를 $F(L, R)$이라고 합시다. 이 때, 모든 $0 \le L \le R \le 1$에 대해, $\left\lvert \frac{F(L, R)}{N} - (R-L)\right\rvert \le D$를 만족하는 최소의 실수 $D$를 구하세요.

풀이

$x$ 이하인 실수의 개수를 $f(x)$라고 하면, 식은 충분히 작은 $\varepsilon$에 대해 $\left\lvert\frac{f(R) - F(L-\varepsilon)}{N} - (R - L)\right\rvert$ $= \left\lvert\left(\frac{f(R)}{N} - R\right) - \left(\frac{f(L-\epsilon)}{N} - \left(L - \epsilon\right)\right) + \epsilon\right\rvert$이 가질 수 있는 값의 상한을 구하는 문제가 됩니다. 여기서 $\epsilon$은 충분히 작으니까 무시할 수 있기 때문에, $\frac{f(x)}{N} - x$이 가지는 값의 상한과 하한의 차이를 구하는 문제가 됩니다.

$N$개의 수를 정렬해서 $A_1, \cdots, A_{N}$이라고 합시다(편의상 $A_0 = 0, A_1 =1 + \varepsilon$이라고 가정합니다). $A_i \le x < A_{i+1}$인 $x$에 대해 $\frac{f(x)}{N} - x$는 $\frac{i}{N} - A_i$부터 $\frac{i}{N} - A_{i+1}$ 미만까지의 값을 가집니다.

즉, 이 값들의 최솟값과 최댓값을 계산해서 그 차이를 출력해주면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
 
double solve(vector<double> V) {
    int N = V.size();
    sort(V.begin(), V.end());
    V.insert(V.begin(), 0.0), V.push_back(1.0);
 
    double mn = 1, mx = -1;
    for (int i = 0; i <= N; i++) {
        mx = max(mx, (double)i / N - V[i]);
        mn = min(mn, (double)i / N - V[i + 1]);
    }
    return mx - mn;
}
 
int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    for (int t = 1; t <= T; t++) {
        int N; cin >> N;
        vector<double> V(N);
        for (auto &v : V) cin >> v;
        cout << "Case #" << t << endl;
        cout << fixed << setprecision(12) << solve(V) << endl;
    }
}

돌무더기 게임

요약

양의 정수 $N$ 개가 일렬로 있고, $A$와 $B$가 게임을 합니다. 정수가 모두 없어질 때까지 다음 행동을 반복합니다.

• $A$가 현재 있는 정수 중 하나를 고릅니다.
• $B$는 $A$가 고른 정수의 왼쪽에 있는 정수를 모두 없애거나, 오른쪽에 있는 정수를 모두 없앱니다.

$A$는 $A$가 가져간 정수의 합을 최대화하고 싶고, $B$는 $A$가 가져간 정수의 합을 최소화 하고 싶습니다. 두 명이 최선의 선택을 할 때, $A$가 고른 정수의 합은 무엇일까요?

풀이

동적 계획법 배열 $D_{i,\ j}$를 게임을 $A_i, \cdots, A_j$에서 진행했을 때 답이라고 합시다. $A$가 $k$번째 수를 가져가면, $B$는 왼쪽과 오른쪽 중 이후 게임에서 고른 정수의 합이 작은 쪽을 고를 것입니다.

$D_{i,\ j} = \left( \max_{i \le k \le j} \min(D_{i,\ k-1 }; D_{k+1,\ j}) + A_k \right)$ 이고, 이를 직접 계산하면 $\mathcal{O}(N^3)$이 됩니다.

이제 다음과 같은 관찰을 합시다.

• $D_{i,\ j} \le D_{i,\ j+1}; D_{i,\ j} \le D_{i-1,\ j}$
  • 가져갈 수 있는 정수가 더 늘어났으므로, $A$가 가져간 정수의 합은 증가합니다.
• $k \le K_{i,\ j}$에 대해서는 $D_{i,\ k-1} < D_{k+1,\ j}$이고, $k > K_{i,\ j}$에 대해서는 $D_{i,\ k-1} \ge D_{k+1,\ j}$인 $K_{i,\ j}$가 존재합니다.
  • $D_{i, k-1}$은 $k$가 증가함에 따라 단조증가하고, $D_{k+1, j}$는 $k$가 증가함에 따라 단조감소하기 때문입니다.
• $K_{i-1,\ j} \le K_{i,\ j} \le K_{i,\ j+1}$
  • $k > K_{i,\ j}$에 대해 $D_{i-1,\ k-1} \ge D_{i,\ k-1} \ge D_{k+1,\ j}$이므로, $K_{i-1,\ j} \le K_{i,\ j}$입니다.
  • $k \le K_{i, j}$에 대해 $D_{i,\ k-1} < D_{k+1,\ j} < D_{k+1,\ j+1}$이므로, $K_{i,\ j} \le K_{i,\ j+1}$입니다.

이제 식을 $K_{i,\ j}$를 기준으로 다시 쓸 수 있습니다.

• $K_{i,\ j}$는 $K_{i-1,\ j}$ 이상 $K_{i,\ j-1}$ 이하에서 차례대로 탐색해서 찾습니다.
• $B$가 왼쪽을 남기는 경우, $L_{i, j} = \max_{i \le k \le j} (D_{i,\ k-1 }+ A_k) = \max(L_{i,\ j-1}; D_{i,\ j-1} + A_j)$입니다.
• $B$가 오른쪽을 남기는 경우, $R_{i, j} = \max_{i \le k \le j} (A_k + D_{k+1,\ j}) = \max( R_{i+1, \ j}, A_i + D_{i+1, \ j } )$입니다.
• $D_{i, \ j} =\max(L_{i,\ K_{i, \ j}}, R_{K_{i, \ j} + 1,\ j })$이고 $K_{i, j}$를 기준으로 왼쪽 혹은 오른쪽을 가져갑니다.

$K_{i,\ j}$를 탐색하는데 걸리는 시간은 $K_{i,\ j-1} - K_{i-1,\ j}$에 비례합니다. 이를 모든 $(i, j)$에 대해 더하면 $\mathcal{O}(N^2)$이됩니다($i-j$가 같은 것끼리 묶으면 항이 상쇄되어서 $\mathcal{O}(N)$입니다.)

코드

#include<bits/stdc++.h>
using namespace std;
 
long long solve(vector<long long> A) {
    int N = A.size();
    vector<vector<long long>> D(N, vector<long long>(N)), L = D, R = D;
    vector<vector<int>> K(N, vector<int>(N));
 
    for (int i = 0; i < N; i++) D[i][i] = L[i][i] = R[i][i] = A[i], K[i][i] = i;
    for (int d = 1; d < N; d++) for (int i = 0; i < N - d; i++) {
        int j = i + d, k = max(i, i == 0 ? 0 : K[i][j - 1]);
        int maxK = min(j - 1, j == N - 1 ? N - 1 : K[i + 1][j]);
        while (k < maxK && D[i][k] <= D[k + 2][j]) ++k;
 
        K[i][j] = k;
        L[i][j] = max(L[i][j - 1], D[i][j - 1] + A[j]);
        R[i][j] = max(R[i + 1][j], A[i] + D[i + 1][j]);
        D[i][j] = max(L[i][k], R[k + 1][j]);
    }
    return D[0][N - 1];
}
 
int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        int N; cin >> N;
        vector<long long> A(N);
        for (auto& a: A) cin >> a;
        long long ans = solve(A);
        cout << "Case #" << tc << '\n' << ans << endl;
    }
}

K 등분 2

요약

$K$등분 문제는 길이 $N$의 배열과 $K$가 주어졌을 때, 합이 같은 $K$개의 (비어있지 않은 연속된) 구간으로 나누는 경우의 수를 구하는 문제입니다. $K$등분 문제의 답이 정확히 $X$가 되는 데이터를 만드세요. $(X \le 10^{18}; 1 \le K \le N \le 180)$

풀이

$K$등분 문제의 풀이를 생각 해봅시다. 전체의 합을 $S$라고 하면 $i$번째 구간까지의 누적합은 $\frac{iS}{K}$가 되어야 합니다. 결국 누적합을 구한 이후 $\left(\frac{S}{K}, \frac{2S}{K}, \cdots, \frac{(K-1)S}{K}\right)$가 부분수열로 등장하는 경우의 수를 세는 문제입니다.

편의상 $K\ne 0$인 경우만 생각하고, $K=S$라고 생각합시다. 이러면 $(1, 2, \cdots, K-1)$가 부분수열로 등장하는 경우의 수를 세는 문제가 됩니다. $i$번째 수인 $A_i$로 끝나는 부분수열의 경우의 수를 $D_i$라고 하면 $D_i = \sum_{j < i;\ A_j = A_i+1} D_j$가 됩니다. 이후 $A_i = K-1$인 $i$에 대해 $D_i$를 모두 더하면 답이 됩니다.

답이 $x$인 수열이 있고, 이를 $K$등분 해야한다고 생각합시다. 이제 $K$를 $1$ 증가시키고 $K$를 삽입해 봅시다. 가장 처음으로 등장하는 $K-1$뒤에 $K$를 삽입하면, 두 수의 $D_i$ 값은 같을 것입니다. 또한 가장 뒤에 $K$를 삽입하면, 이에 해당하는 $D_i$값은 $x$일 것입니다. $A_i = K-1, D_i = 1$인 $i$가 있고, 전체 답이 $x$인 수열을 $ax+b$로 바꾸는 방법은 다음과 같습니다.

• 처음으로 등장하는 $K-1$ 뒤에 $K$를 $b$개 삽입합니다.
• 마지막에 $K$를 $a$개 삽입합니다.

여기서 주목할 점은 이를 반복적으로 사용하기 위해서는 항상 $b \ge 1$이어야 하고, 수가 $a+b$개가 늘어난다는 것입니다. $a=2, b=1; a=2, b=2$를 사용하면 답을 $2$배씩 늘릴 때 마다 수가 최대 $4$개 늘어나므로, $240$개 정도로 문제를 해결할 수 있습니다.

더 효율적인 방법은 $a=4, b=1; a=4, b=2$를 함께 사용해서 $4x+1$ 혹은 $4x+2$꼴의 수의 경우에는 $a=4$를 사용하는 것입니다. 이제 $K \ge 1$에 대해 다음 사실을 증명합시다.

• 답으로 $2^K$ 이하의 수를 만들 때, 홀수는 $3K-2$, 짝수는 $3K-1$개 이하의 수를 사용하는 것이 가능합니다.
  • $K = 1, 2, 3$일 때: $x$를 만들기 위해 $1$을 $x$개 쓰면 됩니다.
  • $K > 3$일 때, $x \le 2^K$라고 합시다.
    • $x = 4k+1$: $k$를 만드는 데에 $3(K-2)-1$개 이하의 수를 사용합니다. $3(K-2)-1 + (4+1) = 3K-2$입니다.
    • $x=4k+2$: $k$를 만드는 데에 $3(K-2)-1$개 이하의 수를 사용합니다. $3(K-2)-1+(4+1) = 3K-1$입니다.
    • $x=4k+3 = 2(2k+1)+1$: $2k+1$을 만드는 데에 $3(K-1)-2$개 이하의 수를 사용합니다. $3(K-1) -2 + (2 + 1) = 3K-2$입니다.
    • $x = 4k+3 = 2(2k+1)+2$: $2k+1$을 만드는 데에 $3(K-1)-2$개 이하의 수를 사용합니다. $3(K-1)-2 + (2+2) = 3K-1$입니다.

이렇기에 우리는 $10^{18} \le 2^{60}$이하의 수를 $179$개 이하의 누적합을 써서 만들 수 있고, 원래 문제인 변화값은 $180$개 이하로 사용해서 만드는 것이 가능합니다.

이 방법을 발전 시켜서 $170$개 이하만 사용해서 답을 만드는 것도 가능합니다. 몇 가지 $a$에 대해 시도해 본 결과중 최솟값을 동적 계획법 등으로 관리하면, 더 적은 개수로 답을 만들 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
pair<int, vector<int>> aug(int a, int b, pair<int, vector<int>> X) {
    auto [k, V] = X;
    for(int i=0; i<a; i++) V.insert(next(find(V.begin(), V.end(), k)), k+1);
    for(int i=0; i<b; i++) V.push_back(k+1);
    return {k+1, V};
}
 
pair<int, vector<int>> gen(long long x) {
    if(x == 0) return {1, {0, 0}};
    if(x <= 8) return {1, vector<int>(x, 1)};
    const vector<pair<int, int>> ab = {{1, 4}, {2, 4}, {1, 2}, {2, 2}};
    for(auto [a, b]: ab) if(x%b == a%b) return aug(a, b, gen((x-a)/b));
}
 
pair<int, vector<int>> delta(pair<int, vector<int>> P) {
    auto [k, V] = P;
    vector<int> U = {V[0]};
    for (int i = 1; i < (int)V.size(); i++) U.push_back(V[i] - V[i-1]);
    U.push_back(k+1 - V.back());
    return {k+1, U};
}
 
int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    for (int i = 1; i <= T; i++) {
        cout << "Case #" << i << endl;
        long long v; cin >> v;
        auto [K, A] = delta(gen(v));
        cout << A.size() << ' ' << K << endl;
        for (int i = 0; i < (int)A.size(); i++)
            cout << A[i] << (i + 1 == (int)A.size() ? '\n' : ' ');
        cout << flush;
    }
}
 

아름다운 수열

요약

양의 정수로 이루어진 수열 $A_1, \cdots, A_N$에 대해 이 수열의 아름다움을 $A_{i-1} \le A_i \ge A_{i+1}$을 만족하는 $i$의 개수라고 정의합시다. $(A_0 = A_{N+1} = 0;$ $1 \le i \le N)$. 양의 정수 $N$개가 주어질 때 이를 임의로 재배열해서 만들 수 있는 수열의 아름다움의 최댓값을 구해야 합니다.

풀이

$A_{i-1} \le A_i \ge A_{i+1}$을 만족하는 $i$를 아름다운 위치라고 합시다.

아름답지 않은 위치를 $i_1, i_2, \cdots, i_m$이라고 하고, $i_0 = 0, i_{m+1} = N+1$이라고 합시다. 아름다운 수인 $i_k+1$부터 $i_{k+1}-1$번째 까지 수가 만족해야 하는 조건은 $A_{i_k} \le A_{i_k+1} = A_{i_k+2} = \cdots = A_{i_{k+1}-1} \ge A_{i_{k+1}}$라는 것을 알 수 있습니다.

아름다움을 최대화하기 위해서는 $m$이 가능한 한 작아야 합니다. 아름답지 않은 위치의 개수가 $m$개인 해당하는 수열을 만들기 위해서는

• $N$개의 수 중 $m$개의 수 $V_1, V_2, \cdots, V_m$을 고릅니다.
• 나머지 수의 종류가 $m+1$개 이하입니다.
• 각 수는 $V_1$ 이상의 수, $\max(V_1, V_2)$ 이상의 수, $\max(V_2, V_3)$ 이상의 수, $\cdots$, $\max(V_{m-1}, V_m)$ 이상의 수, $V_{m}$ 이상의 수여야 합니다.

여기서 다음 관찰을 합시다.

• 수의 범위를 최대한 늘리기 위해서는 $V_1, V_2, \cdots, V_m$이 정렬되어있어야 합니다.
  • $V_1, \max(V_1, V_2), \cdots, \max(V_{m-1}, V_m), V_m$중 $V_i$ 이상인 수는 $i+1$개 이상입니다. 이를 정확히 $i+1$개로 만드는 방법은 $V_1 \le V_2 \le \cdots \le V_m$으로 나누는 것입니다.
• 마찬가지로, 나머지 수 역시 정렬되어 있어야 합니다. 나머지 수는 $V_1, V_2, \cdots, V_{m-1}$이상이 1개씩, $V_{m+1}$ 이상이 2개 있어야 합니다.

그래서 우리는 수를 묶어서 작은 것부터 하나씩 추가할 것입니다. 그 후 조건에 맞지 않을 때 즉, $m$을 늘려야 할 때마다 $m$을 하나씩 고를 것입니다. 남은 수의 서로 다른 수의 개수가 가장 작아야 하기 때문에, 제일 적게 남은 수로 $V_m$을 사용합니다. 수가 작은것부터 추가되기 때문에 이후에 추가되는 수는 모두 $V_m$이상이고, 기타 수의 조건에 영향을 주지 않습니다. 구현은 우선 순위 큐 등을 사용해서 $\mathcal{O}(N \log N)$ 시간에 가능합니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
int solve(vector<int> V) {
    sort(V.begin(), V.end());
    if(V.front() == V.back()) return V.size();
 
    priority_queue<int, vector<int>, greater<int>> Q;
    int cur = 0;
    auto push = [&](int v) {
        if (cur < (int)Q.size()) {
            int x = Q.top(); Q.pop();
            if(x > 1) Q.push(x-1);
            ++cur;
        }
        Q.push(v);
    };
 
    int p = V[0], c = 1;
    for(int i=1; i<(int)V.size(); i++) {
        if(p != V[i]) push(c), p = V[i], c = 1;
        else ++c;
    }
    push(c);
    return V.size() - cur;
}
 
 
int main() {
    int T; cin >> T;
    for(int t=1; t<=T; t++) {
        int N; cin >> N;
        vector<int> V(N);
        for(int&v: V) cin >> v;
        cout << "Case #" << t << '\n' << solve(V) << endl;
    }
}

최적 함수

요약

점 $(x_i, y_i)$가 $N$개 주어집니다. 2차함수 $y=f(x)$에 대해, $\left(f(x_i)-y_i\right)^2$의 최댓값을 $f$의 오차라고 합시다. 오차가 최소가 되는 $f$를 찾아서, 해당 오차를 출력하세요. (좌표 범위: $10^6$, 출력의 절대 오차 및 상대 오차 허용값: $2 \times 10^{-6}$)

풀이

오차가 $\varepsilon$ 이하인 함수 $f(x)$와 $g(x)$에 대해, $\left(\frac{f+g}{2}\right)(x)$의 오차도 $\varepsilon$이하입니다. $f$의 등고선이 볼록이기 때문에 $f$에 따른 오차는 Unimodal하고 삼분탐색을 사용할 수 있습니다. 주어진 절대오차 및 상대 오차 허용값을 $\varepsilon$, 좌표 범위를 $L$이라고 하면 $2$차항과 $1$차항에 대한 삼분탐색을 차례로 사용해서, $\mathcal{O}(N \log^2 \left(\frac{L}{\varepsilon}\right))$ 정도의 시간에 문제를 해결할 수 있습니다($2$차항과 $1$차항이 주어지면, 상수항은 $2$차항과 $1$차항만 계산한 값과 $y$값 차이의 최솟값과 최댓값의 평균으로 설정하면 됩니다.)

이제 (계산시의) 오차에 대해 생각해 봅시다. Machine epislon을 $\epsilon$이라고 합시다. 함수를 $f(x) = ax^2+bx+c$와 같이 잡으면, 해당하는 $c$의 값이 $\mathcal{O}(L^2)$정도까지 발산할 수 있기 때문에, $\mathcal{O}(L^2\epsilon) << \varepsilon$여야 하고, $\epsilon << 10^{-18}$이어야 하기 때문에, long double 자료형을 사용해야 하며, 이를 사용해도 실수 오차 문제가 발생할 수 있습니다. 그래서 다음과 같은 형태의 함수를 생각해봅시다.

• 가능한 $x$의 범위가 $[l, r]$일 때, $f(x) = a(x-l)(x-r) + b(x-l) + c$꼴입니다.

이제 최적인 $f$에 대해 각 항이 $\mathcal{O}(L)$로 bound됨을 보입시다.

• 오차의 제곱근은 $L$ 이하입니다
  • $f(x) = 0$의 경우 오차의 제곱근은 좌표 범위인 $L$ 이하가 됩니다.
• $\lvert c \rvert$는 $2L$이하입니다.
  • $f(l) = c$이므로, $\lvert c \rvert = \lvert f(l) \rvert \le L + \lvert y_i \rvert \le 2L$입니다.
• $\lvert b(x-l) \rvert $은 모든 $x$에 대해 $4L$이하입니다.
  • $f(r) = b(r-l) + c$이므로, $\lvert b(x-l) \rvert \le \lvert b(r-l) \rvert \le L + \lvert y-c \rvert \le L + \lvert y \rvert + \lvert c \rvert \le 4L$입니다.
• $\lvert a(x-l)(x-r) \rvert$는 모든 $x$에 대해 $8L$이하입니다.
  • $\lvert a(x-l)(x-r) \rvert \le \lvert f(x) - b(x-l) + c \rvert \le y + \lvert f(x) \rvert + \lvert b(x-l) \rvert + \lvert c \rvert \le 8L$ 입니다.

그러므로 해당 $a, b, c$를 사용해서 삼분탐색을 하면, $\mathcal{O}(L \epsilon) << \varepsilon$이면 충분하고, $\epsilon << 10^{-12}$ 정도이므로 double 자료형만 사용해도 문제를 해결할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
double solve(vector<pair<int, int>> V) {
    const double LIM = 1e7;
    const int iter = 150;
    const double INF = std::numeric_limits<double>::infinity();
 
    sort(V.begin(), V.end());
    int L = V.front().first, R = V.back().first;
 
    auto calcC = [&](double a, double b) {
        double minv = +INF, maxv = -INF;
        for (auto &[x, y] : V) {
            double c = y - (a * (x - L) * (x - R)) + b * (x - L);
            minv = min(minv, c);
            maxv = max(maxv, c);
        }
        double E = (maxv - minv) / 2;
        return E * E;
    };
 
    auto calcB = [&](double a) {
        double lo = -LIM, hi = +LIM;
        for (int i = 0; i < iter; i++) {
            double b1 = (lo + lo + hi) / 3, b2 = (lo + hi + hi) / 3;
            double v1 = calcC(a, b1), v2 = calcC(a, b2);
            if (v1 < v2) hi = b2;
            else lo = b1;
        }
        return calcC(a, (lo + hi) / 2);
    };
 
    auto calcA = [&]() {
        double lo = -LIM, hi = +LIM;
        for (int i = 0; i < iter; i++) {
            double a1 = (lo + lo + hi) / 3, a2 = (lo + hi + hi) / 3;
            double v1 = calcB(a1), v2 = calcB(a2);
            if (v1 < v2) hi = a2;
            else lo = a1;
        }
        return calcB((lo + hi) / 2);
    };
 
    return calcA();
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int N; cin >> N;
        vector<pair<int, int>> V(N);
        for (auto &[x, y] : V) cin >> x >> y;
        cout << "Case #" << t << '\n';
        cout << fixed << setprecision(20) << solve(V) << endl;
    }
}