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

  UCPC는 개인이 진행하는 가장 큰 알고리즘 문제 풀이 대회 중에 가장 큰 프로그래밍 대회라고 해도 과언이 아닙니다. UCPC는 많은 알고리즘 문제 풀이를 하는 사람이 참여하고, 올해에는 오프라인으로 대회를 다시 바꾸면서 이것저것을 알아보고 있습니다.
  UCPC 운영을 맡으면서 한 일 중 하나는 UCPC 본선 진출 자격을 바꾸는 것이었습니다. 학교별 1팀 선발과 여성 및 비전공자 팀 추가 선발을 넣었습니다. 이렇게 바꾼 이유는 여럿이 있습니다.


  하나는 UCPC를 좀 더 교류의 장으로 만들고자 했습니다. 흔히 들어봤을 케빈 베이컨의 6단계 법칙은, 지구에 있는 사람들이 6단계 이내에서 아는 사람과 연결될 수 있다는, 어떻게 보면 세상이 매우 좁다는 법칙이었습니다. 생각보다 나는 내 주위 사람만 아는 것 같은데, 해외에 있는 사람을 알지도 못하는데, 어떻게 연결될 수 있을까요?
  실제로 사람은 자기 주위의 사람을 많이 알지만, 우연히 지금은 자기랑 떨어져 있지만 다른 먼 클러스터에 속한 사람을 많이 알고 있습니다. 얼핏 보면 관계가 없어 보이는 두 사람이 한두 사람을 거쳐 아는 이유에는 알고 있지만 멀리 떨어져 있는 사람의 역이 큽니다. UCPC도 이런역할을 하고 싶었고, 각 학교의 사람이 클러스터가 되어서 학교와 학교끼리 서로 교류하면 좋을 것이라는 생각을 했습니다.


  또한, 여성 및 비전공자 팀 추가 선발하는 이유는, 특정 집단이 알고리즘 문제 풀이에 접근하기 힘들었던 것을 해결하기 위해서도 있습니다. 저는 이렇게 벽이 있는 이유에는 구조적 문제점이 작용한다고 말합니다.
  다음의 예를 봅시다. 어떤 대회에 선발되는 국가대표가 대부분 1~4월에 태어났고, 5월 이후에 태어난 사람이 없다고 합시다. 이는 생일이 실력에 영향을 끼쳤다고 판단하는 것보다, 생일로 사람이 갈릴 수밖에 없는 구조적인 문제가 발생한다고 판단하는 것이 옳습니다. 이는 실제로 캐나다 하키 대표팀에서 일어난 것입니다. 캐나다 하키팀은 생년을 기준으로 리그를 나누는데, 5~6살 정도 되는 어린 나이에서는 출생 연도가 같아도 생일에 따라 큰 체격 차가 나게 됩니다. 이렇게 생일이 앞에 있는 사람이 뒤에 있는 사람보다 먼저 수상을 하고, 이것이 성장 후에 국가대표 선발에도 영향을 미칩니다. 이렇게 우리가 언뜻 보기에는 아무 상관이 없이 "임의"로 정한 것에도 구조적인 차별이 발생합니다.
  이런 구조적인 문제를 해결하려면 어떻게 해야 할까요? 하키팀의 문제로 돌아오면, 우리가 1~4월생만 집중하는 것이 아닌, 5-12월생에도 추가로 기회를 주면 됩니다. 이러면 하키팀에 참여할 수 있는 후보가 3배가 됩니다. 그러면 더 좋은 선수가 나올 가능성도 3배가 되겠죠. 이는 하키팀에 분명한 이득일 것입니다.

 

  프로그래밍에서의 여성도 예외는 아닙니다. 여성은 피임 도구가 발명되어 사용되기 전까지는 본인의 재생산 능력의 노예였습니다. 농업시대에서의 인구수는 곧 노동력을 뜻하니까요. 현재의 가치관은 많이 바뀌었습니다. 자연을 지배하고, 양적인 풍요를 추구하던 가치관에서, 조화를 꾀하고 질적인 행복을 추구하는 가치관으로 바뀌었습니다. 그런 사회에서도 아직 과거의 구조적인 문제는 남아 있고, 이 구조적인 문제는 적극적으로 해결되어야 합니다. 사실, 이는 여성 개개인에게서만 이득이 아니라 프로그래밍 분야 전체에서 이득입니다. 여성을 추가로 지원하게 되면 결과적으로 프로그래밍 분야를 이끌어 줄 사람이 2배가 되는 것입니다.

  비전공자의 경우도 마찬가지입니다. 왜냐하면 한국에서 전공은 선택하는 것이 아닌 경우도 많기 때문입니다. 성적에 따라 학교에 가는 경우가 많고, 대학의 이름을 위해서 과를 포기하는 경우도 많습니다. 프로그래밍 분야는 2016년 이후에 매우 인기가 많아졌으며, 프로그래밍에 관심이 있는 사람이 다른 성적 기준을 맞추지 못해 다른 과에 들어간 경우도 분명히 있습니다. 아쉬운 일이지만, 이 사람이 계속 프로그래밍을 즐길 수 있게 하고 싶었습니다.

 

  결국, 이런 본선 진출 자격 변경으로 인해서 이루고 싶은 것은 알고리즘 문제 풀이를 하는 사람의 결속력을 강화하며, 구조적 문제로 소외당하였던 사람도 참여시켜서 더 알고리즘 문제 풀이 커뮤니티를 풍요롭게 만드는 것입니다. 개인이 대회를 운영하기 때문에 이런 발걸음을 내디딜 수 있었다고 생각합니다. 이런 분위기가 확산하여, 프로그래밍 분야를 이끌어 갈 수 있는 사람이 더 많이 나왔으면 좋겠습니다.



 

