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

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

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

 

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

 


1. 원 안의 점

  문제를 요약하면, 원점 $(0, 0)$을 중심으로 하는 반지름 $R$인 원 내부에 들어있는 좌표가 모두 정수인 점의 개수를 세는 문제이다. 단, 원의 경계에 놓인 점은 생각하지 않는다. ($R \le 200\,000$)

  풀이는 간단하다. $x$좌표가 $a$인 위치에 대해서 $y$좌표로 가능한 값은 $-\sqrt{x^2-a^2}$ 초과 $\sqrt{x^2-a^2}$ 미만인 값이고($-R < a < R$), 정수점의 개수는 $\sqrt{x^2-a^2}$ 미만인 양의 정수의 개수에다가 1을 곱한 값이다. 구현할 때는 $\sum_{a=-R+1}^{R-1} (\lfloor \sqrt{x^2-a^2-1} \rfloor$)과 같은 식으로 구현할 수 있다. ($x^2-a^2$은 정수이기 때문에, $x^2-a^2$ 미만인 정수는 $x^2-a^2-1$ 이하인 정수와 같다.)

  시간복잡도는 $\mathcal{O}(R)$이다.


2. 직8각형

  문제를 요약하면, 한 변의 길이가 $K$인 각 변이 축에 평행한 정사각형 5개가 그림처럼 +모양으로 배치되어 있을 때, 외각에 놓인 8개의 점을 길이가 $K$인 직8각형이라고 부른다. 평면 상의 점 8개와 $K$가 주어질 때, 길이가 $K$인 직8각형이 되도록 점을 옮기려고 한다. 여기서, 점의 순서는 중요하지 않다. 이 때, 필요한 점의 이동거리 합의 최소값을 구하는 문제이다. 여기서, 이동거리는 택시거리이다($(a, b)$와 $(c, d)$ 사이의 거리는 $|a-b| + |c-d|$이다.)

  어떤 점이 직8각형의 어떤 점에 대응되어야 하는지 알 경우에 필요한 이동거리 합의 최솟값을 구하는 방법을 생각해보자.

  첫째로, 택시거리는 $x$좌표와 $y$좌표의 차이의 합이기 때문에, $x$좌표와 $y$좌표를 따로 생각할 수 있다. 그렇기 때문에, $x$좌표와 $y$좌표에 대해 문제를 따로 따로 풀어줄 수 있다.

  둘째로, 이동거리가 최소가 되는 $p_0$의 $x$좌표를 편의상 $a$라고 하면, $p_0, p_1$으로 옮기는 점은 $x$좌표가 $a$, $p_2, p_7$로 옮기는 점은 $x$좌표가 $a+K$, $p_3, p_6$으로 옮기는 점은 $x$좌표가 $a+2K$, $p_4, p_5$로 옮기는 점은 $x$좌표가 $a+3K$가 되도록 옮겨야 한다. $p_i$로 옮겨야 하는 점의 $x$좌표를 $x_i$라고 하면, $|x_0 - a| + |x_1 - a| + |x_2 - (a+K)| + |x_3 - (a+2K)| + |x_4 - (a+3K)| + |x_5 - (a+3K)| + |x_6 - (a+2K)| + |x_7 - (a+K)|$ 를 최소화 하는 문제가 된다. 기본적으로 어떤 배열 $v$에 대해, 합 $|v_i-a|$를 최소화하는 문제는 매우 잘 알려진 문제로, $a$를 $v_i$의 중앙값으로 잡으면 된다. 이 경우도 유사하게, $a$를 $x_0, x_1, x_2-K, x_3-2K, x_4-3K, x_5-3K, x_6-2K, x_7-K$의 중앙값으로 설정하면 될 것이다. $y$좌표에 대해서도 문제를 비슷하게 풀어줄 수 있다.

  이런 식으로, 어떤 점이 직8각형의 어떤 점에 대응되어야 하는지 알 경우 필요한 이동거리 합의 최솟값은 $\mathcal{O}(8)$에서 $\mathcal{O}(8^2)$ 정도의 시간에 중앙값을 구해서 합을 구하는 방식으로 문제를 해결할 수 있다. 이제 모든 조합을 다 시도해보면 $\mathcal{O}(8! \times 8)$ 에서 $\mathcal{O}(8! \times 8^2)$ 정도 시간에 문제를 해결할 수 있다.


3. 산탄총

  문제를 요약하면, $N \times N$ 격자의 각 칸에 (음수일 수 있는) 수가 하나 써 있고, 산탄총의 퍼지는 정도 $K$가 주어진다. 산탄총을 어떤 칸을 중심으로 사격하면 중심과 택시거리가 $K$ 미만인 칸에 대해서, 해당 칸과 중심의 택시거리가 $x$이면 해당 칸에 있는 수에 $K-x$를 곱한 수 만큼의 점수를 얻는다. 여기서, 중심은 격자 밖일수도 있다. 산탄총을 한번 사격해서 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 오른쪽 그림은 $K=3$일때 산탄총을 사격해서 얻을 수 있는 점수의 모양이다. ($1 \le K \le N \le 600$)

  모든 칸을 중심으로 해서 산탄총을 쐈을 때, 각각의 점수를 구해서 그 중 최댓값을 구하면 되는 문제이다. 격자의 밖을 중심으로 하는 경우도 물론 고려해야한다. 격자에서 $K$ 이상 떨어진 곳을 중심으로 산탄총을 사격하는 경우에는 점수가 항상 0이므로 고려하지 않아도 되고, 각 좌표가 $-K$ 부터 $N+K$인 곳을 고려해서 사격하면 된다.

  이제, 각 칸의 점수를 효율적으로 구하기 위해서, 중심을 오른쪽으로 한 칸 옮길 때 점수 차이를 살펴보자. 두 칸의 경계를 기준으로 왼쪽에 있는 칸의 거리는 1씩 늘어나고, 오른쪽에 있는 칸의 거리는 1씩 줄어든다. 열 번호가 왼쪽 칸 이하이면서, 거리가 $K$미만인 칸(아래 그림에서 주황색 영역)의 수의 합만큼 값이 줄어들고, 열 번호가 오른쪽 칸 이상이면서, 거리가 $K$미만인 칸(아래 그림에서 파란색 영역)의 수의 합만큼 값이 늘어난다.

  이제, 파란색 영역과 주황색 영역의 합을 효율적으로 구해보자. 파란색 영역의 중심칸을 아래로 한 칸 옮기면 거리가 $K-1$인 점들이 바뀌게 된다. 여기서 위쪽 칸과 거리가 $K-1$이면서, 열 번호가 위쪽 칸 이상이고, 행 번호가 위쪽칸 이하인 점들(아래 그림에서 빨간색 영역)의 수의 합 만큼 값이 줄어들고, 아래쪽 칸과 거리가 $K-1$이면서, 열 번호가 위쪽 칸 이상이고, 행 번호가 오른쪽 칸 이상인 점들(아래 그림에서 초록색 영역)의 수의 합 만큼 값이 늘어난다. 주황색 영역도 대칭적으로 구할 수 있다.

  이제, 우리는 빨간색과 초록색으로 표현된 영역인 대각선 모양의 $K$개의 칸의 합을 효율적으로 구해야하는데, 이는 중심칸이 오른쪽 아래로 내려갔을 때, 왼쪽 끝과 오른쪽 끝의 수가 더해지고 빠지는 것으로 문제를 해결할 수 있다. (그림의 노란색과 보라색 칸) 초록색 영역도 대칭적으로 구할 수 있다.

문제에서 구해야하는 영역들

  이 영역들의 합을, 좌표를 섬세하게 계산해주면 문제를 해결할 수 있다. 각 영역은 중심이 한 점에서 다른 점으로 옮겨질 때 상수번의 연산만을 하기 때문에, 시간 복잡도는 $\mathcal{O}(N^2)$이다.


