2025 NYPC 본선 풀이

작성일 | In

서론

문제 지문과 공식 풀이는 NYPC 아카이브에서 확인할 수 있습니다. 채점은 BIKO에서 받을 수 있습니다.

제가 생각하는 난이도(solved.ac 기준)는 다음과 같습니다. 1214 부문 3번(돌 무더기)과 5번(마방진 만들기) 문제는 사람마다 편차가 클 것 같습니다. 1519 5번(편집 거리) 문제 사실상 두 가지 문제가 합쳐진 문제이므로 따로 구분해서 매겼습니다.

  • 1214 부문
    • [S?] 기호
    • [G5] Connexion
    • [P?] 돌 무더기
    • [P3] 개미
    • [P?] 마방진 만들기
  • 1519 부문
    • [G5] Connexion
    • [P3] 개미
    • [D4] 물 뿌리기
    • [D3] 거래
    • [D2] 편집 거리 - subtask 1,2,4,5
    • [R5] 편집 거리 - subtask 1,2,3

1214 2번 = 1519 1번, 1214 4번 = 1519 2번입니다.

PC 화면으로 보는 분들은 우측 사이드바를 이용해 원하는 문제로 빠르게 이동할 수 있습니다.

1214 1번. 기호

문자열을 앞에서부터 차례대로 보면서, 뺄셈 기호의 수가 덧셈 기호의 수보다 커질 때마다 뺄셈 기호 하나를 덧셈 기호로 바꾸는 전략이 성립합니다.

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, X=0, R=0; string S; cin >> N >> S;
    for(auto c : S){
        X += c == '+' ? 1 : -1;
        if(X < 0) R++, X += 2;
    }
    cout << R;
}

1214 2번 / 1519 1번. Connexion

그래프를 적절히 구성한 뒤, BFS/DFS 등을 이용해 컴포넌트의 크기를 구하면 됩니다.

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;
constexpr int N = 72;
string S = "RGBY";
int f(int i, int j, int k){ return i * 12 + j * 2 + k; }
int sq(int x){ return x * x; }

int A[N], B[N], C[N];
vector<int> G[N];
void AddEdge(int u, int v){ G[u].push_back(v); G[v].push_back(u); }

int DFS(int v, int *arr, int chk){
    int res = 1; C[v] = chk;
    for(auto i : G[v]) if(arr[v] == arr[i] && C[i] != chk) res += DFS(i, arr, chk);
    return res;
}

void Solve(){
    memset(A, -1, sizeof A);
    memset(B, -1, sizeof B);
    memset(C, 0, sizeof C);

    int n; cin >> n;
    for(int i=1; i<=n; i++){
        string a, b; cin >> a >> b;
        int pos = f(a[0]-'a', a[1]-'1', a[2]=='+');
        A[pos] = b[1] - '1'; B[pos] = S.find(b[0]);
    }

    int x = 0, y = 0;
    for(int i=0; i<72; i++) if(A[i] != -1 && C[i] != 1) x += sq(DFS(i, A, 1));
    for(int i=0; i<72; i++) if(B[i] != -1 && C[i] != 2) y += sq(DFS(i, B, 2));
    cout << x << " " << y << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int i=0; i<6; i++) for(int j=0; j<6; j++) AddEdge(f(i,j,0), f(i,j,1));
    for(int i=1; i<6; i++) for(int j=0; j<6; j++) AddEdge(f(i,j,0), f(i-1,j,1));
    for(int i=0; i<6; i++) for(int j=1; j<6; j++) AddEdge(f(i,j,0), f(i,j-1,1));
    for(int tc=1; tc<=TC; tc++) Solve();
}

1214 3번. 돌 무더기