'생각들' 카테고리의 다른 글

내 부끄러운 이야기  (0) 2022.04.12
물리적인 세상 [Draft]  (0) 2021.12.23
지식의 반감기, 진로와 달리기  (0) 2021.11.11
멘헤라 빙고 번역 후기  (0) 2021.06.17
About my private life  (0) 2021.04.10

  흔히 컨닝이라는 말로 많이 불리는 부정행위를 뜻하는 올바른 영어 단어는 치팅입니다. 좁은 의미에서는, 평가를 볼 때 응시자가 하는 불법적이거나 비도덕적인 행위를 말합니다. 넓은 의미의 치팅은 규칙에 반하는 행위를 하는 것 전체를 의미합니다. 치팅에는 여러 가지가 있습니다. 흔히 생각하는 컨닝페이퍼(cheat sheet)가 허용되지 않는 시험에서 몰래 보는 것이나 전자제품을 사용하는 것부터 시작해서 리포트나 과제를 인터넷이나 지인으로부터 전부 베끼는 것도 치팅에 해당합니다. 물론 보여준 사람도 치팅을 한 사람입니다.

  저는 치팅을 매우 싫어합니다. 도둑이 제 발 저린다는 옛말이 맞을지는 몰라도 동시에 저는 치팅을 매우 많이 해 온 사람이기도 합니다. 치팅을 싫어하는 모든 사람이 치팅을 많이 하지는 않았으니까 오해는 하지 않으셨으면 합니다. 동시에 저는 치팅에 대한 강경한 정책을 펼쳐야 한다고 계속 말하는 사람입니다. 제가 한 치팅은 남에게 과제를 보여준 적은 물론 있고 돈을 받고 남의 과제를 하기도 해 봤으며, 프로그래밍에 관련된 교육을 받을 때 소스 코드를 외부에서 가져온 것도, 평가를 볼 때도 사실상 cheat sheet을 사용한 것과 다름없는 행동을 한 적도 있습니다. 저의 부끄러운 이야기입니다.

  다행인 점은 이 내용 모두가 결국은 들켰다는 것입니다. 치팅은 어느 순간 들키게 됩니다. 남에게 과제를 보여주면 많은 부분이 보고 썼다는 느낌이 나게 됩니다. 이것이 쌓이면 여러 정황 증거가 쌓입니다. 소스코드를 다른 곳에서 베꼈으면 치팅이고 전부 잡아낼 수 있습니다. 소스코드 순서를 바꾸거나 주석을 추가하거나 하는 등의 행위도 마찬가지입니다. 저는 한 온라인 대회가 끝나고 나서 치팅을 잡기 위해서만 거의 30시간 정도를 사용했습니다. 이런 치팅을 많이 해 본 적이 있는 사람이 잡는 치팅을 피할 수 있을까요? 물론 들키지 않을 수도 있습니다. 수법이 교묘하면 교묘할수록 찾아내기 힘든 것은 사실이니까요. 하지만 이런 치팅은 습관화가 되고 여러 번 하게 되며 반복하는 동안 실수를 하게 됩니다. 그래서 발각되면 이전의 치팅에 대해서도 처벌을 받을 것입니다. 사실, 이전에 했던 행위에 대해서는 물증이 없어서 치팅을 처벌하지 않고 있던 것이지 한 번 발각되면 이전의 치팅에 대해서도 같이 죄를 물을 수 있습니다.

  제가 치팅에 대해 강경한 정책을 펼쳐야 한다고 말하는 이유는 이러한 치팅은 습관화가 되고 다른 사람의 의욕을 갉아먹기 때문입니다. 치팅은 고평가라는 보상을 얻는 매우 쉬운 수단입니다. 그렇기 때문에 뇌는 적은 노력으로 많은 보상을 얻을 수 있는 치팅을 계속하게 되고 만성화됩니다. 나중에 가면 그 보상에 대해서도 무뎌지게 되는데 이러면 모든 일에 대해서 노력하지 않으려고 할 수도 있습니다. 이것은 치팅한 사람을 볼 때도 마찬가지입니다. 본인은 노력했는데 타인은 적은 노력으로, 그것도 부당한 방법으로 고평가를 받은 것은 본인의 노력에 대한 가치를 저평가하기 쉽고 비슷하게 치팅을 시작하기 쉽게 됩니다. 이것이 반복되면 평가와 학습을 한다는 본래의 목적은 변질하고 사라져버립니다.

  치팅은 역사적으로도 오래되었고 시험이 존재했을 때부터 함께했습니다. 그리고 사실 많은 사람이 시도해 봤을 것으로 생각합니다. 부끄러운 일이지만 누구나가 거쳐 갈 수 있는 길이기도 합니다. 사람이 고평가를 많아야 하는 이유는 많으며 여러모로 중요한 일이기도 합니다. 평가가 중요한 만큼 다른 사람은 고평가에 상응하는 기대를 하고 오히려 이 기대는 치팅보다 더더욱 끊기 힘든 것일 수도 있습니다. 이렇게 상습적으로 치팅을 하는 것의 결말은 당장 타인의 기대를 충족하지 못하는 것보다 비극적입니다. 치팅을 하고 있었다면 다시 올바른 길로 돌아왔으면 합니다. 열심히 공부하고 열심히 노력해서 평가받는 것이요. 물론 이전과 같은 노력을 하는 방법을 까먹었을 수도 있습니다. 하지만 다시 시작하면 됩니다. 지금이라도 올바른 길을 걷는 것이 본인을 더더욱 잘 알고, 본인이 보람과 성취감을 느끼는 가장 좋은 길이라고 생각합니다.