4. 패턴 매칭

  문제를 요약하면, 두 문자열 $A$와 $B$가 매칭된다는 것은, $A$와 $B$의 길이가 같고, $A_i = A_j$와 $B_i=B_j$가 동치라는 것을 의미한다. 텍스트 하나와 $K$개의 패턴을 주어질 때, 각 패턴이 텍스트에 등장하는 횟수를 계산하여라. (텍스트의 길이 $2\,000\,000$ 이하, 패턴의 길이 $500$이하, 패턴 길이 합 $30\,000$이하)

  Aho-corasik의 패턴 매칭 알고리즘을 사용하자. 우리가 문자열의 각 문자 대신 매칭에 사용할 대상은 이전에 같은 문자가 언제 등장했는지 여부이다. 다음과 같은 관찰을 활용하자.

 

  관찰. 어떤 문자열 $S$의 $f(S)$를 다음과 같이 정의하자.

    - $f(S)$는 길이가 $S$와 같은 배열이다. $f(S)$의 $i$ 번째 값은 $S_i = S_{i-L}$을 만족하는 최소인 양수 $L$이다. (조건을 만족하는 $L$이 없을 경우 $f(S)$의 $i$ 번째 값은 0이다.)

  문제에서 정의한 문자열 $A$와 $B$가 매칭되는 것은 $f(A)$와 $f(B)$가 동일한 것과 동치이다.

 

  증명. (⇒) $f$를 정의할 때 사용한 연산은, 문자열의 두 값이 같다는 연산 뿐이기 때문에, 문제에서 주어진 $A$와 $B$에 대한 $f(A)$와 $f(B)$의 값은 동일하다.

  (⇐) $A_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치를 찾아보자. $f(A)_i$가 0이면, 같은 문자가 등장하지 않는다. $f$의 정의에 따라, $A$의 $i-f(A)_i$ 번째 위치에서 $A_i$와 같은 문자가 등장하고, $i-f(A)_i$ 번째 위치에서 $i$번째 위치 사이에서는 문자가 등장하지 않는다. 이제 $i-f(A)_i$ 번째 위치 이전에서는 $A_i$와 같은 문자가 언제 등장하는지를 살펴보자. $A_{i-f(A)_i} = A_i$이기 때문에, $f(A)$ 배열의 $i-f(A)_i$ 값을 확인하는 것으로 재귀적으로 확인해 줄 수 있다.

$f(A)$와 $f(B)$의 값이 같다는 것은, $A_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치와, $B_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치의 집합이 같다는 뜻이다. 그렇기 때문에, $A_i = A_j$와 $B_i=B_j$는 동치이다.

 

  이를 직접 사용하려고 하면, 위의 정의가 "길이가 다른 두 문자열"에 대해서는 동작하지 않는다는 것을 알 수 있다. 예를 들면 $S=abaca$와 $T=xyx$가 있다고 하자. $f(S)$는 $[0, 0, 2, 0, 2]$이고 $f(T)$는 $[0, 0, 2]$이다. 위에 정의한 문자열 매칭을 그대로 사용하면, $S$는 $T$의 첫 번째 위치에서만 매칭되는 것으로 생각되지만, 실제로는 세번째 위치에서도 매칭된다. 이는 부분문자열 $aca$와 $xyz$에서 첫번째 $a$에 해당하는 $f$값 $2$가 매칭되는 패턴 $xyz$의 $x$의 인덱스인 $0$보다 커서, $2$칸 전의 문자가 사실 같음에도 매칭할 때는 고려대상이 되지 않기 때문에 발생하는 문제이다. 특정 위치의 함수값이 인덱스보다 큰 경우는 고려 대상에서 제외해서 배열의 값을 $0$으로 바꿔줘야 하고, 이는 Aho-corasik의 failure function을 계산할 때 처리해 줄 수 있다.

  이래서, (일반적인) 스트링 $f(T)$에서 패턴 $f(P)$가 언제 등장하는지 개수를 세는 문제로 바뀌었다. 기본적인 Aho-corasik 문제임으로 따로 설명하지는 않는다. 위의 failure function을 계산할 때, 자기보다 길이가 긴 인덱스 값이 등장하는 시점에 유의하자.

  시간복잡도는 문자열 길이와 패턴 길이 합의 선형에 비례하는 시간복잡도가 든다.


5. Hanoi Tower

  문제를 요약하면, 일반적인 하노이 타워 문제와 같이, 1번 기둥에 있는 원판을 3번 원판으로, 큰 디스크가 작은 디스크 위에 올라가지 않도록 모두 옮기는 문제이다. 단, 기존 하노이 타워는 한 기둥에서 다른 기둥으로 옮길 때, 한 기둥의 첫 번째 원판을 다른 기둥의 첫 번째 원판이 되도록 옮겼다. 하지만, 이번 하노이 타워는 한 기둥의 가운데 원판이 다른 기둥의 "가운데 원판"이 되도록 옮겨야 한다. 여기서 어떤 기둥의 가운데 원판은, 그 기둥에 쌓인 원판의 개수를 $n$이라고 할 때, $1+\left\lfloor\frac{n}{2}\right\rfloor$ 번째 원판을 말한다. 최대 이동 회수 $M = 980403$이 주어졌을 때, 디스크의 개수 $N$을 (코드를 제출하는 사람이) 정하고, 1번 기둥의 $N$개의 원판을 3번 기둥으로 옮기는 문제이다. ($N = 26$인 경우 만점이다.)

  여러가지 관찰이 필요한 문제이다. 다음과 같은 관찰을 하나씩 해 보자.

 

관찰 1. 한 기둥의 가장 위에 있는 원판을 다른 기둥의 가장 위로 옮기려면, 해당 원판을 제외하고는 두 기둥에 다른 어떠한 원판도 존재하지 않아야 한다.

증명. $n=1$인 경우만 $1+\left\lfloor\frac{n}{2}\right\rfloor = 1$이 된다.

 

  편의상 원판의 번호를 작은 것 부터 큰 것 까지 $1$부터 $N$까지의 번호를 붙이자. 여기서 다음과 같은 전략을 사용할 수 있다. 1번 기둥에서 3번 기둥으로 원판을 모두 옮기기 위해서는 $2$번 원판부터 $N$번 원판까지를 전부다 2번 기둥으로 옮긴다음에, 1번 기둥에서 3번 기둥으로 1번 원판을 옮기고, 2번 기둥에 놓인 $N-1$개의 원판을 다시 3번 기둥으로 옮겨야 한다.

과정 M000, 이름이 붙은 이유는 아래 문단이 설명되어 있다.

  일반적인 하노이 타워 문제는 나머지 원판들에 대해 재귀적으로 같은 방식으로 진행했겠지만, 이 문제는 다른 점이 있다. 바로, 1번 원판의 존재때문에 기둥을 빼내는 순서가 다르다는 점이다. 1~5번 원판이 쌓여있을 때 빠지는 순서는 3, 4, 2, 5(, 1)순이다. 하지만 2~5번 원판이 쌓여있을 때 빠지는 순서는 4, 3, 5, 2순이다. 즉, 어떤 기둥 위에 (고정되어서 빠지지 않는) 원판이 $0$개 있는지 $1$개 있는지에 따라서 과정이 다르게 된다. $a$, $b$, $c$번 기둥 위에 고정된 원판이 각각 $x$, $y$, $z$개 있는 상황에서 a번 기둥에서 c번 기둥까지 $N$개의 원판을 옮기는 과정을 $Mabc(N, a, b, c)$이라고 말하자. 가장 처음의 상황은 $M000(N, 1, 2, 3)$이고, $M000(N, a, b, c)$는 $M100(N-1, a, c, b)$를 수행하고, $a$에서 $c$로 1번 원판을 옮기고, $M001(b, a, c)$를 수행하게 된다. 이제 해당 기둥의 "가운데 원판"의 위치가 바뀐다.

 

관찰 2. 기둥 위에 고정된 원판이 1개 있는 경우, 가운데 원판을 $\left\lfloor\frac{n+1}{2}\right\rfloor$번 원판이라고 생각하면 된다. 또한, 해당 기둥의 가장 아래에 있는 원판을 옮기려면, 해당 기둥에는 고정된 원판과 가장 아래에 있는 원판을 제외하고, 남은 원판이 없어야 한다.

 

증명. 고정된 원판 1개를 제외하고 원판이 $n$개 있는 경우, 고정된 원판을 포함한 중심 위치는 $1+\left\lfloor\frac{n+1}{2}\right\rfloor$번째이다. 첫 번째인 고정된 원판을 제외하면, 중심 위치는 $\left\lfloor\frac{n+1}{2}\right\rfloor$번 원판이 된다. 여기서 $n \ge 1$ 일 때, 항상 $1 \le \left\lfloor\frac{n+1}{2}\right\rfloor \le n$을 만족하므로, 중심 원판은 항상 옮기려는 원판 중에 존재한다. 가장 아래쪽에 있는 원판을 꺼내려면, $n = \left\lfloor\frac{n+1}{2}\right\rfloor$ 이어야 하고, 이 경우는 $n=1$이다. 옮기려는 원판을 제외하고는 다른 원판이 존재하지 않는다.

 

  이제 해당 과정을 기준으로 $M100(N, a, b, c)$상황을 생각해보자. ($M001$은 $M100$의 역순으로 진행된다.) 가장 아래에 있는 원판을 옮기는 과정을 생각해보자. 이도 마찬가지로, $a$번 기둥의 $N$번 원판을 제외한 원판들을 전부 $b$번 원판에 옮기고 $N$번 원판을 $c$번 원판에 옮긴 이후에, $b$번 기둥의 나머지 원판을 $c$번 기둥으로 옮기면 된다.

  여기서, 과정을 잘 살펴보면 $a$번 기둥에서 마지막에 나오는 두 개의 1번 원판과 $N$번 원판을 옮길 때, $b$번 기둥을 거쳐갈 필요 없이 $c$번 기둥으로 두 원판을 차례로 옮길 수 있다는 것을 알 수 있다. ($a$번째 원판과 $c$번째 원판의 "가운데 원판"을 정의하는 홀짝성이 달라서 발생하는 일이다.) 그래서 과정을 바꿔서 $N-2$개의 기둥을 한번에 옮기는 것으로 문제를 풀 수 있다.

