서론

문제 지문과 공식 풀이는 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번. 기호

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

#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 등을 이용해 컴포넌트의 크기를 구하면 됩니다.

#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)$ 풀이를 얻을 수 있습니다.

#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$값이 같은 상태를 되돌려주므로 선공이 질 수밖에 없습니다.

#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)$ 시간에 해결할 수 있습니다.

#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$ 으로 줄일 수 있고, 적절한 가지치기를 동반해 제한 시간 안에 문제를 해결할 수 있습니다.

#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)$이며, 두 풀이 모두 제한 시간 안에 문제를 해결할 수 있습니다.

#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$가 됩니다.

#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)$ 시간에 구할 수 있습니다.

#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)$에 계산할 수도 있습니다. 뒤에서는 이 방법을 발전시켜서 전체 문제를 해결할 것입니다.

#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)$ 시간에 계산할 수 있습니다.

#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번. 편집 거리

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

$N \le 100\,000$, $M \le 1\,000$, $K \le 20$ (서브태스크 1, 2, 4, 5 / 65점)
$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)$ 시간에 문제를 해결할 수 있습니다.

#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)$가 됩니다.

#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})$는 아래 세 가지 경우를 계산해서 구할 수 있습니다.

$(i_{s,k-1}, j_{s,k-1})$에서 값을 1 만큼 증가시켜서 대각선 방향으로 내려온 다음, $(i_{s,k-1}+1, j_{s,k-1}+1)$부터 값 증가 없이 대각선 타고 내려가기
$(i_{s-1,k-1}, j_{s-1,k-1})$에서 값을 1 만큼 증가시켜서 한 칸 내려온 다음, $(i_{s-1,k-1}+1, j_{s-1,k-1})$부터 값 증가 없이 대각선 타고 내려가기
$(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)$ 시간에 해결할 수 있습니다.

#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의 정보를 보존하는 또다른 테이블을 만들어서 관리해야 합니다.

풀이 준비 중…

2025 NYPC 본선 풀이

댓글