'생각들' 카테고리의 다른 글

UCPC의 본선 진출 자격 변경에 대해  (0) 2022.05.12
물리적인 세상 [Draft]  (0) 2021.12.23
지식의 반감기, 진로와 달리기  (0) 2021.11.11
멘헤라 빙고 번역 후기  (0) 2021.06.17
About my private life  (0) 2021.04.10

  저는 오픈리 퀴어입니다. 제가 퀴어라는 걸 굳이 밝힐 필요가 없을 때는 밝히지 않지만, 굳이 숨기지도 않으며, 많은 표현을 하고 다닙니다. 유난히 페미닌한 옷을 즐겨 입습니다. 이렇게 제가 오픈리 퀴어가 될 수 있는 이유는 제가 능력적으로 큰 성공을 거두었기 때문이라고 생각합니다.

  한국에는 성차별적인 정서가 보이는 형태든, 사람의 무의식적인 편견 속에서든 남아 있습니다. 그리고 그런 편견을 "깨부숴줬다"라고 하는 인터넷 커뮤니티 글은 대부분 "여성이라서 사람들이 나를 무시했는데, 좋은 능력을 보여주니까 아무 말 못 하더라"였습니다. 물론 저는 이런 일화를 긍정적으로만 바라보지는 않습니다. 하나는 그들은 다시 좋은 능력을 보여주지 못하는 여성을 무시할 것이고, 다른 하나는 한국에서 능력주의와 엘리트주의가 성차별보다 더 심하다는 것을 나타내주기도 하기 때문입니다. 이 능력 차이가 많이 나면 많이 날수록 그 사람의 개성은 "이상한 것"에서 "그 사람의 특징"이 되고, 저에게 있어서는 사람들이 이상하다고 느끼는 퀴어리티가 그렇습니다. 저는 이걸 적극적으로 활용합니다. 저의 능력은 저의 퀴어리티를 마음껏 표현할 수 있게 해 주는 도구이고, 그래도 특색으로 인정하는 게 사회의 시선이고, 퀴어리티를 사회에게 익숙한 것으로 끌어올리는 것이 목적입니다.

  저는 한동안 퀴어리티를 가진 사람들의 커뮤니티에서 많은 교류를 했습니다. "신드롬"이라는 닉네임을 사용했고, 지금도 저를 닉네임인 신드롬 님 이라고 불러주시는 분도 종종 있습니다. 하지만 앞으로는 교류가 적어질 것 같습니다. 가장 큰 이유는, 퀴어리티가 제 삶의 일부이고, 어떤 두 사람을 퀴어라는 연결로 묶기에 퀴어는 매우 느슨한 연결이기 때문입니다. 같은 지향성과 정체성을 가지고 고민한다면 어느 정도는 많이 연결될 것도 같지만요. 제가 어떤 사람과 서로 퀴어라는 공통점만 있을 때 친해지기란 쉽지 않다는 판단이었습니다.

  제가 해당 커뮤니티에 들어가지 않는다고 퀴어가 아니게 될 것도 아니며, 퀴어를 향한 지원을 멈추지도 않을 것이고, 운동을 멈추지도 않을 것입니다. 그중 하나가 제가 오픈리 퀴어라는 점입니다. 하지만, 이게 나의 삶의 전부가 되기를 원치는 않습니다. 저는 하고 싶은 게 많기 때문입니다. 퀴어리티는 저의 "특색" 중의 하나입니다.

  어떤 비슷한 두 사람이 있는데 그중 한 명이 퀴어인 것을 알면, 아마 그걸 계기로 더 빠르게 친해질 확률이 높을 것 같습니다. 그런데 나머지 한 명이 맥주의 일종인 스타우트를 좋아한다는 사실을 알면... 저는 그 둘과 비슷한 속도로 친해질 것 같습니다. 저에게 있어서 제가 퀴어라는 것이 삶에서 차지하는 비율은, 제가 스타우트를 좋아한다는 것이 삶에서 차지하는 비율과 비슷한 것 같습니다. 제가 스타우트를 좋아하는 것이 저의 특색이듯이, 제가 퀴어라는 것이 저의 특색입니다. 그런 인간과 인간 간의 감정과 마실 것을 어떻게 비교하냐고 할 사람도 있을 텐데, 원래 그런 것은 사람마다 다른 법이니까요. 저는 유럽에 맥주를 마시면서 여행을 떠나고 싶다고 생각한 적은 있지만, 저의 퀴어리티 때문에 여행을 떠나고 싶다고 생각한 적은 없습니다.

  제가 스타우트와 관련해서 양조장에 기부하지 않더라도, 제가 퀴어를 향한 단체에 기부하고, 퀴어리티를 가진 사람에게 지원하고 운동을 할 것이라는 이유는, 사람들은 스타우트를 좋아한다는 사실에는 말을 얹지 않지만, 퀴어라는 사실에는 말을 얹기 때문입니다. 저는 이게 단지 싫을 뿐입니다. 그래서 계속 지원하고, 운동하고, 투쟁할 것입니다. 저는 저의 삶의 그 어떤 일부라도 부정당하고 싶지 않으니까요. 그리고 남이 그런 경험을 하는 것도 원치 않으니까요.