과정 M100, 고정된 원판은 -로 표시되었다.

  이제, 여기서 재귀적인 과정을 하려면 또 역시 자신 위와 아래에 있는 원판이 문제라는 것을 알 수 있다. 하지만 이 경우에는 중심 원판이 바뀌지 않기 때문에, 다음과 같은 관찰을 이용해서 재귀식을 그대로 사용할 수 있다.

 

관찰 3. 기둥 위에 고정된 원판이 X+K개, 아래쪽에 X개 있는 경우 가운데 원판은 기둥 위에 고정된 원판이 $K$개, 아래쪽에 $0$개 있는 경우와 같다.

 

증명. 원판이 $n$개 있는 경우, 고정된 원판을 포함한 중심 위치는 $1+\left\lfloor\frac{n+2X+K}{2}\right\rfloor$번째이다. $X+K$개의 고정된 원판을 제외하면, 중심 위치는 $1-K+\left\lfloor\frac{n+K}{2}\right\rfloor$번 원판이 된다. $K=0$일 때는, 위에서 $1+\left\lfloor\frac{n}{2}\right\rfloor$번째, $K=1$일 때는, 위에서 $\left\lfloor\frac{n+1}{2}\right\rfloor$번째 원판이다.

 

  그래서 $1$번과 $N$번 원판을 더 이상 옮기지 않을 생각으로 같이 무시해주어도, 원반의 위치는 변하지 않는다. $M100(N, a, b, c)$는 $M100(N-2, a, c, b)$를 진행하고, $a$ 번 기둥에서 $c$ 번 기둥으로 원판을 두 번 옮기고, $M010(N-2, b, a, c)$를 진행해주면 된다.

  이제 $M010$을 살펴보자. $M010$은 $M000$과 유사하지만, 가운데 원판에 따른 홀짝성을 고려해서 $M101(N-1, a, c, b)$를 진행하고 $a$번 기둥에서 $c$번 기둥으로 원판을 옮기고, $M101(N-1, b, a, c)$를 진행하면 된다. 하지만 이것이 최적이 아닌 경우는 위에 논의했던 대로 $a$ 번 기둥에서 $b$ 번 기둥에 홀짝성이 다른 점을 이용하면 한 번에 두 개의 원판을 옮길 수 있기 때문이다. 이를 이용해서 $a$ 번 기둥에서 $c$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기고, $a$ 번 기둥에서 $b$ 번 기둥으로 $1$번과 $N$번 원판을 옮기고, $c$ 번 기둥에서 $a$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기고, $b$ 번 기둥에서 $c$ 번 기둥으로 $1$번과 $N$번 원판을 옮기고 $a$ 번 기둥에서 $c$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기면 된다.

  ...여기까지가 Jérémy Barbay가 arXiv[1602.03934]에 올린 "Bouncing Towers move faster than Hanoï Towers, but still require exponential time"라는 아티클에 설명되어 있는 사항이고, 이 아티클은 이 방법이 최적이라고 주장하지만, 이 아티클의 증명이 틀렸는지 이 문제가 만점을 받을 수 없는 문제인지, 위에 적힌 방법으로는 만점을 받을 수 없다.($N=25$일 때 $885\,735$번, $N=26$일 때 $1\,594\,323$번 움직인다.)

과정 M010?, 고정된 원판은 -로 표시되었다.

 

 

 

 

 

 

 

  이 문제에서 만점을 받으려면, 해당 아티클의 증명의 틀린 부분을 찾으면서 위 문제의 설명에서 간과되어 있는 부분을 찾아야 하는데, $M010(N, a, b, c)$의 과정은 바깥에 있는 고정된 원판을 움직일 수 없는 것을 가정하고 있지만, 사실 고정된 원판을 움직이고 원래 위치로 돌려놓으면 된다!

  다음과 같은 과정을 생각하자. $N$번 원판의 위치를 고려하지 않고 $1$번부터 $N-1$번까지의 원판을 $a$ 번 기둥에서 $b$ 번 기둥으로 옮겨놓는다. 그 후 $N$번 원반이 $a$ 번 기둥에 있으면 $c$ 번 기둥으로, $c$ 번 기둥에 있으면 $a$ 번 기둥으로 옮긴 다음에, 다시 $1$번부터 $N-1$번까지의 원판을 위 과정의 역순으로 $b$ 번 기둥에서 $c$ 번 기둥으로 옮겨놓는다. 이 경우 $M010(N, a, b, c)$는 (Notation을 확장해서 관찰 3에서 $K=-1$이라는 의미로) $M(-1)01(N-1, a, c, b)$를 진행하고 $N$번 원판의 $a$, $c$위치를 바꾼 이후에 $M10(-1)(N-1, b, a, c)$를 실행한다고도 볼 수 있겠다. 여기서 $K$가 $0$이나 $1$이 아닐 경우에는, 가운데 원판이 고정된 원판을 가리킬 수 있다는 점이고, 우리는 이 경우를 특별하게 허용하기로 했다.

과정 M010, 고정된 원판은 -로 표현되었다.

  위쪽에서 고정된 원판을 -로 표현했다. 아래쪽에서 고정된 원판은 +로 표현하자. $1$번부터 $N$번까지의 원판을 빼내는 과정의 마지막은 $2, +, 1$번 원판 순이 되어버렸다. 이 경우에도 $1$번 원판을 빼내려면 나머지 원판을 다 빼내야 하기 때문에, 나머지 $2$번부터 $N$번 원판까지를 생각해보자. 가장 빨리 빼내는 방법은 $2$번부터 $N$번까지의 원판을 한 개 이하를 제외하고 $b$ 번 기둥에 몰아놓은 이후에 1번 원판을 $c$ 번 기둥으로 옮기는 것이다. 여기서 한 개 이하의 원판을 제외하는 이유는, 한 개의 원판이 있어도 1번 원판이 $c$번 기둥으로 들어갈 수 있기 때문이다. 여기서 우리는 1번과 2번 다음으로 빼기 어려운 $N$ 번 원판을 $c$ 번 기둥에 같이 남기는 방식을 사용할 것이다.

  $3$번 원판부터 $N$ 번 원판까지를 $c$ 번 기둥에 옮기고, $2$번과 $+$ 번 원판을 $b$ 번 기둥에 옮기다. 그리고 나머지 허용된 하나의 $N$ 번 기둥을 제외한 $3$번 부터 $N-1$번 원판을 $b$ 번 기둥에 옮긴다. 나머지는 재귀적으로 $M(-1)01(N-2, b, a, c)$를 호출해주면 된다.

과정 M(-1)01, 고정된 원판은 -, 가장 커서 위치를 자유로이 할 수 있는 원판은 +로 표현되었다.

  이를 구현하면 $N=26$일 때 $972\,051$번 연산을 사용해서 원판을 전부 옮길 수 있고, 이는 $980\,403$이라는 제한 안에 들어가는 수이다.


아래는 풀이를 구현한 소스코드이다.

 

#1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
 
long long solve(int N)
{
    long long ans = 0;
    for(int i=-N+1; i<=N-1++i)
    {
        int j = sqrt(1LL*N*N-1LL*i*i-1);
        ans += 2*j+1;
    }
    return ans;
}
 
int main()
{
    int T; scanf("%d"&T);
    for(int i=1; i<=T; ++i)
    {
        int N; scanf("%d"&N);
        printf("Case #%d\n%lld\n", i, solve(N));
    }
}
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
#include <bits/stdc++.h>
using namespace std;
 
 
int solve(int K, vector<pair<intint> > V)
{
    sort(V.begin(), V.end());
    long long minv = LLONG_MAX;
    do
    {
        const int dx[] = {00123321};
        const int dy[] = {12332100};
        vector<int> xc, yc;
        for(int i=0; i<8++i)
        {
            xc.push_back(V[i].first+dx[i]*K);
            yc.push_back(V[i].second+dy[i]*K);
        }
        sort(xc.begin(), xc.end()); sort(yc.begin(), yc.end());
        long long ans = 0;
        for(int i=0; i<8++i)
            ans += abs(xc[i]-xc[3])+abs(yc[i]-yc[3]);
        minv = min(ans, minv);
    }while(next_permutation(V.begin(), V.end()));
 
    return minv;
}
 