가장 먼저 떠오르는 풀이는 각 무더기에 있는 돌의 개수를 인자로 하는 동적 계획법입니다. 아래와 같이 구현하면 $N = \max(a,b,c)$일 때 상태 공간의 크기가 $O(N^3)$이고, 각 상태의 답을 $O(N)$에 구하는 $O(N^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
#include <bits/stdc++.h>
using namespace std;

int D[111][111][111];

int f(array<int,3> a){
    sort(a.begin(), a.end());
    int &res = D[a[0]][a[1]][a[2]];
    if(res != -1) return res;
    if(a[2] == 0) return res = 0;

    res = 0;
    for(int take=0; take<3; take++){
        for(int split=0; split<3; split++){
            if(take == split) continue;
            for(int i=1; i<a[split]; i++){
                auto nxt = a;
                nxt[take] = i; nxt[split] -= i;
                if(!f(nxt)) res = 1;
            }
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    memset(D, -1, sizeof D);
    for(int tc=1; tc<=TC; tc++){
        int a, b, c; cin >> a >> b >> c;
        cout << (f({a, b, c}) ? "first" : "second") << "\n";
    }
}

위 풀이를 이용해 작은 범위에서 답을 구한 뒤, $D(a, b, c) = 0$인 $(a, b, c)$ 튜플을 모두 출력해놓고 열심히 쳐다보면 규칙을 찾을 수 있습니다. $g(x)$를 $x$에 2가 곱해진 횟수라고 정의합시다. $D(a, b, c) = 0$일 필요충분조건은 $g(a) = g(b) = g(c)$임을 관찰하면 문제를 해결할 수 있습니다.

$g(a) = g(b) = g(c)$인 위치가 패배하는 위치라는 것은 다음과 같이 증명할 수 있습니다.

돌이 $x$개 있는 더미가 있고, $g(x) = t$라고 합시다. $0 \le s < t$인 모든 정수 $s$에 대해, $g(y) = g(z) = s$가 성립하도록 크기가 $x$인 더미를 크기가 $y=2^s$인 더미와 $z=x-2^s$인 더미인 나눌 수 있습니다. 반대로, $s \ge t$이면 $g(y) = g(z) = s$가 되도록 더미를 나눌 수 없습니다.

즉, 세 더미의 $g(a) = g(b) = g(c)$라면 플레이어가 어떤 행동을 하더라도 $\min(g(a), g(b), g(c))$가 감소할 수밖에 없습니다. 반대로, 세 더미의 $g$값 중 하나라도 다르다면, 플레이어는 항상 세 더미의 $g$값이 같아지도록 만들 수 있습니다. 또한, 더이상 행동을 할 수 없는 상태($a,b,c \le 1$)는 $g(a) = g(b) = g(c) = 0$입니다.

따라서 세 더미의 $g$값이 같은 상태로 게임을 시작한다면, 후공이 매번 세 더미의 $g$값이 같은 상태를 되돌려주므로 선공이 질 수밖에 없습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++){
        ll a, b, c; cin >> a >> b >> c;
        a = __builtin_ctzll(a);
        b = __builtin_ctzll(b);
        c = __builtin_ctzll(c);
        cout << (a == b && b == c ? "second" : "first") << "\n";
    }
}

1214 4번 / 1519 2번. 개미

$v$를 루트로 하는 서브트리의 각 정점에 개미를 정확히 한 마리씩 배치하고 남은 개미의 수를 $S[v]$라고 정의합시다. 이는 서브트리에 속한 정점들의 $A[i] - 1$ 값을 더하면 구할 수 있고, 개미가 부족하면 $S[v]$는 음수가 됩니다.

각 간선을 따라 이동하는 개미의 수에 집중합시다. 편의상 $v$의 부모 정점을 $p(v)$라고 부를 것입니다.

만약 $S = N$이라면 모든 정점에 정확히 한 마리의 개미가 배정되어야 합니다. 따라서 $S[v] > 0$인 서브트리에서는 $v$에서 $p(v)$로 $S[v]$마리의 개미가 이동해야 합니다. 반대로, $S[v] < 0$인 서브트리에서는 $p(v)$에서 $v$로 $-S[v]$마리의 개미가 이동해야 합니다. 따라서 $S = N$이면 정답은 $\sum \vert S[v] \vert$입니다.

$S = N+1$이라면 정확히 한 정점에만 두 마리의 개미가 들어가야 합니다. 개미가 두 마리 들어가는 정점을 $x$라고 하면, 간선 $(p(v), v)$ 를 통과하는 개미의 수는 다음과 같이 계산할 수 있습니다.

  • $v$가 $x$ 또는 $x$의 조상인 경우: $\vert S[v] - 1 \vert$
  • $v$가 $x$의 조상이 아닌 경우: $\vert S_v \vert$

즉, 루트에서 $x$로 가는 경로 위의 간선을 통과하는 개미의 수만 바뀌고, 다른 간선들의 값은 바뀌지 않습니다. 따라서 개미 한 마리를 $x$로 보내는 비용은 $D(x) = D(p(x)) + \vert S[x] - 1 \vert - \vert S[x] \vert$을 이용해 계산할 수 있습니다. 비용을 최소화하는 것이 목적으므로, 문제의 정답은 $\sum \vert S_v \vert + \min D_v$입니다.

마지막으로 $S = N+2$인 상황을 생각합시다. 정확히 두 정점에 두 마리의 개미가 들어가야 합니다. 개미가 두 마리 들어가는 두 정점을 각각 $x, y$라고 하고, $x$와 $y$의 LCA를 $l$이라고 하면, 간선 $(p(v), v)$를 통과하는 개미의 수는 다음과 같이 계산할 수 있습니다.

  • $v$가 $l$ 또는 $l$의 조상인 경우: $\vert S[v] - 2 \vert$
  • $v$가 $x$ 또는 $y$, 또는 그들의 조상이면서 $l$의 자손인 경우: $\vert S[v] - 1 \vert$
  • 나머지: $\vert S[v] \vert$

$f(v) = \vert S[v] - 1 \vert - \vert S[v] \vert$, $g(v) = \vert S[v] - 2 \vert - \vert S[v] \vert$라고 정의하고, $D_f(x)$를 루트부터 $x$까지 $f$의 합, $D_g(x)$를 루트부터 $x$까지 $g$의 합이라고 합시다. 개미가 두 마리 들어갈 정점을 각각 $x, y$라고 하면, 비용은 $\sum \vert S[v] \vert$에서 $D_f(x) + D_f(y) - 2D_f(l) + D_g(l)$ 만큼 증가합니다. 따라서 이 식의 결과로 가능한 최솟값을 구하면 문제를 해결할 수 있습니다. 이는 트리 DP를 이용해 트리의 지름을 구하는 것처럼, 두 정점의 LCA를 고정한 다음 가장 작은 두 자식 정점의 값을 가져오는 방식으로 $O(N)$ 시간에 계산할 수 있습니다.

따라서 $S = N, N+1, N+2$인 문제를 모두 $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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

ll N, A[505050], S[505050], Df[505050], Dg[505050], T;
vector<int> G[505050];

void DFS0(int v, int b=-1){
    S[v] = A[v] - 1;
    for(auto i : G[v]) if(i != b) DFS0(i, v), S[v] += S[i];
}

void DFS1(int v, int b=-1){
    Df[v] = (b != -1 ? Df[b] : 0) + abs(S[v]-1) - abs(S[v]);
    Dg[v] = (b != -1 ? Dg[b] : 0) + abs(S[v]-2) - abs(S[v]);
    for(auto i : G[v]) if(i != b) DFS1(i, v);
}

ll DFS2(ll &res, int v, int b=-1){
    ll mn1 = Df[v], mn2 = INF;
    for(auto i : G[v]){
        if(i == b) continue;
        ll now = DFS2(res, i, v);
        if(now < mn1) mn2 = mn1, mn1 = now;
        else if(now < mn2) mn2 = now;
    }
    res = min(res, mn1 + mn2 - 2*Df[v] + Dg[v]);
    return mn1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1,u,v; i<N; i++) cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
    T = accumulate(A+1, A+N+1, 0LL);
    assert(N <= T && T <= N + 2);

    DFS0(1);
    ll move = accumulate(S+1, S+N+1, 0LL, [](ll a, ll b){ return a + abs(b); });
    if(T == N){ cout << move; return 0; }

    DFS1(1);
    ll mn = *min_element(Df+1, Df+N+1);
    if(T == N + 1){ cout << move + mn; return 0; }

    ll pick_two = INF;
    DFS2(pick_two, 1);
    if(T == N + 2){ cout << move + pick_two; return 0; }

    assert(false);
}