'생각들 > GD' 카테고리의 다른 글

2021-12-21  (0) 2021.12.23
2021-08-17  (0) 2021.08.18
#2  (0) 2021.08.11
2021-08-11  (0) 2021.08.11
2021-07-19  (0) 2021.07.20

   어제 20211222일에 저는 워크숍을 하나 진행했습니다. 해당 모임은 어떤 사기업에서 진행하고 있는 모임이고, 참가할 기회가 있을 때마다 참가했습니다. 다양한 분야의 사람들이 모여서, 각자 자기가 하고 있는 것들에 대해 발표하고, 친목을 다지는 행사였고, 해당 멤버십 행사에서 모인 사람들과 좋은 식당에서 밥도 먹고, 이러저러 얘기도 했던 것이 기억납니다.

   이번에 해당 워크숍은 "개더타운"이라는 서비스에서 진행을 했습니다. 관리자가 맵(여기서는 해당 사기업의 회사 건물이었습니다)을 구성해 놓으면, 방향키로 이동해서 해당 맵을 탐험할 수 있고, 그 중에서 가까이 위치한 사람과는 화상 채팅이 열리는 방식의 시스템이었습니다. 흔히 "메타버스"라고도 불리는 가상 세계의 서비스 중 하나입니다.

   사실, 조금 놀라웠습니다. 오프라인에서 진행하고 있는 여러 행사들을 온라인으로 되게 잘 구현하려고 노력한 흔적들이 많이 보였기 때문입니다. 실제로 많은 사람이 컨퍼런스를 진행하고 식사를 하면 실제 대화나 사람간의 상호작용은 매우 소규모에서 이루어지기 때문입니다. 이번 워크숍에는 약 16명 정도가 참여했는데, 16명이 모인다고 16명이 모두 서로 대화를 원활하게 할 수 있는 것은 아닙니다. 워크3개의 팀으로 나누어서 진행했고, 제 팀에는 6명 정도가 있었는데, 이게 한 사람이 상호작용 할 수 있는 한계라고 생각합니다. 또한, 내가 가만히 있는 게 아니라 어쨌든 키보드를 사용하고 이동함으로써, 내가 장소와도 상호작용한다는 것을 알려주고, 이런 행동을 할 수 있다는 점이 사람의 집중력을 잘 유지시켜준다고 생각했습니다. 가령이면 OX퀴즈를 할 때, OX버튼을 누르는 것이 아닌, 사람들이 실제로 우르르 몰려다니고, 움직이는 것을 확인할 수 있는 것은 생각보다 현실감 있게 다가왔습니다. 이런 사항들을 생각보다 잘 반영한 프로그램이 아닌가하고 생각했습니다.

   하지만, 현실에서 얼굴을 맞대는 것과는 역시 달랐습니다. 몇몇은 문제가 아니라고 생각합니다. 여러 연결 문제로 진행에 딜레이가 생겼지만, 이것은 현실에서도 장비가 제대로 동작하지 않으면 점검을 해야 하는 것은 어느 곳이나 다 마찬가지입니다. 제가 좀 더 느끼는 것은, 해당 모임에 대해 느끼는 피로감이었습니다. 사람은 대화를 할 때, 표정의 매우 미묘한 부분까지 관찰하는데, 반응의 약간의 딜레이에도 사람은 민감하게 반응을 하고 그래서 서로가 서로의 맥락을 공유하는 데에 좀 더 피로감을 느낀 면이 있는 것 같습니다. , 화자에게 집중을 한다는 신호(백채널링)의 전달이 느리거나 줄어들기 때문에, 계속 화자와 청자 간의 커뮤니케이션에 서로가 집중하고 있는지 확인을 해야 하고, 그런 커뮤니케이션 자체보다 부수적인 부분에 대해서 커뮤니케이션에 추가적인 코스트가 든다고 생각합니다. 물론, 먼 거리를 이동해야하는 수고가 줄어든 것은 사실입니다. 어느 부분은 장점, 어느 부분은 단점을 잘 골라서 택해야 한다고 생각합니다.

   이런 대형 워크숍 같은 경우에는 장점과 단점을 어느 부분 저울질 할 수 있다고 생각합니다. 정보 전달이 좀 더 목적인 경우가 많고, 이동하기 힘든 사람들이 대부분인 경우가 많으니까요. 하지만, 사람들이 소규모로 친목을 하기 위해서 모이는 곳이라면 장점과 단점의 저울질이 힘들다고 생각하고, 물리적인 세계에서 만나는 것의 이점이 많다고 생각합니다.

  저는 휴학을 하고 있을 때도 동아리에 어떤 신입들이 들어오는지에 관심이 많았고, 그리고 사실 지금도 관심이 많습니다. 하지만 전혀 확인을 하지 못하고 있는데, 그 이유는 다름이 아니라 동아리방에 신입생이 없기 때문입니다. 학교 기숙사를 굳이 들어 올 필요가 없고, 방역 수칙 때문에 동아리방에서 모이기도 힘듭니다. 사실 온라인에서 회의가 있기도 하고, 마음만 먹으면 서로 얘기할 수 있는 기회는 많습니다. 하지만, 동아리방에서 있는 사람에게 그냥 얘기를 하는 것과 온라인에서 만날 약속을 따로 잡아 이야기 하는 것은 다른 이야기 입니다. 그래서 개인적으로는 기존 동아리원과 새 동아리원 사이의 결속력이 약해지고 있다는 생각을 했습니다.

   혹은 온라인에서 아예 할 수 없는 행동들도 있습니다. 제가 생각보다 중요하게 여기는 사람과 사람 사이의 포옹, 저의 큰 취미중인 하나였던 위스키와 칵테일을 마시는 것과, 파인 다이닝을 찾아다니는 것은 온라인에서는 아예 할 수 없습니다. 저의 생활 반경을 수도권에서 대전으로 옮기면서 아쉬운 것 중 하나라고 생각합니다. 대전에서의 새로운 인간관계를 맺어야 하는데, 저는 학교 안에서는 신입생만큼 새로운 도전이 허용되는 나이도 아니고, 아직도 좋은 요리와 좋은 술을 찾으러 갈 때는 서울에 있는 식당과 바를 찾아갑니다. 이것은 한국의 수도권 중심주의도 있다고 생각하지만, 그냥 생활 반경을 옮기면서 겪어야 하는 필연적인 변화 중에 하나도 있습니다.

   어쨌든 우리는 물리적인 세상 안에서 살아갑니다. 디지털이 세상을 좀 더 가깝게 만들어 주었고, 물리적인 세상의 영향력을 줄인다고는 했지만, 사실 세상을 가깝게 만들어 주기보다는 세상을 넓게 만들고 새로운 연결을 만들어줬다고 하는 게 맞는 것 같습니다. 디지털이 세상을 가까이 만들어 준만큼, 물리적인 세상은 멀어졌다고 느낍니다. 사실 우리는 이런 디지털과 물리적인 세상을 적당히 선택하고 조율할 수 있는 계기가 만들어진 걸지도 모르겠습니다. 어떤 것은 디지털로 해도 상관이 없거나 혹은 더 좋고, 어떤 것은 디지털이 해결해 줄 수 없는지.

 

  사실, 저는 물리적인 세상에 큰 원망을 가지고 살아갑니다. 하지만 어쩌겠나요? 주어진 것은 주어진 것이고, 계속 시도해 보는 것만이 답이라고 생각합니다. 제가 개척할 수 있는 것은 개척해 보려고 노력해야 할 것 같습니다. 오늘도 서울을 갈 준비를 해야겠습니다. 이제 씻고, 옷도 잘 챙겨 입고 화장도 하고 나가야죠.

