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}$ 미만까지의 값을 가집니다.

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

코드

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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;
    }
}
cs

돌무더기 게임

요약

양의 정수 $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)$입니다.)

코드

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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;
    }
}
cs

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$에 대해 시도해 본 결과중 최솟값을 동적 계획법 등으로 관리하면, 더 적은 개수로 답을 만들 수 있습니다.

코드

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
 
pair<intvector<int>> aug(int a, int b, pair<intvector<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<intvector<int>> gen(long long x) {
    if(x == 0return {1, {00}};
    if(x <= 8return {1vector<int>(x, 1)};
    const vector<pair<intint>> ab = {{14}, {24}, {12}, {22}};
    for(auto [a, b]: ab) if(x%b == a%b) return aug(a, b, gen((x-a)/b));
}
 
pair<intvector<int>> delta(pair<intvector<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;
    }
}
 
cs

아름다운 수열

요약

양의 정수로 이루어진 수열 $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)$ 시간에 가능합니다.

코드

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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<intvector<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;
    }
}
cs

최적 함수

요약

점 $(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 자료형만 사용해도 문제를 해결할 수 있습니다.

코드

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
 
double solve(vector<pair<intint>> 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<intint>> V(N);
        for (auto &[x, y] : V) cin >> x >> y;
        cout << "Case #" << t << '\n';
        cout << fixed << setprecision(20<< solve(V) << endl;
    }
}
cs

'프로그래밍 > 알고리즘' 카테고리의 다른 글

SCPC 2022 2차 풀이  (0) 2022.08.06
SCPC 2021 2차 풀이  (0) 2021.08.07
SCPC 2021 1차 풀이  (0) 2021.07.17
Merry Problem Solving 4일차  (0) 2018.12.26
Merry Problem Solving 3일차  (0) 2018.12.24

SCPC 2022 2차 대회가 8월 6일 오전 9시부터 12시간동안 진행되었다.

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

 

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


1. 수열 연산

문제를 요약하면, 주어진 수열 $A$의 모든 수를 주어진 수 $K$ 이상으로 만들기 위해서 최소 횟수의 연산을 사용하고, 이 때 가능한 총 비용의 최솟값을 구하는 문제다. 한 연산은 연속된 구간의 모든 수를 $1$ 증가시키고, 이 연산의 비용은 구간의 길이이다.

 

더보기

연산을 수열 전체에 사용한다고 생각하면 사용해야하는 연산의 횟수는 $\max(K - \min A, 0)$이다. 이 이하로 사용해서는 최솟값을 $K$ 이상으로 만들 수 없다. 이제 가능한 총 비용의 최솟값을 구하자.

이전 관찰로, 우리는 연산을 수열의 최솟값에 해당하는 인덱스에만 증가시켜주면 된다는 것을 알 수 있다(최솟값이 늘어나면, 필요한 횟수가 줄어든다.) 그렇기에 최솟값에 해당하는 모든 인덱스를 포함하는 가장 짧은 구간에 연산을 사용하면 된다는 것을 알 수 있다. 이를 그대로 구현하면 $O((\max A) \times N)$ 정도의 시간이 든다.

 

원래 최솟값이었던 수는 항상 연산에 포함되어있다는 사실을 주목하자. 각 인덱스가 증가되는 횟수는 이 값을 최대로 해서 바깥으로 갈수록 줄어드는 모양이라는 것을 알 수 있다(연산의 구간이 연속되어있다.) 이를 이용해서 각 인덱스가 증가되는 횟수를, 자기 이전 혹은 이후 인덱스가 증가되는 횟수에 따라 계산해주면 된다. 시간 복잡도는 $O(N)$ 이다.


2. 반 협동 게임

문제를 요약하면, 수열 $A$가 주어지는데 이 수열에 있는 수 중 같은 수 두 개를 잡아서 제거할 수 있다. 이렇게 제거할 때마다, 제거한 두 수의 인덱스 차에 해당하는 점수를 얻는다. 가능한 점수의 최댓값은 무엇인가?

 

더보기

수가 같은 $4$개의 인덱스 $a < b < c < d$가 존재하고, 제거 연산이 $(a, d) \rightarrow (b, c)$순이 아니면, 제거 연산을 $(a, d) \rightarrow (b, c)$순으로 바꾸어 주는 것으로 더 높은 점수를 얻을 수 있다. 이를 통해, 우리는 같은 수에서 제거되는 쌍을 바깥쪽부터 차례로 만드는 것이 가장 이득이라는 것을 알 수 있다.

네 인덱스 $a < b < c < d$에 대해, $(a, c)$와 $(b, d)$는 어느것을 먼저 수행해도 상관 없고, $(a, d)$와 $(b, c)$는 $(a, d)$의 제거 연산을 먼저 수행하는 것이 이득이라는 것을 알 수 있다. 이를 통해, 우리는 정해진 쌍을 제거하는 연산을 두 인덱스 차이 순서대로 실행하면, 가능한 최고의 점수를 얻는다는 것을 알 수 있다.

이를 세그먼트 트리 등을 이용하여 시뮬레이션하면, 시간복잡도는 $O(N \log N)$이다.


3. ABC

문제를 요약하면, 간선에 $A, B, C$중 하나가 써있는 유향그래프가 주어진다. 이 중, 아무 정점에서나 시작해서, 간선을 타고가며 간선에 있는 글자를 만나는 순서대로 붙여서 문자열을 만드는데, $A$ 다음에는 $B$, $B$ 다음에는 $C$, $C$ 다음에는 $A$가 와야한다. 글자는 항상 붙여야하지만, 주어진 $K = 0, 1, 2$ 혹은 $\infty$번만큼 간선에서 글자를 붙이지 않아도 된다.이렇게 만들어지는 문자열의 최대 길이를 구하여라(문자열이 무수히 길어질 수 있다.)

 

더보기

$D[a][k][c]$를 현재 $a$ 정점에 있고, $k$번 스킵할 수 있으며, 다음 간선의 문자가 $c$일때 가능한 최대 길이라고 정의하자.

다음 문자를 스킵하는 경우와 경우하지 않는 경우의 두 가지가 있다.

  • 문자가 일치하는 경우: $a \xrightarrow{c} b$에 대해서 $1+D[b][k][next(c)]$, $next(c): c$의 다음 문자
  • 문자가 일치하지 않는 경우 :$a \xrightarrow{c} b$에 대해서 $D[b][k-1][c]$. $(k > 0)$

현재 위치에서 끝낼수 있으므로, 0과 위 값들의 최댓값을 구하면 된다.

 

이를 동적계획법을 사용하여 해결하면 되는데, 정의가 순환적이라는 문제가 생긴다. 즉 이전 방문한 DP상태를 다음에도 방문할 수 있다는 의미이다. 이를 위해서 DP를 순서대로 돌리는 것이 아니라, memoization을 활용하고, 다음과 같은 방법으로 처리한다.

  • 현재 상태를 방문한 적이 없는 경우, 위 DP식을 이용해 답을 찾는다.
  • 현재 상태에서 정답을 찾은 적이 있을경우, 기존에 저장한 해당 정답을 반환한다.
  • 현재 상태에서 정답을 찾은 적이 없는데 이전에 방문한 적이 있는 경우, 현재 상태에서 다시 정답으로 돌아오는 방법이 있다는 의미이다. 이 경우에는 방문 횟수가 무한할 수 있다.

$k = 0, 1, 2$일 때는 방문 횟수가 무한하면 문자열의 길이가 무한하지만, $k=-1$일 때는 문자열의 길이가 무한하지 않을 수 있다(가령이면, $A, B$가 있는 사이클을 무한히 반복한다.) 이를 처리하는 방법은 다양한 방법이 있는데 하나는 SCC를 구해서 정점을 압축하는 방식이다. 다른 방법은 방문한 사이클이 유효하게 문자를 붙여오면서 한바퀴를 돌았는지를 판단하는 방법이 있다. 뒤의 방법을 조금 더 설명한다.

문자를 붙일 때마다(즉, 1번 경우만) 깊이가 $1$씩 깊어지도록 코드를 작성하면 같은 상태를 다시 방문했을 때 깊이가 깊어졌으면 문자를 붙이는 사이클이 존재하므로 답은 무한하다. 그렇지 않으면, "사이클은 존재하지만, 해당 사이클을 방문하면서 문자를 붙일수 없는 상태"이기 때문에, 답을 현재 상태에서 갱신하지 않는다(즉, 0을 반환한다.)

이와 같이 구현하면 시간복잡도는 $k$가 유한할 때 $O(kM)$이 된다. $k = \infty$ 일 때는 $k$가 가질 수 있는 상태가 $\infty$ 하나로 유일하기 때문에 시간복잡도가 $O(M)$이다.


4. 직사각형

문제를 요약하면, $1$부터 $N^2$까지의 수가 하나씩 써있는 $N \times N$ 격자에서 꽉찬 직사각형의 수를 세는 것이다. 꽉찬 직사각형이란 이 영역 안의 수들을 재배열해서 연속적으로 만들 수 있으면 꽉 찬 직사각형이라고 한다.

 

더보기

어떤 직사각형이 꽉 찬 직사각형인지 판단하는 법을 생각해보자. 우리가 직사각형 내부 칸의 최솟값과 최댓값을 안다면 직사각형 안에는 최솟값부터 최댓값까지 모든 수가 다 존재해야 한다. 즉, 최댓값에서 최솟값을 뺀 값에 $1$을 더한 값이 면적과 같은지 확인하면 된다.

이제 직사각형의 최솟값 $T$를 고정시켜보자. 해당 수만 포함하는 직사각형은 자명하게 꽉 찬 직사각형이다. 이제 다음으로 큰 꽉 찬 직사각형을 구해보자. 이 꽉 찬 직사각형은 상하좌우중 한 방향으로 늘어나야한다. 이 중 "늘어나는 영역의 최솟값과 최댓값"에 대해 살펴보자.

  • 늘어나는 영역의 최솟값이 $T$이하이면 해당 영역을 포함하면 직사각형의 최솟값이 $T$가 아니기 때문에 해당 방향으로 늘어나날 수 없다.
  • 늘어나는 영역의 최댓값중 가장 작은 값 $C$쪽으로는 항상 늘어나야 한다. 다른 방향으로만 늘이게 되면 최댓값은 $C$보다 큰데 $C$를 포함하지 않게 된다.

각 수에 대해 직사각형 영역은 $2N-1$번 늘어나므로, 총 $2N^3-N^2$번 미만 늘어난다. $O(N^3)$에 전처리를 해서 늘어나는 구간에 대한 정보를 $O(1)$에 계산할 수 있으면, 시간복잡도 $O(N^3)$에 문제를 풀 수 있다.


5. 황금카드

문제를 요약하면, 카드가 $N$ 종류가 있고 각 카드가 뽑힐 확률은 $\frac{p_i}{P}$이다. $(P = p_1 + \cdots + p_N)$ 카드를 $k$장 뽑았을 때 뽑힌 카드 종류 개수의 기댓값을 $E_k$라고 하면, $k = 1, \cdots, K$에 대해서 $P^k E_k$를 $998,244,353$으로 나눈 나머지를 구하는 문제이다.

 

더보기

일단, $P^k E_k$를 구하는 식을 써보자. 카드 종류 개수의 기댓값은 기댓값의 선형성을 이용하면 $1$번 카드가 뽑힐 확률 + $2$번 카드가 뽑일 확률 + $\cdots$ + $N$번 카드가 뽑힐 확률로 계산할 수 있다. 여사건인 $i$번 카드가 $k$번 중에 한 번도 뽑히지 않을 확률은 $\left(\frac{P-p_i}{P}\right)^k$이므로 $i$번 카드가 뽑힐 확률은 $1-\left(\frac{P-p_i}{P}\right)^k$이다. $P^k E_k$는 이를 $i = 1, \cdots, N$에 대해 더한 $\sum_{i=1}^N P^k - (P-p_i)^k$와 같이 계산할 수 있다. 이를 직접 계산하면 $O(NK)$가 된다.

 

이제 시간복잡도를 줄여보자. 위 식을 정리하면 $N P^k - \sum_{i=1}^N q_i^k$ $(q_i = P-p_i)$가 된다. $F_k = \sum_{i=1}^N q_i^k$을 모든 $i = 1, \cdots, K$에 대해 빠르게 구해야 한다. 생성함수 $f(x) = \sum_{k=0}^{\infty} F_k x^k$를 생각하자. $f(x) = \sum_{k=0}^{\infty} \left( \left( \sum_{i=1}^N q_i^k \right) x^k \right) = \sum_{i=1}^N \left( \sum_{k=0}^{\infty} \left( (q_i x)^k \right) \right) = \sum_{i=1}^N \frac{1}{1-q_i x}$가 된다.

$\sum_{i=1}^N \frac{1}{1-q_i x}$을 분수형태로 구하는 법은, 좌우 절반으로 나눠서 왼쪽이 $\frac{A(x)}{B(x)}$, 오른쪽이 $\frac{C(x)}{D(x)}$일  때 $\frac{A(x)D(x) + B(x)C(x)}{B(x)D(x)}$로 구하면 되고, 다항식 곱셈을 세 번 사용하면 된다. 이를 구하는 시간복잡도는 $T(N) = 2T(N/2) + O(N \log N)$이고, $T(N) = O(N \log^2 N)$이다.

이제, $\frac{A(x)}{B(x)}$와 같은 식을 실제로 계산해야 하는데, 다항식 나눗셈을 사용하면 이 값을 $K$번째 항까지 $O(K \log K)$에 계산할 수 있다. $f(x)$의 각 항을 구할 수 있으니, 각 $F_k$를 알 수 있다.

시간복잡도는 $O(N \log^2 N + K \log K)$이다.

 


코드

1번

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
 
pair<int, int64_t> solve(int K, vector<int> A)
{
    int N = A.size();
    for (int &a : A)
        a = max(0, K - a);
 
    vector<int> L(N), R(N);
    L[0= A[0];
    for (int i = 1; i < N; i++)
        L[i] = max(L[i - 1], A[i]);
    R[N - 1= A[N - 1];
    for (int i = N - 2; i >= 0; i--)
        R[i] = max(R[i + 1], A[i]);
 
    int64_t ans = 0;
    for (int i = 0; i < N; i++)
        ans += min(L[i], R[i]);
 
    return {*max_element(A.begin(), A.end()), ans};
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        int N, K;
        cin >> N >> K;
        vector<int> A(N);
        for (int &a : A)
            cin >> a;
        auto [f, s] = solve(K, A);
        cout << "Case #" << tc << "\n"
             << f << " " << s << endl;
    }
}
cs

 

2번

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <algorithm>
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;
 
struct Seg
{
    int N;
    vector<int> idx;
    Seg(vector<int> V)
    {
        N = 1;
        while (N < (int)V.size())
            N *= 2;
        idx.resize(2 * N);
        copy(V.begin(), V.end(), idx.begin() + N);
        for (int i = N - 1; i > 0; i--)
            idx[i] = idx[2 * i] + idx[2 * i + 1];
    }
    int get(int a, int b)
    {
        a += N, b += N;
        int ans = 0;
        while (a <= b)
        {
            if (a % 2 == 1)
                ans += idx[a++];
            if (b % 2 == 0)
                ans += idx[b--];
            a /= 2;
            b /= 2;
        }
        return ans;
    }
    void set(int a, int v)
    {
        idx[a += N] = v;
        while ((a = a / 2))
            idx[a] = idx[2 * a] + idx[2 * a + 1];
    }
};
 
int64_t solve(vector<int> A)
{
    int N = A.size();
    vector<int> used(N, 1);
    vector<vector<int>> idx(N);
    for (int i = 0; i < N; i++)
        idx[A[i] - 1].push_back(i);
 
    vector<pair<intint>> P;
    for (auto &V : idx)
    {
        int K = V.size();
        for (int i = 0; i < K / 2; i++)
        {
            P.emplace_back(V[i], V[K - 1 - i]);
            used[V[i]] = used[V[K - 1 - i]] = 0;
        }
    }
    sort(P.begin(), P.end(), [&](pair<intint> a, pair<intint> b)
         { return a.second - a.first < b.second - b.first; });
 
    Seg S = used;
    long ans = 0;
    for (auto [l, r] : P)
    {
        ans += 1 + S.get(l, r);
        S.set(l, 1);
        S.set(r, 1);
    }
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        int N;
        cin >> N;
        vector<int> A(N);
        for (int &a : A)
            cin >> a;
        cout << "Case #" << tc << "\n"
             << solve(A) << endl;
    }
}
cs

3번

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
 
int solve(int N, int K, const vector<vector<pair<intint>>> &G)
{
    bool inf = K == -1;
    if (inf)
        K = 0;
    vector<vector<vector<int>>> ans(N, vector<vector<int>>(1 + K, vector<int>(3-1))), vis = ans;
 
    function<int(intintintint)> dfs = [&](int a, int k, int c, int d)
    {
        if (ans[a][k][c] != -1)
            return ans[a][k][c];
        if (vis[a][k][c] == d)
            return 0;
        if (vis[a][k][c] > 0)
            return -1;
        vis[a][k][c] = d;
        int ret = 0;
        for (auto [v, t] : G[a])
        {
            if (t == c)
            {
                int res = dfs(v, k, c == 2 ? 0 : c + 1, d + 1);
                if (res == -1)
                    return -1;
                ret = max(ret, 1 + res);
            }
            if (k > 0 || inf)
            {
                int res = dfs(v, inf ? k : k - 1, c, d);
                if (res == -1)
                    return -1;
                ret = max(ret, res);
            }
        }
        return ans[a][k][c] = ret;
    };
 
    int ret = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < 3; j++)
        {
            int v = dfs(i, K, j, 1);
            if (v == -1)
                return -1;
            ret = max(ret, v);
        }
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        int N, M, K;
        cin >> N >> M >> K;
        vector<vector<pair<intint>>> G(N);
        for (int i = 0; i < M; i++)
        {
            int a, b;
            char c;
            cin >> a >> b >> c;
            a--;
            b--;
            c -= 'A';
            G[a].emplace_back(b, c);
        }
        cout << "Case #" << tc << "\n"
             << solve(N, K, G) << endl;
    }
}
cs