1214 5번. 마방진 만들기

$N \le 3$일 때는 가능한 $O(N^2!)$가지 조합을 시도하면 되므로 $N = 4$인 경우만 생각해도 충분합니다.

다항 시간에 풀 수 없어보이므로 가지치기를 동반한 완전 탐색을 시도해야 할 텐데, 잘 생각해 보면 탐색하지 않고도 값을 확정지을 수 있는 칸이 존재한다는 것을 알 수 있습니다. 구체적으로,

  • $(0, 0)$, $(0, 1)$, $(0, 2)$의 값이 정해지면 $(0, 3)$의 값은 자동으로 확정됩니다.
  • $(1, 0)$, $(1, 1)$, $(1, 2)$의 값이 정해지면 $(1, 3)$의 값은 자동으로 확정됩니다.
  • $(2, 1)$, $(2, 2)$의 값이 정해지면 나머지 6칸의 값이 자동으로 확정됩니다.

따라서 16개의 칸 중 8칸의 값만 정하면 다른 8칸의 값은 탐색할 필요가 없습니다. 따라서 탐색해야 하는 경우의 수를 $16!/8! = 518\,918\,400$ 으로 줄일 수 있고, 적절한 가지치기를 동반해 제한 시간 안에 문제를 해결할 수 있습니다.

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
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 0x3f3f3f3f;

int N, A[16], B[4][4], C[111], R, S;

bool Check(){
    for(int i=0; i<N; i++){
        int x = 0, y = 0;
        for(int j=0; j<N; j++) x += B[i][j];
        for(int j=0; j<N; j++) y += B[j][i];
        if(x != S || y != S) return false;
    }
    int x = 0, y = 0;
    for(int i=0; i<N; i++) x += B[i][i], y += B[i][N-i-1];
    return x == S && y == S;
}

void SolveSmall(){
    do{
        for(int i=0; i<N*N; i++) B[i/N][i%N] = A[i];
        R += Check();
    }while(next_permutation(A, A+N*N));
}

vector<pair<int,int>> Pos = {
    {0, 0}, {0, 1}, {0, 2}, {0, 3},
    {1, 0}, {1, 1}, {1, 2}, {1, 3},
    {2, 1}, {2, 2},
    {3, 0}, {3, 1}, {3, 2}, {3, 3},
    {2, 0}, {2, 3}
};

bool Feasible(int x){ return 0 <= x && x <= 100 && C[x] > 0; }

int Calc(int r, int c){
    if(r <= 1 && c == 3) return S - B[r][0] - B[r][1] - B[r][2];
    if(r == 3 && c == 0) return S - B[0][3] - B[1][2] - B[2][1];
    if(r == 3 && c == 3) return S - B[0][0] - B[1][1] - B[2][2];
    if(r == 3 && (c == 1 || c == 2)) return S - B[0][c] - B[1][c] - B[2][c];
    if(r == 2 && (c == 0 || c == 3)) return S - B[0][c] - B[1][c] - B[3][c];
    return INF;
}

void Solve(int idx){
    if(idx == Pos.size()){ R += Check(); return; }
    auto [r,c] = Pos[idx];
    auto auto_fill = Calc(r, c);
    if(auto_fill != INF){
        if(Feasible(auto_fill)){
            B[r][c] = auto_fill; C[auto_fill]--;
            Solve(idx+1);
            C[auto_fill]++;
        }
        return;
    }

    for(int i=0; i<16; i++){
        if(i > 0 && A[i-1] == A[i] || !Feasible(A[i])) continue;
        B[r][c] = A[i]; C[A[i]]--;
        Solve(idx+1);
        C[A[i]]++;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=0; i<N*N; i++) cin >> A[i];
    for(int i=0; i<N*N; i++) C[A[i]]++;
    sort(A, A+N*N);

    S = accumulate(A, A+N*N, 0);
    if(S % N != 0){ cout << 0; return 0; }
    S /= N;
    if(N <= 3){ SolveSmall(); cout << R; return 0; }

    Solve(0);
    cout << R;
}