'생각들' 카테고리의 다른 글

UCPC의 본선 진출 자격 변경에 대해  (0) 2022.05.12
내 부끄러운 이야기  (0) 2022.04.12
지식의 반감기, 진로와 달리기  (0) 2021.11.11
멘헤라 빙고 번역 후기  (0) 2021.06.17
About my private life  (0) 2021.04.10

피검사를 4달 정도만에 진행했습니다. 에스트라디올-데포를 맞고 1주일 후에 피검사를 진행했고, 프롤락틴 수치가 28ng/mL, 에스트라디올 수치가 342pg/mL, 테스토스테론 수치가 0.28ng/mL이 나왔습니다. 안티안드로겐을 사용하지 않았는데 테스토스테론 수치가 매우 낮은게 이례적이라고 합니다. 저는 샘플이 바뀌지 않았나 의심할 정도였습니다.

 

피검사를 진행한 이유는 에스트라디올 변화에서 나타나는 감정변화입니다. 에스트라디올 농도가 낮아지는 피크에서 감정변화가 생기고(여러 기작이 있다고 합니다), 그래서 에스트라디올 데포를 맞는 주기를 줄여보자는 생각에서 피검사를 요청을 했습니다. 에스트라디올 데포는 그대로 비슷한 주기로 맞되, 프로기노바 경구투여를 하는 방법을 바꿀 생각입니다.

 

 