4번

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int solve(const vector<vector<int>> &A)
{
    int N = A.size();
    vector<vector<vector<int>>> Hx(N, vector<vector<int>>(N, vector<int>(N)));
    auto Vx = Hx, Hn = Hx, Vn = Hx;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = j; k < N; k++)
                if (j == k)
                {
                    Hx[i][j][k] = Hn[i][j][k] = A[i][k];
                    Vx[i][j][k] = Vn[i][j][k] = A[k][i];
                }
                else
                {
                    Hx[i][j][k] = max(Hx[i][j][k - 1], A[i][k]);
                    Hn[i][j][k] = min(Hn[i][j][k - 1], A[i][k]);
                    Vx[i][j][k] = max(Vx[i][j][k - 1], A[k][i]);
                    Vn[i][j][k] = min(Vn[i][j][k - 1], A[k][i]);
                }
 
    int ans = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            int L = j, R = j, U = i, D = i, T = A[i][j], C = A[i][j];
            ++ans;
            while (true)
            {
                int ls = (L == 0 || Vn[L - 1][U][D] < T) ? N * N + 1 : Vx[L - 1][U][D];
                int rs = (R == N - 1 || Vn[R + 1][U][D] < T) ? N * N + 1 : Vx[R + 1][U][D];
                int us = (U == 0 || Hn[U - 1][L][R] < T) ? N * N + 1 : Hx[U - 1][L][R];
                int ds = (D == N - 1 || Hn[D + 1][L][R] < T) ? N * N + 1 : Hx[D + 1][L][R];
                int mn = min({ls, rs, us, ds});
                if (mn == N * N + 1)
                    break;
                C = max(C, mn);
                if (mn == ls)
                    --L;
                else if (mn == rs)
                    ++R;
                else if (mn == us)
                    --U;
                else if (mn == ds)
                    ++D;
                if ((R - L + 1* (D - U + 1== C - T + 1)
                    ++ans;
            }
        }
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        int N;
        cin >> N;
        vector<vector<int>> V(N, vector<int>(N));
        for (auto &y : V)
            for (int &x : y)
                cin >> x;
        cout << "Case #" << tc << "\n"
             << solve(V) << endl;
    }
}
cs