1519 3번. 물 뿌리기

트리 위에 원을 2개 그린 뒤, 두 원의 교집합에 속한 정점의 값을 업데이트하는 쿼리를 처리해야 합니다. 트리에서 원의 교집합이 어떤 형태인지를 먼저 관찰해 봅시다.

두 원 $C_1(v_1, r_1)$, $C_2(v_2, r_2)$가 있다고 합시다. 만약 $v_1$과 $v_2$ 사이의 거리 $d$가 $r_1+r_2$보다 크다면 교집합은 공집합입니다. 그렇지 않은 경우, 두 원의 교집합은 $v_1$에서 $v_2$ 방향으로 $x = \frac{r_1+(d-r_2)}{2}$ 만큼 이동한 지점이 중심이고, 반지름이 $r_2 - x$인 원이 됨을 알 수 있습니다. 즉, 정점을 원의 중심으로 하는 두 원의 교집합은, 정점 또는 간선의 중앙을 중심으로 하는 원입니다.

따라서 간선의 중앙에 정점을 하나씩 더 끼워넣은 크기가 $2N-1$인 트리를 만들면, 어떤 정점 $v$와의 거리가 $d$ 이하인 모든 정점의 값을 업데이트하는 문제로 바꿀 수 있습니다. 센트로이드 트리를 이용하면 사용하는 자료구조에 따라 매번 $O(\log N)$ 또는 $O(\log^2 N)$ 시간에 업데이트할 수 있습니다.