'생각들 > GD' 카테고리의 다른 글

나에게 퀴어란  (0) 2021.12.26
2021-08-17  (0) 2021.08.18
#2  (0) 2021.08.11
2021-08-11  (0) 2021.08.11
2021-07-19  (0) 2021.07.20

프로그래밍을 하고 싶지 않다. 이유는 여럿 있는데, 가장 큰 것은 매번 바뀌는 기술적인 사항을 찾아가는게 매우 힘들기 때문이다. 6개월정도 지난 repo에 npm i를 타이핑하고 본 2000여개의 보안 취약점을 보고, 지친다는 것을 가장 크게 느낀 것 같다.

 

학문적인 지식에는 반감기가 있다는 주장이 있다. 학문에서 활발하게 사용되는 지식 중 절반이, 새로운 발견으로 대체되거나 틀린것으로 밝혀지는 시간이다. 물론 엄밀하게 정의되어 있지는 않는 개념이지만, 프로그래밍은 2.5년에서 7년정도라고 한다. [1] 필드에서 어떤지에 대해서는 찾은 글이 없다. 프로그래밍과 컴퓨터공학을 하다보면, 어딘가로 계속 달려야 한다. 과거에 내가 배웠던 것은 현재에 와서는 낡거나 틀린 지식이 된다. 그래서 나는 이론전산학을 하는게 좋다고 생각했다. 왜 이론전산학을 하는게 좋다고 생각하냐면, 적어도 반감기가 2.5년까지 짧지는 않을 것이니까. 그리고, 나는 프로그래밍을 잘 하니까. 이 생각은 점점 바뀌어서 이산수학을 하고 싶다는 생각까지 바뀌었다. 물론, Tutte Graph 보다는 node.js가 내가 살아가고 있는 세상을 더 많이 바꿔놓을 수 있겠지만, 어쨌든 내가 하고 싶은 것을 해야하니까. 사실 수학의 반감기도 그렇게 길지는 않은 것 같다. 9.17년 정도라고 한다. [2] 물론, 내가 "올바르다"고 받아들였던 사실이 "틀린" 사실이 되지는 않겠지만.

 