5번

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
 
struct Mint
{
    static const int MOD = 998'244'353;
    static const int prr = 3;
 
    Mint() : _v(0) {}
    Mint(int v) : _v((v % MOD + MOD) % MOD) {}
    int val() const { return _v; }
 
    Mint &operator+=(const Mint &rhs)
    {
        _v += rhs._v;
        if (_v >= MOD)
            _v -= MOD;
        return *this;
    }
    Mint &operator-=(const Mint &rhs)
    {
        _v -= rhs._v;
        if (_v < 0)
            _v += MOD;
        return *this;
    }
    Mint &operator*=(const Mint &rhs)
    {
        _v = (long long)_v * rhs._v % MOD;
        return *this;
    }
    Mint &operator/=(const Mint &rhs) { return *this = *this * rhs.inv(); }
 
    Mint operator+() const { return *this; }
    Mint operator-() const { return Mint() - *this; }
 
    Mint pow(long long n) const
    {
        assert(0 <= n);
        Mint x = *this, r = 1;
        while (n)
        {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    Mint inv() const
    {
        assert(_v);
        return pow(MOD - 2);
    }
    friend Mint operator+(const Mint &lhs, const Mint &rhs) { return Mint(lhs) += rhs; }
    friend Mint operator-(const Mint &lhs, const Mint &rhs) { return Mint(lhs) -= rhs; }
    friend Mint operator*(const Mint &lhs, const Mint &rhs) { return Mint(lhs) *= rhs; }
    friend Mint operator/(const Mint &lhs, const Mint &rhs) { return Mint(lhs) /= rhs; }
    friend bool operator==(const Mint &lhs, const Mint &rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const Mint &lhs, const Mint &rhs) { return lhs._v != rhs._v; }
 
    static Mint w(int n)
    {
        assert((MOD - 1) % n == 0);
        return Mint(prr).pow((MOD - 1/ n);
    }
 
private:
    int _v;
};
 
template <class F>
void fft(vector<F> &a, bool inv)
{
    int N = a.size(), j = 0;
    vector<F> roots(N / 2);
    for (int i = 1; i < N; i++)
    {
        int bit = N >> 1;
        while (j >= bit)
        {
            j -= bit;
            bit >>= 1;
        }
        j += bit;
        if (i < j)
            swap(a[i], a[j]);
    }
 
    F w = F::w(N);
    if (inv)
        w = w.inv();
    for (int i = 0; i < N / 2; i++)
        roots[i] = i ? w * roots[i - 1] : F(1);
 
    for (int i = 2; i <= N; i <<= 1)
    {
        int step = N / i;
        for (int j = 0; j < N; j += i)
            for (int k = 0; k < i / 2; k++)
            {
                F u = a[j + k], v = a[j + k + i / 2* roots[step * k];
                a[j + k] = u + v;
                a[j + k + i / 2= u - v;
            }
    }
}
 
template <class F>
vector<F> convolution(vector<F> a, vector<F> b)
{
    int n = int(a.size()), m = int(b.size());
    if (!|| !m)
        return {};
    int z = 2;
    while (z < n + m - 1)
        z <<= 1;
 
    a.resize(z), fft(a, false);
    b.resize(z), fft(b, false);
    for (int i = 0; i < z; i++)
        a[i] *= b[i];
    fft(a, true), a.resize(n + m - 1);
 
    F iz = F(z).inv();
    for (int i = 0; i < n + m - 1; i++)
        a[i] *= iz;
 
    return a;
}
 
template <class F, vector<F> (*conv)(vector<F>vector<F>)>
class Polynomial
{
    vector<F> p;
 
public:
    Polynomial() : p() {}
    Polynomial(vector<F> v) : p(v) {}
    int deg() const { return (int)p.size() - 1; }
    F &operator[](int idx) { return p[idx]; }
    const F &operator[](int idx) const { return p[idx]; }
 
    void set_degree(int deg)
    {
        assert(deg >= -1);
        p.resize(deg + 1);
    }
 
    Polynomial operator+(const Polynomial &rhs) const
    {
        Polynomial ret = *this;
        if (ret.deg() < rhs.deg())
            ret.set_degree(rhs.deg());
        for (int i = 0; i <= rhs.deg(); i++)
            ret[i] += rhs[i];
        return ret;
    }
    Polynomial &operator+=(const Polynomial &rhs)
    {
        if (deg() < rhs.deg())
            set_degree(rhs.deg());
        for (int i = 0; i <= rhs.deg(); i++)
            p[i] += rhs[i];
        return *this;
    }
 
    Polynomial operator*(const Polynomial &rhs) const { return Polynomial(conv(p, rhs.p)); }
    Polynomial &operator*=(const Polynomial &rhs)
    {
        p = move(conv(p, rhs.p));
        return *this;
    }
 
    Polynomial inv(int degree = -1const
    {
        if (degree == -1)
            degree = deg();
        assert(deg() >= 0 && degree >= 0 && p[0== F(1));
 
        Polynomial a({F(1)});
        for (int l = 1; l <= degree; l *= 2)
        {
            Polynomial p0 = vector(p.begin(), p.begin() + min(l, (int)p.size()));
            Polynomial p1;
            if ((int)p.size() >= l)
                p1 = vector(p.begin() + l, p.begin() + min(2 * l, (int)p.size()));
 
            Polynomial ap0 = a * p0;
            Polynomial c = vector(ap0.p.begin() + l, ap0.p.end());
 
            Polynomial b = a * p1;
            b.set_degree(l - 1);
            b += c;
            b *= a;
            b.set_degree(l - 1);
            a.p.resize(2 * l);
            for (int i = l; i < 2 * l; i++)
                a.p[i] -= b[i - l];
        }
        a.set_degree(degree);
        return a;
    }
};
 
using Poly = Polynomial<Mint, convolution<Mint>>;
 
int solve(int K, vector<Mint> p)
{
    int N = p.size();
    Mint P = 0;
    for (Mint x : p)
        P += x;
    for (Mint &x : p)
        x = P - x;
 
    function<pair<Poly, Poly>(intint)> mul = [&](int s, int e)
    {
        if (s == e)
            return make_pair(Poly({1}), Poly({1-p[s]}));
        auto [lu, ld] = mul(s, (s + e) / 2);
        auto [ru, rd] = mul((s + e) / 2 + 1, e);
        return make_pair(lu * rd + ru * ld, ld * rd);
    };
 
    auto [u, d] = mul(0, N - 1);
    u *= d.inv(K);
 
    int ans = 0;
    for (int i = 1; i <= K; i++)
        ans ^= (Mint(N) * P.pow(i) - u[i]).val();
 
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++)
    {
        int N, K;
        cin >> N >> K;
        vector<Mint> p(N);
        for (Mint &x : p)
        {
            int v;
            cin >> v;
            x = v;
        }
        int ans = solve(K, p);
        cout << "Case #" << tc << '\n'
             << ans << endl;
    }
}
 
cs

 

'프로그래밍 > 알고리즘' 카테고리의 다른 글

SCPC 2022 본선 풀이  (0) 2022.09.03
SCPC 2021 2차 풀이  (0) 2021.08.07
SCPC 2021 1차 풀이  (0) 2021.07.17
Merry Problem Solving 4일차  (0) 2018.12.26
Merry Problem Solving 3일차  (0) 2018.12.24

 

 

연세대 미래캠퍼스 고급 알고리즘 강의자료를 업로드 합니다.

1주차 - 명제, 수학적 귀납법, 루프 불변

자료 https://www.overleaf.com/read/pmgtgrcqqszv

문제 9461, 14601, 15948

 

2주차 - 힙

자료 https://www.overleaf.com/read/qvchqswzmnby

문제 1927, 2751, 2696, 7662, 11003

 

3주차 - 최단거리 알고리즘

자료 https://www.overleaf.com/read/kywxcwtrgvzn

문제 11404, 1916, 1753, 11779, 1162, 24042, 8111, 8112, 8008

 

4주차 - 트리 분할정복 (트리 DP)

자료 https://www.overleaf.com/read/mgpvrnpbbgbb

문제 15681, 1967, 2533, 2213, 1693, 10075

 

5주차 - 탐욕법 (Greedy Algorithm)

자료 https://www.overleaf.com/read/dnrnkdnmvyzy

문제 5585, 1026, 7450, 1931, 1379, 22988, 1202, 11047, 25312, 11509, 25297, 16496, 13904, 12430, 7981, 24524

 

6주차 - 최소 신장 트리 (Minimum Spanning Tree)

자료 https://www.overleaf.com/read/mbwmfyjrdrwv

문제 1922, 2887, 4792, 16950, 4386, 21062

 

7주차 - 정수론과 조합론

자료 https://www.overleaf.com/read/gypvqtzcjqss

문제 17466, 10430, 13172, 11050, 11051, 11401, 13977, 14565, 2960, 1629, 24270, 1256, 9343, 2247

 

8주차 - 버킷, 토너먼트 트리

자료 https://www.overleaf.com/read/jdcpmmzwvcnp

문제 10868, 22976, 16975, 17408, 17407, 12855, 10167

 

9주차 - 문자열 알고리즘

자료 https://www.overleaf.com/read/qfhdypfjtsgd

문제 14425, 1786, 13713, 9248, 13505, 11479, 9249, 16900, 13576

+ Recent posts