이후 단계는 단순한 다익스트라 알고리즘으로, $O(N \log N)$ 시간에 완료할 수 있습니다. 따라서 전체 시간 복잡도는 $O((N+M) \log N)$ 또는 $O(N \log N + M \log^2 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
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
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_N = 101010;
constexpr int INF = 0x3f3f3f3f;

struct Circle{
    int v, r;
    Circle() : v(-1), r(0) {}
    Circle(int v, int r) : v(v), r(r) {}
    bool empty() const { return v == -1; }
};

int N, M, K, P[22][MAX_N*2], D[MAX_N*2];
vector<int> G[MAX_N*2], T[MAX_N*2];
int R[MAX_N*2];

void DFS(int v, int b=-1){
    for(auto i : G[v]) if(i != b) D[i] = D[v] + 1, P[0][i] = v, DFS(i, v);
}
int LCA(int u, int v){
    if(D[u] < D[v]) swap(u, v);
    for(int i=0, k=D[u]-D[v]; k; i++, k/=2) if(k & 1) u = P[i][u];
    if(u == v) return u;
    for(int i=21; i>=0; i--) if(P[i][u] != P[i][v]) u = P[i][u], v = P[i][v];
    return P[0][u];
}
int Dist(int u, int v){ return D[u] + D[v] - 2 * D[LCA(u, v)]; }
int Kth(int v, int k){
    for(int i=0; k; i++, k/=2) if(k & 1) v = P[i][v];
    return v;
}

Circle operator + (const Circle &a, const Circle &b){
    if(a.empty() || b.empty()) return Circle();
    int dist = Dist(a.v, b.v);
    if(a.r + b.r < dist) return Circle();

    int st = max(-a.r, dist - b.r);
    int ed = min(+a.r, dist + b.r);
    int md = (st + ed) / 2, lca = LCA(a.v, b.v);
    if(D[a.v] - D[lca] < md) return Circle(Kth(b.v, dist - md), ed - md);
    else return Circle(Kth(a.v, md), ed - md);
}

// Centroid tree

int S[MAX_N*2], U[MAX_N*2], CP[MAX_N*2], CD[MAX_N*2], SubDist[22][MAX_N*2];
vector<pair<int,int>> ST[MAX_N*2]; // subtree info: {dist, vertex}

int GetSize(int v, int b=-1){
    S[v] = 1;
    for(auto i : G[v]) if(i != b && !U[i]) S[v] += GetSize(i, v);
    return S[v];
}
int GetCent(int v, int sz, int b=-1){
    for(auto i : G[v]) if(i != b && !U[i] && S[i] * 2 > sz) return GetCent(i, sz, v);
    return v;
}
void Gather(int root, int v, int b=-1, int d=0){
    ST[root].emplace_back(d, v); SubDist[CD[root]][v] = d;
    for(auto i : G[v]) if(i != b && !U[i]) Gather(root, i, v, d+1);
}
int Build(int v=1, int lv=0){
    v = GetCent(v, GetSize(v)); U[v] = 1; CD[v] = lv;
    Gather(v, v);
    sort(ST[v].begin(), ST[v].end(), greater<>());
    for(auto i : G[v]) if(!U[i]) CP[Build(i, lv+1)] = v;
    return v;
}
void Update(int v, int r, int t){
    // Circle(v, r) <- t
    for(int x=v; x; x=CP[x]){
        int limit = r - SubDist[CD[x]][v];
        while(!ST[x].empty() && ST[x].back().first <= limit){
            auto y = ST[x].back().second;
            R[y] = min(R[y], t);
            ST[x].pop_back();
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K;
    for(int i=1; i<N; i++){
        int u, v; cin >> u >> v;
        G[u].push_back(N+i); G[N+i].push_back(u);
        G[v].push_back(N+i); G[N+i].push_back(v);
        T[u].push_back(v); T[v].push_back(u);
    }
    N = N * 2 - 1; DFS(1);
    for(int i=1; i<22; i++) for(int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];
    Build();

    memset(R, 0x3f, sizeof R);
    vector<pair<int, Circle>> V;
    for(int i=1; i<=M; i++){
        int t, u, v, ru, rv;
        cin >> t >> u >> v >> ru >> rv;
        Circle c = Circle(u, ru*2) + Circle(v, rv*2);
        if(!c.empty()) V.emplace_back(t, c);
    }
    sort(V.begin(), V.end(), [](auto a, auto b){ return a.first < b.first; });
    for(auto [t,c] : V) Update(c.v, c.r, t);

    N = (N + 1) / 2;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> Q;
    for(int i=1; i<=N; i++) if(R[i] < INF) Q.emplace(R[i], i);

    while(!Q.empty()){
        auto [c,v] = Q.top(); Q.pop();
        if(c == R[v]) for(auto i : T[v]) if(R[i] > c + K) Q.emplace(R[i]=c+K, i);
    }
    for(int i=1; i<=N; i++) cout << (R[i] < INF ? R[i] : -1) << "\n";
}

1519 4번. 거래

서브태스크 2. $P_i \ne 0$

이득을 최대화하기 위해서는 $i$번째 물건을 산 다음, $i, i+1, \cdots, N$번째 날 중 물건이 가장 비쌀 때 팔면 됩니다. 따라서 $M_i = \max_{i \le k \le N} P_k$라고 정의하면, 문제의 답은 $\mathcal{F}(P) = \sum M_i - P_i$가 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, A[8080], M[8080], R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=N; i>=1; i--) M[i] = max(M[i+1], A[i]);
    for(int i=1; i<=N; i++) R += M[i] - A[i];
    cout << R;
}

하지만 다르게도 생각해 볼 수 있습니다.

어떤 정수 $h$에 대해, 가격이 $h$ 이하일 때 구매한 뒤에 $h$ 초과일 때 판매해서 수익을 얻는 횟수를 생각해 봅시다. 구체적으로, $1 \le P_i \le h$이면서 $i < j$ 이고 $P_j > h$인 $j$가 존재하는 $i$의 개수를 $f_h(P)$라고 정의하면, $\mathcal{F}(P) = \sum_{h=1}^{N-1} f_h(P)$가 성립합니다.

$f_h(P)$는 $h$ 초과가 등장하는 마지막 위치보다 앞에 있는 $1 \le P_i \le h$인 개수라고 생각할 수 있습니다. 계산하기 쉽게 만들기 위해 $g_h(P) :=$ $h$ 초과가 등장하는 마지막 인덱스보다 뒤에 있는 $1 \le P_i \le h$ 의 개수를 정의합시다. $f_h(P) = h - g_h(P)$가 성립하며, $g_h(P)$는 $h$가 증가하는 순서대로 보면 펜윅 트리 등을 이용해 $g_1(P), g_2(P), \cdots, g_{N-1}(P)$를 모두 $O(N \log N)$ 시간에 구할 수 있습니다.

따라서 $\mathcal{F}(P) = \sum_{h=1}^{N-1} f_h(P) = \sum_{h=1}^{N-1} h - g_h(P) = N(N-1)/2 - \sum_{h=1}^{N-1} g_h(P)$도 $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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, A[8080], R;
int T[8080]; // fenwick tree
void Add(int x, int v){ for(x+=3; x<8080; x+=x&-x) T[x] += v; }
int Get(int x){ int r = 0; for(x+=3; x; x-=x&-x) r += T[x]; return r; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];

    int pos = N;
    for(int h=1; h<N; h++){
        while(A[pos] <= h) Add(A[pos], 1), pos--;
        R += h - Get(h);
    }
    cout << R;
}

아래와 같이 펜윅 트리 없이 $O(N^2)$에 계산할 수도 있습니다. 뒤에서는 이 방법을 발전시켜서 전체 문제를 해결할 것입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int N, A[8080];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];

    int sum = 0;
    for(int h=1; h<N; h++){
        for(int p=N; p>=1 && A[p]<=h; p--) sum++;
    }
    cout << N * (N - 1) / 2 - sum;
}

서브태스크 7 (100점)

설명의 편의를 위해 수열 전체에 있는 물음표의 개수를 $K$라고 합시다.

$\sum_P \mathcal{F}(P) = \sum_{h=1}^{N-1} \sum_P h - g_h(P)$ 를 계산해야 합니다. 식을 정리하면 $\sum_{h=1}^{N-1} K!h - \sum_P g_h(P) = K!N(N-1)/2 - \sum_{h=1}^{N-1} \sum_P g_h(P)$ 가 되므로, $\sum_{h=1}^{N-1} \sum_P g_h(P)$만 빠르게 계산하면 됩니다. 마찬가지로 $h$가 증가하는 순서대로 계산할 것입니다.

$h$와 $p$를 고정했을 때, $p$ 이후에 있는 모든 수가 $h$ 이하인 순열의 경우의 수를 세는 방법에 대해 생각해 봅시다. $p$ 이후애 있는 물음표의 개수를 $K_p$, 물음표 자리에 들어갈 수 있는($P$에 등장하지 않은) $h$ 이하인 수의 개수를 $L_h$라고 합시다.