내가 지금 공부하고 싶은 공부는 언어학이나 심리학이다. 나는 그렇게 학점이 좋지 않기 때문에 의전원에 갈 수 없다. 내가 현실적으로 언어학을 지금 공부할 수 있는 방법은, 자연어 처리 관련 전산 대학원에 들어가는 것이고, 심리학을 공부할 수 있는 방법은 지금 학교에서 바이오 및 뇌 공학과 복수전공을 해서 심리학과 관련된 대학원을 들어가는 것이다. 그렇지만, 이런 선택을 할 것 같지는 않다. 나는 수학과 프로그래밍을 꽤 잘 하기 때문에, 내 장점을 충분히 이용하는게 맞는 전략이기 때문이다. 만약에 내가 수학과 프로그래밍을 그렇게까지 잘 하지 않았다면, 집에 좀 더 빌붙어서 내가 맞는 전공을 찾아가겠다고 말했을까? 잘 모르겠다. 사실은 심리학의 반감기도 그렇게 길지는 않다. 3.3년에서 19년정도라고 한다. [2] 내가 심리학과 관련된 공부를 해도 위의 문제들을 만날 것이다. 심지어 이 분야는 진짜 과거에 많은 사실이라고 생각했던 것들이 거짓으로 밝혀지는 곳이다. 생각 해 보면, 세상은 빨리 바뀌기 때문에, 세상을 바꿀 수 있는 위치에 있는 학문을 필연적으로 반감기가 짧을 수 밖에 없는 것 같다. 내가 원하는 두 가지를 모두 달성하는 일은, 마치 유니콘을 쫓는 것과 같지 않을까?

 