int main()
{
    int T; scanf("%d"&T);
    for(int i=1; i<=T; ++i)
    {
        int K; scanf("%d"&K);
        vector<pair<intint> > V;
        for(int j=0; j<8++j)
        {
            int a, b; scanf("%d%d"&a, &b);
            V.emplace_back(a, b);
        }
        printf("Case #%d\n%d\n", i, solve(K, V));
    }
}
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
#include <bits/stdc++.h>
using namespace std;
 
long long solve(int N, int K, vector<vector<long long> > A)
{
    vector<vector<long long> > D(N+2*K, vector<long long>(N+2*K)), U = D, R = D, L = D, ans = D;
    auto get = [N, K](const vector<vector<long long> >& V, int x, int y)
    {
        if(x < 0 || x >= N+2*|| y < 0 || y >= N+2*K) return 0LL;
        return V[x][y];
    };
 
    long long ret = 0;
    for(int i=0; i<N+2*K; ++i)
        for(int j=0; j<N+2*K; ++j)
        {
            D[i][j] = get(D, i-1, j-1- get(A, i-K, j-1+ get(A, i, j+K-1);
            U[i][j] = get(U, i-1, j+1- get(A, i-1, j+K) + get(A, i+K-1, j);
        }
    for(int i=0; i<N+2*K; ++i)
        for(int j=0; j<N+2*K; ++j)
        {
            R[i][j] = get(R, i-1, j) - get(D, i-1, j) + get(U, i, j);
            L[i][j] = get(L, i-1, j) - get(U, i-K, j-K+1+ get(D, i+K-1, j-K+1);
        }
    for(int i=0; i<N+2*K; ++i)
        for(int j=0; j<N+2*K; ++j)
            ret = max(ret, (ans[i][j] = get(ans, i, j-1- get(L, i, j-1+ get(R, i, j)));
    return ret;
}
 
int main()
{
    int T; scanf("%d"&T);
    for(int t=1; t<=T; ++t)
    {
        int N, K; scanf("%d%d"&N, &K);
        vector<vector<long long>>V(N+2*K, vector<long long>(N+2*K));
        for(int i=K; i<N+K; ++i)
            for(int j=K; j<N+K; ++j)
                scanf("%lld"&V[i][j]);
        printf("Case #%d\n%lld\n", t, solve(N, K, V));
    }
    return 0;
};
cs

#4 (node가 패턴의 길이만큼의 배열을 담고 있어서, 시간복잡도가 더 크나, 통과 가능하다)

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
#include <bits/stdc++.h>
using namespace std;
 
vector<int> convert(string s)
{
    vector<int> res(s.size());
    vector<int> arr(26-1);
    for(int i=0; i<(int)s.size(); ++i)
    {
        int c = s[i]-'a';
        if(arr[c] == -1) res[i] = 0;
        else res[i] = i - arr[c];
        arr[c] = i;
    }
    return res;
}
 
const int PATTERN_MAXL = 500;
const int PATTERN_TOTLEN = 30000;
 
struct Node
{
    int L, cnt;
    int next[PATTERN_MAXL+1];
    int fail;
} NODE[PATTERN_TOTLEN+1];
 
int tp = 0;
 
void reset(){ tp = 0; }
 
int new_node()
{
    NODE[tp].L = NODE[tp].cnt = 0;
    memset(NODE[tp].next, -1sizeof NODE[tp].next);
    NODE[tp].fail = -1;
    return tp++;
}
 
int get_fail(int node, int c)
{
    if(node == -1return 0;
    if(c > NODE[node].L) c = 0;
    if(NODE[node].next[c] != -1return NODE[node].next[c];
    return get_fail(NODE[node].fail, c);
}
 
int put(int node, int c)
{
    if(NODE[node].next[c] != -1return NODE[node].next[c];
    int ret = new_node();
    NODE[ret].L = NODE[node].L + 1;
    NODE[node].next[c] = ret;
    return ret;
}
 
vector<int> fail_order;
void forward_fail()
{
    fail_order.clear();
    queue<int> Q; Q.push(0);
    while(!Q.empty())
    {
        int n = Q.front(); Q.pop();
        fail_order.push_back(n);
        for(int i=0; i<=NODE[n].L; ++i)
        {
            int m = NODE[n].next[i];
            if(m != -1)
            {
                Q.push(m);
                NODE[m].fail = get_fail(NODE[n].fail, i);
            }
        }
    }
}
void back_prop()
{
    reverse(fail_order.begin(), fail_order.end());
    for(int n: fail_order)
        if(n != 0)
            NODE[ NODE[n].fail ].cnt += NODE[n].cnt;
}
 
 
vector<int> solve(vector<int> s, vector<vector<int>> V)
{
    reset();
    int root = new_node();
    vector<int> patNodes;
    for(const auto& pat: V)
    {
        int cur = root;
        for(auto v: pat)
            cur = put(cur, v);
        patNodes.push_back(cur);
    }
    forward_fail();
    int cur = root;
    for(auto v: s)
    {
        cur = get_fail(cur, v);
        NODE[cur].cnt++;
    }
    back_prop();
    for(auto& v: patNodes) v = NODE[v].cnt;
    return patNodes;
}
 
int main()
{
    ios::sync_with_stdio(false);
    int T; cin >> T;
    for(int t=1; t<=T; ++t)
    {
        int N, K; string s; cin >> N >> K >> s;
 
        vector<vector<int>> V(K);
        for(auto& v: V)
        {
            string s; cin >> s; v = convert(s);
        }
 
        vector<int> res = solve(convert(s), V);
 
        long long ans = 0;
        for(int i=1; i<=K; ++i) ans += res[i-1]*i;
 
        cout << "Case #" << t << endl << ans << 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
#include <string>
#include <iostream>
using namespace std;
 
string op[3= {"*AB""C*D""EF*"};
string B1(intintintint), B2(intintintint), C(intintintint);
string D1(intintintint), D2(intintintint);
 
string A(int N, int a, int b, int c)
{
    if(N == 0return string();
    return B1(N-1, a, c, b) + op[a][c] + B2(N-1, b, a, c);
}
 
string B1(int N, int a, int b, int c)
{
    if(N == 0return string();
    if(N == 1return string({op[a][c]});
    return B1(N-2, a, c, b) + op[a][c] + op[a][c] + C(N-2, b, a, c);
}
 
string B2(int N, int a, int b, int c)
{
    if(N == 0return string();
    if(N == 1return string({op[a][c]});
    return C(N-2, a, c, b) + op[a][c] + op[a][c] + B2(N-2, b, a, c);
}
 
string C(int N, int a, int b, int c)
{
    if(N == 0return string();
    if(N == 1return string({op[a][c]});
    if(N == 2return string({op[a][b], op[a][c], op[b][c]});
    return D1(N-1, a, c, b) + (N%4 < 2 ? op[a][c]: op[c][a]) + D2(N-1, b, a, c);
}
 
string D1(int N, int a, int b, int c)
{
    if(N == 0return string();
    if(N == 1return string({op[a][b], op[a][c]});
    if(N == 2return string({op[a][c], op[a][b], op[a][c]});
    return C(N-2, a, b, c) + op[a][b] + op[a][b] + C(N-3, c, a, b) + op[a][c] + D1(N-2, b, a, c);
}
 
string D2(int N, int a, int b, int c)
{
    if(N == 0return string();
    if(N == 1return string({op[a][c], op[b][c]});
    if(N == 2return string({op[a][c], op[b][c], op[a][c]});
    return D2(N-2, a, c, b) + op[a][c] + C(N-3, b, c, a) + op[b][c] + op[b][c] + C(N-2, a, b, c);
}
 
string solve(int N)
{
    return A(N, 012);
}
 
int main()
{
    int N = 26;
    cout << "Case #1" << endl << N << endl << solve(N) << endl;
}
cs

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

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

SCPC 2021 1차 대회가 7월 16일 오후 3시부터 24시간동안 진행되었다.

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

 

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

 


1. 친구들

  문제를 요약하면, i 번 정점과 i+Di 번 정점을 연결 할 때, (1≤Di≤N, i+Di가 N을 넘으면 연결하지 않음), 연결 성분의 개수를 계산하는 문제이다. 그래프를 만들어주고 DFS와 같은 방법을 이용해서 연결 성분을 세어 주면 끝나는 문제이다.

  이 문제에는 같은 시간복잡도의 좀 더 간단한 풀이가 있는데, i+Di가 N을 넘는 수의 개수가 답이 된다. 이를 증명하기 위해서는 다음과 같은 관찰이 필요하다.

 

- 이 그래프에는 사이클이 존재하지 않는다.

  만약에 이 그래프에 사이클이 존재한다고 하자. 이 때, 이 사이클에 있는 정점중 가장 낮은 번호를 가진 정점은, 자기보다 번호가 큰 정점 두 개와 연결이 되어있다. 정점을 연결하는 규칙은 수가 작은 i 번 정점과 수가 큰 i+Di 번 정점을 연결하는 것이므로 작은 i 번 정점에 두 개의 연결이 있을 수 없어서 모순이다.

 

이런 관찰을 통해, 최초에 정점이 존재하지 않았던 상태에서 연결 성분의 개수가 N개이고, 한 번 연결할 때 마다 연결 성분의 개수가 1씩 줄어드므로, 답은 N - (i+Di가 N 이하인 수의 개수) = i+Di가 N 초과인 수의 개수이다.

 

 


2. 이진수

  문제를 요약하면, 길이 N의 0과 1로 이루어진 문자열 B와 어떤 상수 T가 주어지는데, 0과 1로 이루어진 (숨겨진) 길이 N의 문자열 A에 대해서 Ai+T와 Ai-T중 1이 하나 이상 존재하는 경우에만 Bi가 1이 되도록 만들어진 문자열이다. 단, A의 i+T번째 문자나 i-T번째 문자가 존재하지 않는 경우에는 0으로 취급한다. 사전순으로 가장 빠른 A를 찾아서 출력하는 문제이다.

 

주어진 입력에 해당하는 A가 존재하는지 (문제에서 요구하지는 않았지만) 찾는 알고리즘을 생각하도록 하자.

 

- Bi-T나 Bi+T중 0이 있다면, Ai는 0이어야 한다.

  만약 Ai가 1인 경우, Bi-T와 Bi+T가 (존재한다면) 1이어야 하기 때문에, 만약 이 두 수 중 0이 있으면, Ai는 0이어야 모순이 발생하지 않는다.

 

- Bi-T와 Bi+T중에 0이 없다면, Ai를 1로 두어도 "상관 없다." 여기서 "상관 없다"의 의미는, A가 만약에 존재한다면, Ai가 1인 답도 존재한다는 의미이다.

  만약에 Ai가 0인 답이 존재한다고 하자. 이 Ai를 1로 바꾸게 되면, Bi-T와 Bi+T만 영향을 끼치고, 이 두 숫자는 이미 1이기 때문에, 해당하는 칸에도 영향을 끼치지 않는다. 그래서 Ai가 1이게 되는 답이 존재한다.

 

  이 두 가지 사항을 이용해서, A가 존재하는지 찾는 알고리즘을 만들었으면, 사전순으로 가장 빠른 A를 찾는 알고리즘은, 가장 첫 자리가 0인 A가 존재하는지 확인하고, 존재한다면 가장 첫 자리를 0으로, 존재하지 않는다면 가장 첫 자리를 1로 설정한다. 마찬가지로 (첫 자리가 고정된 A에 대해) 둘째 자리가 0인 A가 존재하는지 확인하고, 존재한다면 가장 첫 자리를 0으로, 존재하지 않는다면 1로 설정한다, 이를 계속 반복하는 것이 문제의 풀이가 될 것이다. 여기까지의 알고리즘을 구현하면 O(N2) 시간 복잡도의 풀이를 얻을 수 있다.

 

  이 알고리즘의 시간을 줄이는 법은, A가 존재하는지 확인하는 알고리즘은 Ai의 값 하나의 변경에 대해서는 작은 영향을 끼친다는 것을 관찰하는 것이다. 주어진 입력에 해당하는 최대의 A를 만들자. 그 후, 앞에서부터 살펴보면서, 1이 있으면 해당 1을 0으로 바꿀 수 있으면 바꾸는 과정을 반복하면 문제를 해결할 수 있다. (이는 Ai가 0인 A가 존재하는지 확인하고, 가능하면 0으로 설정하는 과정과 동일하다.) 1을 0으로 바꿀 수 있는지 여부는 Ai를 바꾸었을 때, B라는 문자열 전체, 특히 Bi-T와 Bi+T가 바뀌지 않을 것을 의미한다. 이를 위해서 추가적으로 Ai-2T와 Ai+2T 칸을 확인 해 줘야 한다. 이 과정을 구현하면 O(N) 시간 복잡도의 풀이를 얻을 수 있다.

 


3. No Cycle

 

  문제를 요약하면, 그래프가 주어지는데 M개의 간선들은 방향성이 있고, K개의 간선들은 방향성이 없다. 이 때, 방향성이 없는 간선에 적당히 방향을 줘서 사이클이 없도록 해야한다. 단, 답이 여러개 존재하는 경우에 사전순으로 가장 빠른 답을 출력해야한다. 여기서 답은 길이 K의 0과 1로 이루어진 문자열인데, i 번째 방향성이 없는 간선은 두 개의 정점 쌍 (ui, vi)로 주어지며, ui→vi로 방향을 주면 답의 i번째 문자가 0이고, vi→ui로 방향을 주면 답의 i번째 문자가 1이다.

 

  2번 문제와 유사한 종류의 관찰을 요구한다. 일단 답이 존재하는지 아닌지 찾는 알고리즘에 대해서 확인 해 보자. 방향이 주어진 M개의 간선에 대해서는 사이클이 없기 때문에 위상정렬을 실행할 수 있고, 해당 위상정렬에 대해 뒤쪽에 있는 간선을 앞쪽에 있는 간선으로 이어주면 항상 사이클이 없는 답을 찾을 수 있다.

 

  사전순으로 가장 빠른 것을 찾는 알고리즘은 2번 문제에 설명된 대로 가장 첫 자리를 0인 답이 존재하는지 아닌지 확인하고, 존재한다면 0, 존재하지 않는다면 1로 설정한 뒤에, 둘째 자리에 대해서도, 셋째 자리에 대해서도 마찬가지로 같은 방법으로 문제를 해결하는 것이다. 이 문제에서는 이미 방향성이 주어진 간선이 사이클이 존재하지 않는 경우 항상 답이 존재하기 때문에, i 번째 자리를 정하고 있다면 i+1 번째 이후의 모든 간선을 무시하고, i번째 간선을 정방향으로 넣었을 때 지금까지 들어가있는 간선에 사이클이 존재하지 않는지 여부를 확인 해 주는 것으로 문제를 해결할 수 있다. 시간복잡도는 O(MK+K2)이다.

 


4. 예약시스템

  문제를 요약하면, 사람이 2M명 있고 그룹이 N개 있다. 각 사람은 그룹 중 하나에 속해있으며, 스트레스 지수가 있다. 이 2M명의 사람을 2×M 모양의 방에 배치하려고 하는데, 그룹이 다른 두 사람이 인접한 방에 배치된 경우에는 충돌이 발생하고, 두 사람의 스트레스 지수의 합만큼 비용이 발생한다. 방에 사람을 적당히 배치해서 비용의 합을 최소화 하는 문제이다. 단, 같은 그룹끼리는 서로 연결되어 배치되어 있어야 하고, 한 그룹에는 5명 이상의 사람이 속해있다.

 

  문제를 생각하기 용이하게 해주도록 배치의 비용을 다르게 나타내어 보자. 사람을 기준으로 생각했을 때, 해당 사람이 만드는 충돌의 개수는, 그 사람에게 인접한 다른 색을 가진 사람의 개수랑 같다. 그렇기 때문에, 총 비용은 모든 사람의 (해당 사람과 인접한 색이 다른 사람 수)×(해당 사람의 스트레스 지수)의 합이다.

 

  이제 정답이 가질 수 있는 배치를 생각 해 보자, 첫번째로 2×M 모양에서 첫번째 열과 마지막 열은 특수하게 다루어져야 하는데, 그룹의 경계를 생각할 때 가장 왼쪽 혹은 가장 오른쪽 열은 그룹의 경계이지만 충돌이 발생하지는 않는다. 그렇기 때문에, 우리는 이 두 열에 대한 특수한 배치를 증명할 것이다.

 

- 첫번째 열과 마지막 열의 두 사람이 같은 그룹인 정답이 존재한다.

  만약에 첫번째 열을 차지하는 두 그룹이 다른 사람인 정답이 존재한다고 하자. 이 둘은 크기가 더 작은 그룹이 존재한다. 해당 그룹을 A라고 하자. 모든 그룹은 연결되어야 하기 때문에, A는 일직선으로 존재하고 B도 A의 맞은 편 행에 일직선으로 존재하게 된다. (A가 끝난 이후에는 아무렇게나 존재할 수 있다.) 각 사람에 대해서 다음 그림과 같이 번호를 붙이자. (A3가 A의 가장 왼쪽 사람, A2, A1이 A의 가장 오른쪽 사람, A1의 오른쪽 사람이 C이고, B1, B2가 B의 가장 왼쪽 사람, B3가 A1의 맞은편 행에 있는 사람이다.)

  여기서 연결관계가 바뀐 사람들의 비용차이를 계산 해 보자. 여기서 B와 C가 같은 그룹일 수 있음에 유의하여라.

    * A1: 발생하는 충돌이 1개 줄었다. (B3, C → B2)

    * A2: 발생하는 충돌이 1개 늘었다. (B1)

    * A3: 발생하는 충돌이 1개 줄었다. (B1)

    * B1: 발생하는 충돌이 1개 혹은 0개 늘었다. (A3 → A2, C)

    * B2: 발생하는 충돌이 1개 줄었다. (A1)

    * B3: 발생하는 충돌이 1개 줄었다. (B1)

    * C: 발생하는 충돌이 1개 혹은 0개 줄었다. (B1)

  바꿔서 코스트가 가장 커지는 경우는 발생하는 B1에서 발생하는 충돌이 1개 늘고, C에서 발생하는 충돌이 바뀌지 않는, B와 C가 다른 그룹인 경우이다. 이 경우를 상정하자.

  최초 배치에서, A1은 충돌이 2개 발생하고, A2는 충돌이 1개 발생했다. 그렇기 때문에 위의 답이 최적이려면 A2의 스트레스 지수는 A1의 스트레스 지수보다 크거나 같아야 한다. 또한, B1과 B2는 모두 충돌이 1개 발생했기 때문에, B1의 스트레스 지수가 B2의 스트레스 지수보다 작거나 같은 답이 존재한다. 이런 사항을 고려해보면, A1과 B1에서 발생하는 비용의 증가는 A2와 B2에서 발생하는 충돌의 감소가 모두 해결해 줄 수 있고, 추가로 A3와 B3 혹은 C에서 발생하는 충돌의 감소가 스트레스 지수를 더 줄여준다. 그렇기 때문에, 첫번째 열과 마지막 열의 두 사람이 같은 그룹인 정답이 존재한다.

 

  위와 같은 증명으로, 우리는 첫번째 열과 마지막 열의 두 그룹을 고정할 수 있다. 해당 그룹 전체에서 발생하는 스트레스 지수에 대해서 생각하자. 해당 그룹의 경계에서는 최소 두 명의 스트레스 지수가 발생한다. 홀수인 경우에는 (가장 작은 스트레스 지수)*2 + (2번째로 작은 스트레스 지수)가 되고, 짝수인 경우에는 (1, 2번째로 작은 스트레스 지수의 합)이 된다.

 

  이제 해당 그룹이 아닌 내부에 존재하는 그룹에 대해서 생각하자.

  - 해당 그룹이 두 열 이상에 대해 두 행의 방을 모두 차지하고 있는 경우. (2×2 방을 차지하고 있는 경우)

    두 열을 기준으로 왼쪽과 오른쪽으로 분리하게 되고, 왼쪽 경계와 오른쪽 경계에 있는 사람들이 충돌하게 된다. 해당 경계에 두 사람만 존재하는 것이 가능하므로, 왼쪽 경계에 두 사람 오른쪽 경계에 두 사람이 존재하는 경우가 해당 그룹이 가질 수 있는 경계의 최솟값이다.

    * 해당 그룹의 크기가 홀수일 경우, 한쪽 경계에는 두 행을 모두 차지하고, 다른쪽 경계에는 한 행만 차지하는 경우가 된다. (사진에 있는 2번째 그룹에 해당된다.) 이 경우, 경계에 스트레스 지수가 낮은 사람을 배치하면 해당 그룹의 스트레스 지수는 (가장 작은 스트레스 지수)*2 + (2, 3, 4번째로 작은 스트레스 지수의 합)이 된다.

   * 해당 그룹의 크기가 짝수일 경우, 양쪽 경계에서 두 행을 모두 차지하는 것이 스트레스 지수의 최솟값이다. 이 경우 해당 그룹의 스트레스는 (1, 2, 3, 4번째로 작은 스트레스 지수의 합)이 된다.

   * 해당 그룹의 크기가 짝수이지만, 양쪽에 와야하는 사람 수가 홀수라서 양쪽 경계에서 두 행을 모두 차지하지 못하는 경우가 있을 수 있다. 이 경우 그룹의 스트레스의 지수는 (1, 2번째로 작은 스트레스 지수의 합)*2 + (3, 4번째로 작은 스트레스 지수의 합)이다.

경계에 존재하지 않는 그룹에 대한 그림

  - 해당 그룹이 한 열 이하에 대해 두 행의 방을 모두 차지하고 있는 경우.

    나머지 양 끝쪽에 존재하는 방에 대해서는, 충돌이 적어도 두 번 이상 일어나고, 칸 하나를 제외한 나머지 칸에 대해서도 충돌이 한 번 이상 일어나게 되기 때문에, 스트레스 지수의 합은 (1, 2번째로 작은 스트레스 지수의 합)*2 + (3, 4번째로 작은 스트레스 지수의 합) 이상이 되게 된다. 그러므로 해당 경우는 스트레스 지수가 위에 말한 경우보다 크게 된다.

 

  이제 위와 같은 상황이 가능한 배치가 존재하는지 확인 해 보자. 홀수 그룹의 방을 항상 두 개씩 인접해서 배치하는 전략을 사용하면, 위에서 말한 모든 그룹의 스트레스 크기를 최소화하는 배치를 할 수 있다. 이렇지 못하는 경우는, 홀수 크기의 그룹이 정확히 2개이며 왼쪽 끝과 오른쪽 끝에 가야하는 경우이고, 이 경우에는 양쪽에 와야 하는 사람 수가 홀수인 짝수 크기 그룹과 같은 형태로 배치할 수 있다.

가능한 배치 목록

  이 방법으로 오른쪽과 왼쪽 끝에 가야하는 그룹을 정하고, 나머지의 스트레스 지수를 더하는 방식을 사용하면 O(M3) 혹은 O(M2)의 시간복잡도가 발생하게 된다. 이제 이 과정을 최적화 하자.

 

  홀수 크기의 그룹이 정확히 2개이며, 왼쪽 끝과 오른쪽 끝에 가야하는 경우를 제외하고는, 각 그룹의 스트레스 크기는 최소화 되기 때문에 총 비용은 (두 그룹을 제외한 각 그룹의 가운데에서 스트레스 지수) + (두 그룹의 양쪽 끝에서 스트레스 지수)이며, 이를 다시 쓰면, (모든 그룹의 가운데에서 스트레스 지수) - (두 그룹이 양쪽 끝에 왔을 때 줄어드는 스트레스 지수의 양)이 된다. 각 그룹의 양쪽 끝에 왔을 때 줄어드는 스트레스 지수의 양은 고정되어있기 때문에, 이 중 최댓값 두 개를 골라서 전체 스트레스 지수에서 빼주는 방식을 사용하면 총 O(N+M)의 시간복잡도를 얻을 수 있다.

 

문제의 조건 중에, 각 그룹끼리 연결될 것과, 그룹의 크기가 5이상일 것이라는 조건이 있다. 왜 이런 조건이 존재하는지는 다음과 같은 예제로 알아볼 수 있을 것 같다.

 


5. 차이

  문제를 요약하면, 쿼리가 다음과 같이 두 종류 들어오고, 2번 종류 쿼리에 대해 답을 해야한다.

  - 1번: i, j, v가 주어진다. 이는 Xi-Xj=v라는 정보를 의미한다.

  - 2번: i, j가 주어진다. 지금까지 1번 쿼리로 들어온 정보들을 토대로 Xi-Xj의 값을 계산해야 한다. 여기서 계산이라고 함은 다음과 같은 과정으로만 재귀적으로 정의된다.

    * Xi-Xj=v나 Xj-Xi=-v가 1번 쿼리로 주어졌다면, Xi-Xj=v라고 계산할 수 있다.

    * Xi-Xj=v와 Xj-Xk=u라고 계산할 수 있으면, Xi-Xk=v+u라고 계산할 수 있다.

  위의 과정을 (유한번) 재귀적으로 사용해서, Xi-Xj의 값을 계산할 수 있는지와, 계산할 수 있다면 계산 결과가 유일한지를 판단하여라. (1번으로 주어진 정보에 모순이 존재할 수도 있다.)

 

  위와 같은 문제에서, Xi-Xj의 값을 계산할 수 있는지를 먼저 살펴보자. 계산에 관한 정보를 빼고 보면, 위의 설명은 i와 j가 연결되어있는지 아닌지에 관한 설명이다. 그렇기 때문에, 잘 알려진 Disjoint-set과 같은 알고리즘을 사용해서 문제를 해결할 수 있다.

  이제, 값을 계산해 보자. Disjoint-set알고리즘은, 트리에서 자신의 부모 노드를 가지고 있는 알고리즘이다. 그렇기 때문에, 자신의 부모 노드와 자신과의 차이를 누적하면, 자신과 루트 노드의 차이를 알 수 있다. Disjoint-set알고리즘 상의 트리에서 노드 i의 부모가 p이고 루트가 r인 경우에, Xr-Xp는 재귀적으로 구할 수 있고, Xp-Xi는 Disjoint-set에서 자기 부모를 저장하는 배열에 자기 부모와 자기 자신의 차이를 추가적으로 저장해서 차이를 구할 수 있다. 2번 쿼리가 들어왔을 때, i와 j가 같은 연결성분에 들어있지 않다면, 값을 계산할 수 없다. 하지만 같은 연결성분 안에 있다면, Xr-Xi와 Xr-Xj를 계산해서 (Xr-Xj)-(Xr-Xi)이 답이 된다.

  이제, 1번 쿼리를 생각해 보자. 하는 과정에서, 서로 다른 두 연결성분에 들어 있으면, 해당 두 연결성분을 Xi-Xj=v라는 관계로 추가로 연결 해 주면 된다. 하지만, 같은 연결성분에 들어있는 경우 계산 결과에 모순이 발생할 수 있다. 이 때는, Xi-Xj=v가 맞는지 2번 쿼리와 같은 방법으로 실제로 확인해 주고, 모순이 발생한 경우에는 해당 연결성분 전체에서 모순이 발생한다고 생각할 수 있다. i,j를 포함하는 Xi-Xj의 결과로 두 개 이상의 답이 존재하는 경우에는 같은 연결 성분에 속한 a, b에 대해서도 Xa-Xi + Xi-Xj + Xj-Xb = Xa-Xb의 결과가 두 개 이상이 된다. 그렇기 때문에 루트노드 쪽에 해당 연결성분에 모순이 발생하는지 아닌지를 체크해 주면 된다. 시간 복잡도는 Disjoint-set 알고리즘과 같은 O(Mα(M)) 이다.


  아래는 문제에 대한 코드이다.

 

1번

#include <cstdio>
#include <vector>
using namespace std;

int solve(const vector<int>& V)
{
    int N = (int)V.size();
    int ans = 0;
    for(int i=0; i<N; ++i)
        if(i + V[i] >= N) ++ans;

    return ans;
}

int main()
{
    int T; scanf("%d", &T);
    for(int t=1; t<=T; ++t)
    {
        int N; scanf("%d", &N);
        vector<int> V(N);
        for(int i=0; i<N; ++i) scanf("%d", &V[i]);

        printf("Case #%d\n%d\n", t, solve(V));
        fflush(stdout);
    }
}

2번

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string solve(int T, const string &B)
{
    int N = (int)B.length();
    string A(N, '1');
    for(int i=0; i+T<N; ++i)
    {
        if(B[i+T] == '0') A[i] = '0';
        if(B[i] == '0') A[i+T] = '0';
    }
    for(int i=0; i<N; ++i) if(A[i] == '1')
        if(i-T < 0 || (i-2*T >= 0 && A[i-2*T] == '1'))
            if(i+T >= N || (i+2*T < N && A[i+2*T] == '1'))
                A[i] = '0';
    return A;
}

int main()
{
    int TC; cin >> TC;
    for(int t=1; t<=TC; ++t)
    {
        int N, T; cin >> N >> T;
        string B; cin >> B;
        cout << "Case #" << t << '\n' << solve(T, B) << endl;
    }
}

3번

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

enum State {WHITE, BLACK, GRAY};

bool dfs(const vector<vector<int>>& conn, vector<State>& visit, int a)
{
    if(visit[a] == BLACK) return false;
    if(visit[a] == GRAY) return true;

    visit[a] = GRAY;
    for(int x: conn[a])
        if(dfs(conn, visit, x))
            return true;
    visit[a] = BLACK;

    return false;
}

bool hasCycle(const vector<vector<int>>& conn)
{
    vector<State> visit(conn.size(), WHITE);
    for(int i=0; i<(int)conn.size(); ++i)
        if(dfs(conn, visit, i))
            return true;
    return false;
}

string solve(int N, vector<pair<int, int> > O, vector<pair<int, int> > U)
{
    vector<vector<int> > conn(N);
    for(auto [u, v]: O) conn[u-1].push_back(v-1);

    string ans;
    for(auto [u, v]: U)
    {
        --u; --v;
        conn[u].push_back(v);
        if(hasCycle(conn))
        {
            conn[u].pop_back();
            conn[v].push_back(u);
            ans += '1';
        } else ans += '0';
    }
    return ans;
}

int main()
{
    int T; cin >> T;
    for(int t=1; t<=T; ++t)
    {
        int N, M, K; cin >> N >> M >> K;
        vector<pair<int, int> > O, U;
        for(int i=0; i<M; ++i)
        {
            int a, b; scanf("%d%d", &a, &b);
            O.emplace_back(a, b);
        }
        for(int i=0; i<K; ++i)
        {
            int a, b; scanf("%d%d", &a, &b);
            U.emplace_back(a, b);
        }
        cout << "Case #" << t << '\n' << solve(N, O, U) << endl;
    }
}

4번

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

long long solve(vector<vector<int>> V)
{
    vector<pair<int, int> > O; // stress, lift
    vector<tuple<int, int, int> > E; // stress, lift, special
    for(auto& x: V)
    {
        sort(x.begin(), x.end());
        if(x.size()%2 == 0)
        {
            int stress = x[0] + x[1] + x[2] + x[3];
            int lift = x[2] + x[3];
            int special = x[0]*2 + x[1]*2 + x[2] + x[3];
            E.emplace_back(stress, lift, special);
        }
        else
        {
            int stress = x[0]*2 + x[1] + x[2] + x[3];
            int lift = x[2] + x[3];
            O.emplace_back(stress, lift);
        }
    }

    long long ans = 0;

    if(O.size() != 2 || E.size() != 0) // handle normal case, careful not to include OE...EO
    {
        vector<int> lifts;
        for(auto [st, li, sp]: E) lifts.push_back(li);
        if(O.size() == 2) lifts.push_back(max(get<1>(O[0]),get<1>(O[1])));
        else for(auto [st, li]: O) lifts.push_back(li);
        sort(lifts.rbegin(), lifts.rend());

        for(auto [st, li, sp]: E) ans += st;
        for(auto [st, li]: O) ans += st;
        ans -= lifts[0] + lifts[1];
    }

    if(O.size() == 2) // special case
    {
        long long spc = 0;
        for(auto [st, li, sp]: E) spc += sp;
        for(auto [st, li]: O) spc += st-li;
        if(ans == 0) ans = spc;
        else ans = min(ans, spc);
    }

    return ans;
}

int main()
{
    int T; scanf("%d", &T);
    for(int t=1; t<=T; ++t)
    {
        int N, M; scanf("%d%d", &N, &M);
        vector<vector<int> >V(N);
        for(int i=0; i<N; ++i)
        {
            int s; scanf("%d", &s);
            V[i].resize(s);
            for(int j=0; j<s; ++j) scanf("%d", &V[i][j]);
        }
        printf("Case #%d\n%lld\n", t, solve(V));
    }
}

5번

#include <cstdio>
#include <vector>
using namespace std;

struct UFD
{
    vector<pair<int, long long> > ufd;
    explicit UFD(int N): ufd(N) {
        for(int i=0; i<N; ++i) ufd[i] = {i, 0LL};
    }
    bool isValid(int x)
    {
        return ufd[Find(x).first].second == 0LL;
    }
    void setInvalid(int x)
    {
        ufd[Find(x).first].second = -1LL;
    }
    pair<int, long long> Find(int a)
    {
        auto [p, u] = ufd[a]; // x[p]-x[a] = u;
        if(a == p) return {p, u};

        auto [r, v] = Find(p); // x[r]-x[p] = v;
        return ufd[a] = {r, u+v};
    }

    void Union(int a, int b, int t)
    {
        auto [pa, va] = Find(a); // x[pa]-x[a] = va
        auto [pb, vb] = Find(b); // x[pb]-x[b] = vb
        if(!isValid(a) || !isValid(b))
        {
            ufd[pb].first = pa; setInvalid(pa);
        }
        else if(pa == pb)
        {
            if(vb-va != t) setInvalid(pa);
        }
        else ufd[pb] = {pa, va-vb+t};
    }

    enum Cases {No, Yes, Any};
    pair<Cases, long long> diff(int a, int b)
    {
        auto [pa, va] = Find(a); // x[pa]-x[a] = va
        auto [pb, vb] = Find(b); // x[pb]-x[b] = vb
        if(pa != pb) return {Any, 0LL};
        else if(!isValid(a)) return {No, 0LL};
        else return {Yes, vb-va}; // vb-va = (x[p]-x[b])-(x[p]-x[a]) = x[a]-x[b]
    }
};

void solve()
{
    int N, Q; scanf("%d%d", &N, &Q);
    UFD ufd(N);
    while(Q--)
    {
        int c; scanf("%d", &c);
        if(c == 1)
        {
            int u, v, t; scanf("%d%d%d", &u, &v, &t);
            ufd.Union(u-1, v-1, t);
        }
        else
        {
            int u, v; scanf("%d%d", &u, &v);
            auto [res, val] = ufd.diff(u-1, v-1);
            if(res == ufd.No) puts("CF");
            else if(res == ufd.Any) puts("NC");
            else printf("%lld\n", val);
        }
    }
    return;
}

int main()
{
    int T; scanf("%d", &T);
    for(int i=1; i<=T; ++i)
    {
        printf("Case #%d\n", i);
        solve();
    }
}

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

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

패키지를 모두 https://bms.kyouko.moe 로 옮겼습니다.

 

BMS Archive는 준비가 많이 되면 업로드 하겠습니다.

 

=== 이전 게시글 ===

 

 

클라이언트 사이드에서 어떻게 하면 쓰기 편할지를 고민하다가 그냥 이미 잘 만들어져 있는 웹에다가 zip파일을 올리고, 여러 파일을 다운 받을 수 있는 패키지를 제공해주는게 가장 좋을거라는 생각을 했습니다. 그 이상의 무언가는 각자 알아서 만들것이고, 솔직히 필요 없을 거라고 생각했습니다.

 

https://bms.kyouko.moe/zips/ 에서 BMS파일을 웹 인터페이스로 받을 수 있습니다. 계속 업로드 중입니다.

 

Windows환경에서 사용불가능한 일부 파일의 이름을 전각문자로 변경했습니다. 또한, zip내부의 BMS파일들로 부터 이름을 자동으로 추정하는데, 잘 안 맞을 때가 있으니 알려주시기 바랍니다.

 

패키지는 https://blog.kyouko.moe/48 에 있습니다. Satellite와 Stella package를 빠른 시일내에 업데이트하겠습니다.

 

P. S.

 

 

서버가 위치해 있던 장소에서 금요일에 짐을 모두 월요일 까지 빼달라는 말을 들었고, 지금 너무 당황스럽네요...

 

현재 그 위치에 물리적인 서버가 2개 돌아가고 있는데, 이 서버 2개를 하나로 통합하는 작업을 한 후 임시로 집에서 서버를 돌려야 할 것 같습니다.

 

영향을 받는 서비스는 bms archive service 와 지인들 끼리 쓰던 음악을 공유하는 NAS가 있는데 인터넷 상황이 좋은 곳에서 안 좋은 곳으로 이동하는 것은 유감스러운 일이고 다시 서버를 원래 위치에 옮겨야 할 때도 다운타임이 꽤 많이 생길거라고 생각하기 때문에 좀 별로네요...

 

집에 있는 서버용으로 사 놓은 싼 데스크톱 하나가 있는데 부팅이 3달전쯤 되었던것 같은데 세팅하려고 보니까 안 되어서 이것도 골칫거리입니다.

 

지금 이 글을 쓰고 있는 위치는 현재 제 집인데 지금 서버가 있는 곳에 가야 하나 하고 생각 중입니다...

이제 BX를 trello 를 사용해서 관리합니다.

 

압축은 UTF-8로 되어 있으니, 이를 지원하는 어떤 프로그램으로 풀어도 상관 없습니다. (Bandizip 등)

 

패키지를 모두

 

https://bms.kyouko.moe/ 로 옮겼습니다. 아래 링크는 2020년 5월 이후에 삭제하겠습니다.

 

 

=== 이전 게시글 ===

 

Satellite(2020-03-01): https://bms.kyouko.moe/package/Satellite.html

 

통상 (17.7GB): https://bms.kyouko.moe/package/Normal.zip

 

델타 (9.4GB): https://bms.kyouko.moe/package/Delta.zip

 

Overjoy (구버전 신버전 포함, 6.1GB): https://bms.kyouko.moe/package/Overjoy.zip

 

발광 (22.4GB): https://bms.kyouko.moe/package/Insane.zip

 

Stella (2020-03-01): https://bms.kyouko.moe/package/Stella.html

 

통합 패키지: https://blog.kyouko.moe/48

 

UPD: 서버가 2020년 1월 4일 오전 10:00 부터 오후 3:00 까지 서버 이전 때문에 접속이 안 될 것입니다.

'프로그래밍 > 코딩' 카테고리의 다른 글

BMS Archive 개발 근황  (0) 2020.01.19
서버 근황  (0) 2019.12.07
[BX 개발기] 1. BMS 제목/아티스트 추출  (0) 2019.08.14
개인 홈페이지에 SSL 인증서를 달았습니다!  (0) 2018.07.27
비트연산과 집합  (0) 2017.11.25

https://github.com/ho94949/bms-archive

 

BMS archive service 의 약자는 BX로 정해졌습니다! archive 를 줄여서 arXiv로 부르는 https://arxiv.org 에서 따왔습니다.

 

일단 오늘 구현한 것은 BMS파일의 제목 및 작곡가 추출입니다. 유저단에서 돌릴 것은 아니므로 에러가 아예 안 날 필요는 없으나, 최대한 예외처리를 하는 방향으로 진행했습니다.

 

BMS 파일은 제목과 아티스트를 설정하게 되어있고, 대부분의 BMS에서는 제목에 난이도 이름까지 넣는 경우가 대부분입니다.

 

NO NIGHT MORE SOUL의 채보 목록

 여기서 우리는 노래 제목이 NO NIGHT MORE SOUL! 이라는 것을 알 수 있지만, 이것을 추출하는데 일련의 로직이 있어야 합니다.

 

제가 구현한 방법은 일단 IMPLICIT SUBTITLE을 모두 제거하는것 입니다. IMPLICIT SUBTITLE은 제목 안에 있는 [], (), -- 등으로 둘러싸인 다른 제목들을, 암시적으로 구분하는 것을 말하며 보통 난이도 등을 표시할 때 많이 쓰이기 때문에, 이것을 제외하면 노래 제목이 나오는 경우가 많습니다. 지금은 #SUBTITLE이란 명령이 있기는 하지만, 대부분 그냥 #TITLE 에 달아놓는것 같습니다.

 

가끔 곡 뒤에 이상한 SUBTITLE을 넣는 경우가 있고, 노래 제목 뒤에 이상한것을 붙이는 경우도 많기 때문에 제가 선택한 방법은 다음과 같습니다.

 

1. 모든 IMPLICIT SUBTITLE을 제거합니다.

 

2. 가장 짧은 제목을 찾습니다.

 

3. 이 제목이 모든 제목의 접두사인지 확인합니다.

 

이 방법을 통해서 대부분의 노래는 구분할 수 있습니다. 물론 너무나도 많은 예외들이 있습니다.

일본어와 영어를 섞어서 노래 제목을 정합니다
노래 제목에 X를 하나 더 넣습니다.
노래 제목을 오타를 칩니다.

 

차분으로 새로운 노래를 만드는 대회가 있습니다... 그래서 차분은 차분이지만 노래 제목이 다릅니다.

그래서 이런 노래들에는 임시로 N/A를 붙여놓고 수동으로 이름을 붙여주는 수 밖에 없을 것 같습니다.

 

뭔가 규칙들을 좀 더 정리해 나가면 좋을것 같다는 생각은 들긴 듭니다.

 

 

Merry Problem Solving 4일차 (12/24) 입니다!




ARC103F - Distance Sums







ARC103E - Tr/ee











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

SCPC 2021 2차 풀이  (0) 2021.08.07
SCPC 2021 1차 풀이  (0) 2021.07.17
Merry Problem Solving 3일차  (0) 2018.12.24
Merry Problem Solving 2일차  (0) 2018.12.24
Merry Problem Solving 1일차  (0) 2018.12.21

+ Recent posts