$p$ 이후에 있는 모든 수가 $h$ 이하인 순열을 만들기 위해서는, 우선 $L_h$개의 수 중 $K_p$개를 골라서 배치한 다음, 남은 $K-K_p$개의 수를 남은 자리에 자유롭게 배치하면 됩니다. 따라서 $L_h! / (L_h - K_p)! \times (K-K_p)!$이 됨을 알 수 있습니다.

따라서 모든 $p, h$에 대해 $L_h! / (L_h - K_p)! \times (K-K_p)!$를 더해서 $\sum_{h=1}^{N-1} \sum_P g_h(P)$를 구할 수 있으며, $O(N^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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 998244353;

ll Pow(ll a, ll b){
    ll res = 1;
    for(; b; b>>=1, a=a*a%MOD) if(b & 1) res = res * a % MOD;
    return res;
}

ll N, K, A[8080], C[8080], R;
ll Fac[8080], Inv[8080];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) C[A[i]] = 1;
    K = count(A+1, A+N+1, 0);

    Fac[0] = 1;
    for(int i=1; i<=N; i++) Fac[i] = Fac[i-1] * i % MOD;
    Inv[N] = Pow(Fac[N], MOD-2);
    for(int i=N-1; i>=0; i--) Inv[i] = Inv[i+1] * (i+1) % MOD;

    for(int h=1; h<N; h++){
        int low_h = 0, empty = 0;
        for(int i=1; i<=h; i++) low_h += !C[i];

        for(int p=N; p>=1 && A[p]<=h; p--){
            empty += !A[p];
            if(low_h - empty < 0) break;
            ll now = Fac[low_h] * Inv[low_h-empty] % MOD * Fac[K-empty] % MOD;
            R = (R + now) % MOD;
        }
    }

    ll tmp = N*(N-1)/2 % MOD * Fac[K] % MOD;
    cout << (tmp - R + MOD) % MOD;
}

1519 5번. 편집 거리

두 가지 문제가 합쳐진 문제입니다.

  1. $N \le 100\,000$, $M \le 1\,000$, $K \le 20$ (서브태스크 1, 2, 4, 5 / 65점)
  2. $N \le 5\,000$, $M \le 1\,000$, $K \le 1\,000$ (서브태스크 1, 2, 3 / 55점)

첫 번째 문제는 $K$가 작다는 점을 이용해 $O(NK^2)$ 시간에 푸는 문제, 두 번째 문제는 $O(NM)$ 시간에 푸는 문제입니다.

서브태스크 1. $N \le 1000, M \le 100, K \le 100$ (8점)

$T$의 모든 접미사와 $P$의 edit distance table(D table)를 구하면 문제를 해결할 수 있습니다. D table을 한 번 구하는 데 $O(NM)$ 만큼 걸리므로 $O(N^2M)$ 시간에 문제를 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int D[1010][111], R[111];

void Solve(const string &a, const string &b){
    int n = a.size(), m = b.size();
    for(int i=0; i<=n; i++) D[i][0] = i;
    for(int j=0; j<=m; j++) D[0][j] = j;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            D[i][j] = min({ D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + (a[i-1] != b[j-1]) });
        }
    }
    for(int i=1; i<=n; i++) R[D[i][m]]++;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, M, K; string S, P;
    cin >> N >> M >> K >> S >> P;
    for(int i=0; i<N; i++) Solve(S.substr(i), P);
    for(int i=0; i<=K; i++) cout << R[i] << "\n";
}

$K$ 범위 제한을 이용하면, $S$의 접미사를 볼 때 첫 $M+K$글자만 봐도 된다는 사실을 알 수 있습니다. 이를 이용하면 편집 거리가 $K$ 이하인 D table의 일부를 구하는 데 $O(M(M+K))$ 시간이 걸리므로, $O(NM^2)$ 시간에 문제를 해결할 수 있습니다. 위 코드의 7번째 줄 뒤에 n = min(n, m+K); 만 추가하면 됩니다.

서브태스크 2. $N \le 3000, M \le 1000, K \le 20$ (20점)

$P$와의 편집 거리가 $K$ 이하인 문자열의 길이는 항상 $M-K$ 이상, $M+K$ 이하입니다. 따라서 D table에서 주대각선과 $K$ 이하 만큼 떨어진 칸들만 계산해도 문제를 해결할 수 있습니다. 이 경우 D table을 한 번 구하는 데 $O(MK)$ 시간이 걸리므로, 전체 시간 복잡도는 $O(NMK)$가 됩니다.

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
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 0x3f3f3f3f;

int D[1010][3030], R[3030];

void Clear(int n, int m, int k){
    for(int j=0; j<=m; j++){
        for(int i=j-k; i<=j+k; i++) if(0 <= i && i <= n) D[j][i] = INF;
        for(int i=-k; i<=k; i++) if(0 <= j+k && j+k <= n) D[j][j+k] = INF;
    }
}

void Solve(const string &a, const string &b, int k){
    int n = a.size(), m = b.size();
    for(int i=0; i<=k; i++) D[0][i] = i;
    for(int j=1; j<=m; j++){
        for(int i=j-k; i<=j+k; i++){
            if(i < 0 || i > n) continue;
            if(i == 0){ D[j][0] = j; continue; }
            D[j][i] = min({ D[j][i-1] + 1, D[j-1][i] + 1, D[j-1][i-1] + (b[j-1] != a[i-1]) });
        }
    }
    for(int i=m-k; i<=m+k; i++) if(1 <= i && i <= n) R[D[m][i]]++;
    Clear(n, m, k);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, M, K; string S, P;
    cin >> N >> M >> K >> S >> P;
    memset(D, 0x3f, sizeof D);
    for(int i=0; i<N; i++) Solve(S.substr(i), P, K);
    for(int i=0; i<=K; i++) cout << R[i] << "\n";
}