사실 난 이런 고민들을, 더 이상 이 분야에서 달릴 자신이 없다는 선언이고, 박수 받을 때 떠나고 싶을 뿐이며, 그냥 내 자리를 유지할 수 없을 것 같기 때문에 도망가는 도피라고 생각한다. 사실 지금도 도망치는 것 보다는 갓길을 선택하는거에 가깝지만.

 

나는 지금도 계속 달리고 있고, 다른 길도 이러저러 확인하고 있다. 다른 사람은 조금 쉬어도 좋다고 하지만, 어릴 때부터 계속 움직이도록 훈련 받은 나는 달리는 것이 나의 삶이기 때문에 달리지 않는 나의 삶이 예상되지 않아서 불안하다. 나의 삶은 컨베이어 벨트여서, 달리지 않는 것은 곧 뒤쳐진다는 의미였으니까. 그리고, 뒤쳐지면 영원히 따라잡을 수 없을 것 같고, 미래의 내가 언젠가 해야 하는 일이라고 생각하니까. 나는 갓길이 되었든, 험난한 길이 되었든 어딘가로 계속 달려야겠다. 이렇게 고민해도 선택은 갈림길에 선 내가 하지 않을까? 어떤 선택을 해도 달리면 된 것이다.

 

출처

[1] https://spectrum.ieee.org/an-engineering-career-only-a-young-persons-game

[2] https://www.universetoday.com/97806/book-review-the-half-life-of-facts-why-everything-we-know-has-an-expiration-date/

[3] https://psycnet.apa.org/record/2012-16074-001

 

 

 

 

 

 

 

 

??

사실은 더 이상 달리고 싶지 않은데, 달리지 않아도 괜찮다고 느낄만한 심리적으로 안정된 기반이 존재하지 않는다. 나는 달리지 않는 나에게 나는 가치를 찾을 수 없어서 오늘도 달리고, 이는 다시 나에게 과부하로 다가와서 나를 해친다. 이런 연결고리가 삶이라면 더 이상 지속하고 싶지 않다. 그래서 연결고리를 끊을 수단을 찾고 있지만, 찾지 못한 것 같다. 그냥 통째로 내던지고 싶다.

 

'생각들' 카테고리의 다른 글

내 부끄러운 이야기  (0) 2022.04.12
물리적인 세상 [Draft]  (0) 2021.12.23
멘헤라 빙고 번역 후기  (0) 2021.06.17
About my private life  (0) 2021.04.10
solved.ac에 관한 주저리주저리  (0) 2020.11.27

  2020년 8월 13일에 혈액결과가 나와서, 전화상담을 했습니다. 직접 방문을 해서 결과를 들을 수 있고, 전화로 상담을 할 수도 있다고 했기 때문에, 저는 전화로 상담을 했습니다. 단, 전화로 상담을 하면 3,500원의 진료비가 나온다고 했습니다.

  2020년 8월 17일에 직접 방문해서 호르몬주사를 맞았습니다. 혈액검사 결과를 얘기 하고, 앞으로 어떤 식으로 건강관리를 해야 한다 같은 점을 얘기 한 이후에 데포주사를 맞았습니다. 근육이 많은 팔과 엉덩이중 선택해서 맞을 수 있었습니다. 용량이 크거나 아프지는 않았으며, 비용은 상담과 합해서 14,500원이 나왔습니다. 나중에 익숙해지면 자가주사를 하는 형태로 처방하기도 한다고 합니다.

 

 

'생각들 > GD' 카테고리의 다른 글

나에게 퀴어란  (0) 2021.12.26
2021-12-21  (0) 2021.12.23
#2  (0) 2021.08.11
2021-08-11  (0) 2021.08.11
2021-07-19  (0) 2021.07.20

+ Recent posts