서브태스크 4 & 5. $N \le 100\,000, M \le 1000, K \le 20$ (65점)

D table에서 오른쪽 아래로 향하는 대각선을 보면, 항상 값이 단조증가한다는 것을 알 수 있습니다. 더 나아가서, 대각선 위에서 인접한 두 칸은 항상 0 또는 1 만큼 차이납니다. 따라서, 각 대각선마다 값이 $k$에서 $k+1$로 바뀌는 지점을 빠르게 찾을 수 있다면, 그러한 연산을 $O(NK^2)$번 수행해서 $K$ 이하인 모든 D table의 값을 알 수 있습니다.

D table에서 대각선 방향으로 같은 값이 많이 뻗어나가는지를 구하면, 값이 1 만큼 증가하는 시점을 포착할 수 있습니다. 구체적으로, $i - j$가 $s$로 일정한 칸들 중, $D(i, j) = k-1$인 마지막 칸을 $(i_{s,k-1}, j_{s,k-1})$이라고 하면, $(i_{s,k}, j_{s,k})$는 아래 세 가지 경우를 계산해서 구할 수 있습니다.

  1. $(i_{s,k-1}, j_{s,k-1})$에서 값을 1 만큼 증가시켜서 대각선 방향으로 내려온 다음, $(i_{s,k-1}+1, j_{s,k-1}+1)$부터 값 증가 없이 대각선 타고 내려가기
  2. $(i_{s-1,k-1}, j_{s-1,k-1})$에서 값을 1 만큼 증가시켜서 한 칸 내려온 다음, $(i_{s-1,k-1}+1, j_{s-1,k-1})$부터 값 증가 없이 대각선 타고 내려가기
  3. $(i_{s+1,k-1}, j_{s+1,k-1})$에서 값을 1 만큼 증가시켜서 한 칸 오른쪽으로 이동한 다음, $(i_{s+1,k-1}, j_{s+1,k+1}+1)$부터 값 증가 없이 대각선 타고 내려가기

대각선을 타고 내려간다는 것을 다르게 이야기하면 $A_i = B_j$가 성립할 동안 $i$와 $j$를 계속 증가시키겠다는 뜻이고, 이는 $A[i\cdots]$와 $B[j\cdots]$의 prefix가 얼마나 많이 일치하는지, 즉 longest common prefix를 구한다는 것을 의미합니다. 따라서 $A\sharp B$의 접미사 배열와 LCP 배열을 미리 전처리해 두면, 스파스 테이블 등을 이용해 $O(1)$ 시간에 대각선을 얼마나 타고 내려갈 수 있는지를 구할 수 있습니다.

각 대각선마다 DP 값의 변화를 매번 $O(1)$ 시간에 구할 수 있으므로, 한 대각선의 DP 값을 총 $O(K)$ 시간에 구할 수 있습니다. 대각선은 $-K \le i-j \le K$ 범위에서 총 $2K+1$개를 관리해야 하므로, $O(K^2)$ 시간에 $T$의 suffix에 대한 문제를 해결할 수 있으며, 전체 문제는 $O(NK^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
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
#include <bits/stdc++.h>
using namespace std;

tuple<vector<int>, vector<int>, vector<int>> SuffixArray(const string &s){
    int n = s.size(), m = max(n, 256);
    vector<int> sa(n), lcp(n), pos(n), tmp(n), cnt(m);
    auto counting_sort = [&](){
        fill(cnt.begin(), cnt.end(), 0);
        for(int i=0; i<n; i++) cnt[pos[i]]++;
        partial_sum(cnt.begin(), cnt.end(), cnt.begin());
        for(int i=n-1; i>=0; i--) sa[--cnt[pos[tmp[i]]]] = tmp[i];
    };
    for(int i=0; i<n; i++) sa[i] = i, pos[i] = s[i], tmp[i] = i;
    counting_sort();
    for(int k=1; ; k<<=1){
        int p = 0; for(int i=n-k; i<n; i++) tmp[p++] = i;
        for(int i=0; i<n; i++) if(sa[i] >= k) tmp[p++] = sa[i] - k;
        counting_sort(); tmp[sa[0]] = 0;
        for(int i=1; i<n; i++){
            tmp[sa[i]] = tmp[sa[i-1]];
            if(sa[i-1]+k < n && sa[i]+k < n && pos[sa[i-1]] == pos[sa[i]] && pos[sa[i-1]+k] == pos[sa[i]+k]) continue;
            tmp[sa[i]] += 1;
        }
        swap(pos, tmp);
        if(pos[sa.back()] + 1 == n) break;
    }
    for(int i=0, j=0; i<n; i++, j=max(j-1,0)){
        if(pos[i] == 0) continue;
        while(sa[pos[i]-1]+j < n && sa[pos[i]]+j < n && s[sa[pos[i]-1]+j] == s[sa[pos[i]]+j]) j++;
        lcp[pos[i]] = j;
    }
    return {sa, lcp, pos};
}

struct sparse_table{
    vector<vector<int>> v;
    sparse_table() = default;
    sparse_table(vector<int> a){
        int n = a.size(), lg = __lg(n*2-1);
        v = vector<vector<int>>(lg+1, vector<int>(n));
        for(int i=0; i<n; i++) v[0][i] = a[i];
        for(int i=1; i<=lg; i++) for(int j=0; j+(1<<i)-1<n; j++) v[i][j] = min(v[i-1][j], v[i-1][j+(1<<(i-1))]);
    }
    int get(int l, int r) const {
        int k = __lg(r-l+1);
        return min(v[k][l], v[k][r-(1<<k)+1]);
    }
};

vector<vector<int>> GetDP(string a, string b){
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1));
    for(int i=0; i<=n; i++) dp[i][0] = i;
    for(int j=0; j<=m; j++) dp[0][j] = j;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[i][j] = min({dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (a[i-1] != b[j-1])});
        }
    }
    return dp;
}

int N, M, K, Answer[1010];
string S, T;
vector<int> SA, LCP, Pos;
sparse_table RMQ;

int GetLCP(int i, int j){
    // lcp(S[i..N-1], T[j..M-1]
    int u = Pos[i], v = Pos[N+1+j];
    if(u > v) swap(u, v);
    return RMQ.get(u+1, v);
}

bool Bound(int s, int i, int j){
    return 0 <= i && i <= N - s && 0 <= j && j <= M;
}

// DP 테이블에서 (i - j)가 같은 대각선 관리
// End[sub][value] : (i - j) = sub인 대각선에서 value가 등장하는 마지막 열 번호
// Use[sub] : (i - j) = sub인 대각선에서 값이 채워진 마지막 열 번호(= max End[sub][value])
// -K <= sub <= K, 0 <= value <= K
int End[2020][1010], Use[2020];

void Clear(){
    for(int i=0; i<=K+K; i++) memset(End[i], -1, sizeof(End[0][0]) * (K+1));
    memset(Use, -1, sizeof(Use[0]) * (2*K+1));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K >> S >> T;
    tie(SA,LCP,Pos) = SuffixArray(S + "#" + T);
    RMQ = sparse_table(LCP);

    for(int s=0; s<N; s++){
        // get edit distance between S[s..N-1] and T[0..M-1]
        Clear();

        for(int value=0; value<=K; value++){
            // i - j = sub, i = sub + j
            for(int sub=-value; sub<=value; sub++){
                int st_i, st_j = -1;
                if(sub == value || sub == -value) st_j = max(st_j, -min(sub,0));

                if(value > 0 && End[sub+K][value-1] != -1){
                    // 현재 대각선에서 value-1의 끝점이 (i, j)이면 (i+1, j+1)부터 시작
                    st_j = max(st_j, End[sub+K][value-1]+1);
                }
                if(value > 0 && abs(sub-1) <= K && End[sub-1+K][value-1] != -1){
                    // 위 대각선에서 value-1의 끝점이 (i, j)이면 (i+1, j)부터 시작
                    st_j = max(st_j, End[sub-1+K][value-1]);
                }
                if(value > 0 && abs(sub+1) <= K && End[sub+1+K][value-1] != -1){
                    // 아래 대각선에서 value-1의 끝점이 (i, j)이면 (j, j+1)부터 시작
                    st_j = max(st_j, End[sub+1+K][value-1]+1);
                }

                st_i = sub + st_j;
                if(st_j == -1 || st_j <= Use[sub+K]) continue;

                if(!Bound(s, st_i, st_j)){
                    // 위 또는 왼쪽 대각선에서 (i+1, j) (i, j+1) 넘겨줄 때, 범위를 벗어나는 경우가 있음
                    // 이 경우에는 (st_i - 1, st_j - 1)까지 쭉 value로 이어진다고 생각할 수 있음
                    if(st_j - 1 > Use[sub+K]) End[sub+K][value] = Use[sub+K] = st_j - 1;
                }
                else if(st_i == N - s || st_j == M){
                    // 이 상황에서 LCP 구하면 런타임 에러, 경계에 있으므로 자기 자신이 끝점이 됨
                    if(st_j > Use[sub+K]) End[sub+K][value] = Use[sub+K] = st_j;
                }
                else{
                    // DP(i, j) <- DP(i-1, j-1)을 얼마나 많이 연속해서 사용할 수 있는지 LCP 배열로 구함
                    int len = GetLCP(s + st_i, st_j);
                    int ed_i = st_i + len, ed_j = st_j + len;
                    End[sub+K][value] = Use[sub+K] = ed_j;
                }
            }
        }

        for(int sub=-K; sub<=K; sub++){
            int j = M, i = sub + j;
            if(i == 0 || !Bound(s, i, j)) continue;
            for(int value=0; value<=K; value++) if(End[sub+K][value] == j) Answer[value]++;
        }
    }

    for(int i=0; i<=K; i++) cout << Answer[i] << " ";
}

서브태스크 3. $N \le 5000, M \le 1000, K \le 1000$ (100점)

$T[i\cdots]$와 $P$의 D table에서 $T[i+1\cdots]$와 $P$의 D table로 전이하는 것은, 최악의 경우 $O(NM)$개의 칸의 값이 바뀔 수 있으므로 $O(NM)$보다 빠르게 할 수 없습니다. 따라서 D table의 정보를 보존하는 또다른 테이블을 만들어서 관리해야 합니다.

풀이 준비 중…