2023 KOI 고등부 2차 대회 후기

 2023 한국 정보 올림피아드 2차 대회가 2023년 7월 16일에 온라인으로 개최되었습니다. 모두 수고하셨습니다.

 

모든 문제를 해결하여 400점을 받았습니다.

타임라인

00:00:00 ~ 00:02:08

 1번 "스케이트 연습" 문제를 읽고 해결했습니다.

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

int n, a[500006];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + n - 1 - i);
    int v = 0;
    long long res = 0;
    for (int i = 0; i < n; i++) {
        ++v;
        v = min(v, a[i]);
        res += v;
    }
    printf("%lld", res);
}

00:02:08 ~ 00:49:36

 2번 "지그재그" 문제를 읽고 시행착오를 겪었지만, 이내 풀이를 찾아 해결했습니다.

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

int n, a[200006], idx[200006];
bool imp[200006];
long long update1[200006], sum1;
long long update2[200006], sum2;
set<int> s;

void up1(int x) {
    int pv = *--s.find(x), nx = *++s.find(x);
    imp[x] = pv != -1 && nx != n && (a[pv] < a[x]) != (a[x] < a[nx]);
    sum1 -= update1[x];
    if (imp[x]) update1[x] = 1LL * (x + 1) * (n - x);
    else update1[x] = 0;
    sum1 += update1[x];
}

void up2(int x) {
    int pv = *--s.find(x), nx = *++s.find(x);
    sum2 -= update2[x];
    if (imp[x]) update2[x] = 0;
    else update2[x] = 1LL * (x - pv) * (n - x) + 1LL * (x + 1) * (nx - x) - 1LL * (x - pv) * (nx - x);
    sum2 += update2[x];
}

void up(int x) {
    up1(x);
    up2(x);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i), a[i]--;
    for (int i = 0; i < n; i++) idx[a[i]] = i;
    s.insert(-1);
    s.insert(n);
    for (int i = 0; i < n; i++) {
        s.insert(idx[i]);
        int pv = *--s.find(idx[i]);
        int nx = *++s.find(idx[i]);
        up(idx[i]);
        if (pv != -1) {
            up(pv);
            int ppv = *--s.find(pv);
            if (ppv != -1) up(ppv);
        }
        if (nx != n) {
            up(nx);
            int nnx = *++s.find(nx);
            if (nnx != n) up(nnx);
        }
        printf("%lld\n", sum1 + sum2);
    }
}

00:49:36 ~ 01:26:51

 3번 "잔디밭의 개미굴" 문제를 읽고 트리 DP를 떠올렸지만 정해는 찾지 못했습니다. 각 방에 개미가 있어야 하는지의 여부가 중요하다는 사실을 찾은 뒤 무작위를 이용해 문제를 해결하려고 시도했습니다.

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

mt19937 gen(1104);
uniform_int_distribution<int> uid(0, 1);

int n, dp[250006][2], pv[250006], ck[250006];
vector<int> adj[250006], lt[250006];

int f(int x, int y, int prev = -1) {
    if (dp[x][y] + 1) return dp[x][y];
    dp[x][y] = y;
    for (auto &i: adj[x]) if (i != prev) {
        if (ck[x]) {
            if (y) dp[x][y] += f(i, 0, x);
            else if (f(i, 0, x) > f(i, 1, x)) dp[x][y] += f(i, 0, x);
            else dp[x][y] += f(i, 1, x);
        } else {
            if (y) dp[x][y] += f(i, 0, x);
            else if (f(i, 0, x) < f(i, 1, x)) dp[x][y] += f(i, 1, x);
            else dp[x][y] += f(i, 0, x);
        }
    }
    return dp[x][y];
}

void g(int x, int y, int prev = -1) {
    pv[x] = y;
    for (auto &i: adj[x]) if (i != prev) {
        if (ck[x]) {
            if (y) g(i, 0, x);
            else if (f(i, 0, x) > f(i, 1, x)) g(i, 0, x);
            else g(i, 1, x);
        } else {
            if (y) g(i, 0, x);
            else if (f(i, 0, x) < f(i, 1, x)) g(i, 1, x);
            else g(i, 0, x);
        }
    }
}

void append(int x, int y) {
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < n; i++) ck[i] = (y == 1 ? 0 : y == 2 ? 1 : uid(gen));
    if (ck[0]) {
        if (f(0, 0) > f(0, 1)) g(0, 0);
        else g(0, 1);
    } else {
        if (f(0, 0) < f(0, 1)) g(0, 1);
        else g(0, 0);
    }
    for (int i = 0; i < n; i++) lt[i].push_back(pv[i]);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    append(0, 1);
    append(0, 2);
    for (int g = 0; g < 50; g++) append(0, 0);
    int cnt = 0;
    for (int i = 0; i < n; i++) cnt += *min_element(lt[i].begin(), lt[i].end());
    printf("%lld", 1LL * n * (n - 1) / 2 - 1LL * cnt * (cnt - 1) / 2);
}

01:26:51 ~ 01:34:01

 3번 문제에서 사실 트리 DP를 이용하면 무작위가 필요없다는 사실을 깨닫고 해결했습니다.

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

int n, dp[250006][2], pv[250006];
vector<int> adj[250006];
bool visited[250006][2];

int f(int x, int y, int prev = -1) {
    if (dp[x][y] + 1) return dp[x][y];
    dp[x][y] = y;
    for (auto &i: adj[x]) if (i != prev) {
        if (y) dp[x][y] += f(i, 0, x);
        else if (f(i, 0, x) > f(i, 1, x)) dp[x][y] += f(i, 0, x);
        else dp[x][y] += f(i, 1, x);
    }
    return dp[x][y];
}

void g(int x, int y, int prev = -1) {
    if (visited[x][y]) return;
    visited[x][y] = true;
    pv[x] = min(pv[x], y);
    for (auto &i: adj[x]) if (i != prev) {
        if (y) g(i, 0, x);
        else if (f(i, 0, x) > f(i, 1, x)) g(i, 0, x);
        else if (f(i, 0, x) < f(i, 1, x)) g(i, 1, x);
        else g(i, 0, x), g(i, 1, x);
    }
}

int main() {
    memset(dp, -1, sizeof dp);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) pv[i] = 1;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if (f(0, 0) > f(0, 1)) g(0, 0);
    else if (f(0, 0) < f(0, 1)) g(0, 1);
    else g(0, 0), g(0, 1);
    int cnt = 0;
    for (int i = 0; i < n; i++) cnt += pv[i];
    printf("%lld", 1LL * n * (n - 1) / 2 - 1LL * cnt * (cnt - 1) / 2);
}

01:34:01 ~ 01:44:45

 4번 "바보 자물쇠"를 읽고 \(O(26N)\) DP를 구현해 25점을 받았습니다.

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

int dp[100006][26];
char s[100006];
int n, q;

void solve() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) dp[i][j] = abs(s[i] - 'a' - j) + (i ? dp[i - 1][j] : 0);
        for (int j = 1; j < 26; j++) dp[i][j] = min(dp[i][j], dp[i][j - 1]);
    }
    int res = *min_element(dp[n - 1], dp[n - 1] + 26);
    printf("%d\n", res);
}

int main() {
    scanf("%s%d", s, &q);
    n = strlen(s);
    solve();
    for (int i = 0; i < q; i++) {
        int x;
        char t;
        scanf("%d %c", &x, &t);
        x--;
        s[x] = t;
        solve();
    }
}

01:44:45 ~ 02:30:44

 4번에서 문제 상황을 단순화해 a, b만 등장하는 부분 문제를 가정했고, DP 배열의 기울기를 세그먼트 트리로 관리하는 \(O(N\log^2N)\) 풀이로 12점을 추가 득점했습니다.

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

int tree[262144], lazy[262144];

void propagate(int i, int b, int e) {
    if (b != e) for (auto j: { i * 2 + 1, i * 2 + 2 }) lazy[j] += lazy[i];
    tree[i] += lazy[i];
    tree[i] = max(tree[i], -1);
    lazy[i] = 0;
}

int query(int i, int b, int e, int l, int r) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return (int)1e9;
    if (l <= b && e <= r) return tree[i];
    int m = (b + e) / 2;
    return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}

int update(int i, int b, int e, int l, int r, int v) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return tree[i];
    if (l <= b && e <= r) {
        lazy[i] = v;
        propagate(i, b, e);
        return tree[i];
    }
    int m = (b + e) / 2;
    return tree[i] = min(update(i * 2 + 1, b, m, l, r, v), update(i * 2 + 2, m + 1, e, l, r, v));
}

int findGE(int i, int b, int e, int l, int r, int v) {
    int L = l, R = r + 1;
    while (L < R) {
        int m = (L + R) / 2;
        if (query(0, 0, 131071, L, m) <= v) R = m;
        else L = m + 1;
    }
    return L;
}

char a[100006];
int n, q, res, cntb;

void ins(int x) {
    int it = findGE(0, 0, 131071, x, n - 1, -1);
    if (it == -1 || it >= n) {
        update(0, 0, 131071, x, n - 1, 1);
        return;
    }
    update(0, 0, 131071, x, it, 1);
    res++;
}

void rem(int x) {
    int it = findGE(0, 0, 131071, x, n - 1, 0);
    if (it == -1 || it >= n) {
        update(0, 0, 131071, x, n - 1, -1);
        return;
    }
    update(0, 0, 131071, x, it, -1);
    res--;
}

int main() {
    memset(tree, -1, sizeof tree);
    scanf("%s%d", a, &q);
    n = strlen(a);
    for (int i = 0; i < n; i++) if (a[i] == 'b') {
        ins(i), ins(i);
        cntb++;
    }
    printf("%d\n", res - cntb);
    for (int i = 0; i < q; i++) {
        int x;
        char t;
        scanf("%d %c", &x, &t);
        x--;
        if (a[x] == t) {
            printf("%d\n", res - cntb);
            continue;
        }
        a[x] = t;
        if (t == 'b') ins(x), ins(x), cntb++;
        else rem(x), rem(x), cntb--;
        printf("%d\n", res - cntb);
    }
}

02:30:44 ~ 02:49:10

 4번에서 각 문자끼리 상황이 독립적이라는 사실을 알게 되어 \(O(N\log^2N)\) 풀이를 \(O(N\log N)\) 풀이로 줄였습니다.

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

int tree[262144], lazy[262144];

void propagate(int i, int b, int e) {
    if (b != e) for (auto j: { i * 2 + 1, i * 2 + 2 }) lazy[j] += lazy[i];
    tree[i] += lazy[i];
    tree[i] = max(tree[i], -1);
    lazy[i] = 0;
}

int query(int i, int b, int e, int l, int r) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return (int)1e9;
    if (l <= b && e <= r) return tree[i];
    int m = (b + e) / 2;
    return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}

int update(int i, int b, int e, int l, int r, int v) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return tree[i];
    if (l <= b && e <= r) {
        lazy[i] = v;
        propagate(i, b, e);
        return tree[i];
    }
    int m = (b + e) / 2;
    return tree[i] = min(update(i * 2 + 1, b, m, l, r, v), update(i * 2 + 2, m + 1, e, l, r, v));
}

int binGE(int i, int b, int e, int v) {
    propagate(i, b, e);
    if (b == e) {
        if (tree[i] <= v) return b;
        else return -1;
    }
    int m = (b + e) / 2;
    propagate(i * 2 + 1, b, m);
    if (tree[i * 2 + 1] <= v) return binGE(i * 2 + 1, b, m, v);
    else return binGE(i * 2 + 2, m + 1, e, v);
}

int findGE(int i, int b, int e, int l, int r, int v) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return -1;
    if (l <= b && e <= r) {
        if (tree[i] <= v) return binGE(i, b, e, v);
        return -1;
    }
    int m = (b + e) / 2;
    int t = findGE(i * 2 + 1, b, m, l, r, v);
    if (t != -1) return t;
    return findGE(i * 2 + 2, m + 1, e, l, r, v);
}

char a[100006];
int n, q, res, cntb;

void ins(int x) {
    int it = findGE(0, 0, 131071, x, n, -1);
    if (it == -1 || it >= n) {
        update(0, 0, 131071, x, n - 1, 1);
        return;
    }
    update(0, 0, 131071, x, it, 1);
    res++;
}

void rem(int x) {
    int it = findGE(0, 0, 131071, x, n - 1, 0);
    if (it == -1 || it >= n) {
        update(0, 0, 131071, x, n - 1, -1);
        return;
    }
    update(0, 0, 131071, x, it, -1);
    res--;
}

int main() {
    memset(tree, -1, sizeof tree);
    scanf("%s%d", a, &q);
    n = strlen(a);
    for (int i = 0; i < n; i++) if (a[i] == 'b') {
        ins(i), ins(i);
        cntb++;
    }
    printf("%d\n", res - cntb);
    for (int i = 0; i < q; i++) {
        int x;
        char t;
        scanf("%d %c", &x, &t);
        x--;
        if (a[x] == t) {
            printf("%d\n", res - cntb);
            continue;
        }
        a[x] = t;
        if (t == 'b') ins(x), ins(x), cntb++;
        else rem(x), rem(x), cntb--;
        printf("%d\n", res - cntb);
    }
}

02:49:10 ~ 02:56:49

 4번에서 a, b, c, d, e까지 등장하는 경우의 풀이로 18점을 추가 득점했습니다.

 

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

int tree[4][262144], lazy[4][262144];

void propagate(int u, int i, int b, int e) {
    if (b != e) for (auto j: { i * 2 + 1, i * 2 + 2 }) lazy[u][j] += lazy[u][i];
    tree[u][i] += lazy[u][i];
    tree[u][i] = max(tree[u][i], -1);
    lazy[u][i] = 0;
}

int query(int u, int i, int b, int e, int l, int r) {
    propagate(u, i, b, e);
    if (r < l || r < b || e < l) return (int)1e9;
    if (l <= b && e <= r) return tree[u][i];
    int m = (b + e) / 2;
    return min(query(u, i * 2 + 1, b, m, l, r), query(u, i * 2 + 2, m + 1, e, l, r));
}

int update(int u, int i, int b, int e, int l, int r, int v) {
    propagate(u, i, b, e);
    if (r < l || r < b || e < l) return tree[u][i];
    if (l <= b && e <= r) {
        lazy[u][i] = v;
        propagate(u, i, b, e);
        return tree[u][i];
    }
    int m = (b + e) / 2;
    return tree[u][i] = min(update(u, i * 2 + 1, b, m, l, r, v), update(u, i * 2 + 2, m + 1, e, l, r, v));
}

int binGE(int u, int i, int b, int e, int v) {
    propagate(u, i, b, e);
    if (b == e) {
        if (tree[u][i] <= v) return b;
        else return -1;
    }
    int m = (b + e) / 2;
    propagate(u, i * 2 + 1, b, m);
    if (tree[u][i * 2 + 1] <= v) return binGE(u, i * 2 + 1, b, m, v);
    else return binGE(u, i * 2 + 2, m + 1, e, v);
}

int findGE(int u, int i, int b, int e, int l, int r, int v) {
    propagate(u, i, b, e);
    if (r < l || r < b || e < l) return -1;
    if (l <= b && e <= r) {
        if (tree[u][i] <= v) return binGE(u, i, b, e, v);
        return -1;
    }
    int m = (b + e) / 2;
    int t = findGE(u, i * 2 + 1, b, m, l, r, v);
    if (t != -1) return t;
    return findGE(u, i * 2 + 2, m + 1, e, l, r, v);
}

char a[100006];
int n, q, res;

void ins(int u, int x) {
    int it = findGE(u, 0, 0, 131071, x, n, -1);
    if (it == -1 || it >= n) {
        update(u, 0, 0, 131071, x, n - 1, 1);
        return;
    }
    update(u, 0, 0, 131071, x, it, 1);
    res++;
}

void rem(int u, int x) {
    int it = findGE(u, 0, 0, 131071, x, n - 1, 0);
    if (it == -1 || it >= n) {
        update(u, 0, 0, 131071, x, n - 1, -1);
        return;
    }
    update(u, 0, 0, 131071, x, it, -1);
    res--;
}

int main() {
    memset(tree, -1, sizeof tree);
    scanf("%s%d", a, &q);
    n = strlen(a);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < a[i] - 'a'; j++) {
            ins(j, i);
            ins(j, i);
            res--;
        }
    }
    printf("%d\n", res);
    for (int i = 0; i < q; i++) {
        int x;
        char t;
        scanf("%d %c", &x, &t);
        x--;
        for (int j = a[x] - 'a'; j < t - 'a'; j++) {
            ins(j, x);
            ins(j, x);
            res--;
        }
        for (int j = t - 'a'; j < a[x] - 'a'; j++) {
            rem(j, x);
            rem(j, x);
            res++;
        }
        a[x] = t;
        printf("%d\n", res);
    }
}

02:56:49 ~ 03:11:46

 4번에서 전체 풀이를 제출했지만 상수 차이로 해결하지 못했고, 결국 상수를 줄여 해결했습니다.

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <tuple>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int tree[25][262144], lazy[25][262144];

void propagate(int u, int i, int b, int e) {
    if (!lazy[u][i]) return;
    if (b != e) for (auto j: { i * 2 + 1, i * 2 + 2 }) lazy[u][j] += lazy[u][i];
    tree[u][i] += lazy[u][i];
    tree[u][i] = max(tree[u][i], -1);
    lazy[u][i] = 0;
}

int query(int u, int i, int b, int e, int l, int r) {
    propagate(u, i, b, e);
    if (r < l || r < b || e < l) return (int)1e9;
    if (l <= b && e <= r) return tree[u][i];
    int m = (b + e) / 2;
    return min(query(u, i * 2 + 1, b, m, l, r), query(u, i * 2 + 2, m + 1, e, l, r));
}

int binGE(int u, int i, int b, int e, int v, int up) {
    propagate(u, i, b, e);
    if (b == e) {
        if (tree[u][i] <= v) {
            lazy[u][i] += up;
            propagate(u, i, b, e);
            return b;
        } else return -1;
    }
    int m = (b + e) / 2;
    propagate(u, i * 2 + 1, b, m);
    if (tree[u][i * 2 + 1] <= v) {
        int t = binGE(u, i * 2 + 1, b, m, v, up);
        tree[u][i] = min(tree[u][i * 2 + 1], tree[u][i * 2 + 2]);
        return t;
    } else {
        lazy[u][i * 2 + 1] += up;
        propagate(u, i * 2 + 1, b, m);
        int t = binGE(u, i * 2 + 2, m + 1, e, v, up);
        tree[u][i] = min(tree[u][i * 2 + 1], tree[u][i * 2 + 2]);
        return t;
    }
}

int findGE(int u, int i, int b, int e, int l, int r, int v, int up) {
    propagate(u, i, b, e);
    if (r < l || r < b || e < l) return -1;
    if (l <= b && e <= r) {
        if (tree[u][i] <= v) return binGE(u, i, b, e, v, up);
        lazy[u][i] += up;
        propagate(u, i, b, e);
        return -1;
    }
    int m = (b + e) / 2;
    int t = findGE(u, i * 2 + 1, b, m, l, r, v, up);
    if (t != -1) {
        tree[u][i] = min(tree[u][i * 2 + 1], tree[u][i * 2 + 2]);
        return t;
    }
    t = findGE(u, i * 2 + 2, m + 1, e, l, r, v, up);
    tree[u][i] = min(tree[u][i * 2 + 1], tree[u][i * 2 + 2]);
    return t;
}

char a[100006];
int n, q, res;

void ins(int u, int x) {
    int it = findGE(u, 0, 0, n, x, n, -1, 1);
    if (it == -1 || it >= n) return;
    res++;
}

void rem(int u, int x) {
    int it = findGE(u, 0, 0, n, x, n - 1, 0, -1);
    if (it == -1 || it >= n) return;
    res--;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    memset(tree, -1, sizeof tree);
    cin >> a >> q;
    n = strlen(a);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < a[i] - 'a'; j++) {
            ins(j, i);
            ins(j, i);
            res--;
        }
    }
    cout << res << '\n';
    for (int i = 0; i < q; i++) {
        int x;
        char t;
        cin >> x >> t;
        x--;
        for (int j = a[x] - 'a'; j < t - 'a'; j++) {
            ins(j, x);
            ins(j, x);
            res--;
        }
        for (int j = t - 'a'; j < a[x] - 'a'; j++) {
            rem(j, x);
            rem(j, x);
            res++;
        }
        a[x] = t;
        cout << res << '\n';
    }
}

소감

 전체적으로 제 실력보다 잘 봤다고 생각해 굉장히 만족스럽습니다. 이번이 제 마지막 KOI인데, 처음으로 네 문제를 모두 해결하며 굉장히 만족스럽게 마무리할 수 있어서 다행입니다. 동시에 2차 대회 금상도 처음 받기 때문에 개인적으로 매우 의미가 깊습니다. 그러나 한편으로는 전체 2등을 했다는 점이 아쉬운 것은 어쩔 수 없나 봅니다. 만점자가 다섯 명인 것으로 알고 있는데, 이로 미루어 보아 문제는 예년보다 쉬웠다고 생각합니다.

결과

 전체 2위로 금상을 수상했습니다.

스케이트 연습

문제

부분 문제 5

 매 중간 지점에서 속력은 임의의 값만큼 증가하거나 1 감소합니다. 이를 뒤집어, 도착 지점에서 시작해 중간 지점들을 거꾸로 지나 시작 지점에 도착한다고 생각하면, 속력이 1 증가하거나 임의의 값만큼 감소할 것입니다. 또한, 각 중간 지점에 속력 제한 \(V_i\)가 있으므로 그보다 빨리 갈 수는 없습니다. 도착 지점에서 시작해 시작 지점으로 가는 동안 다음의 경우가 생길 수 있습니다.

1. \(V_i\)가 현재 속력보다 큽니다. 이때에는 속력이 클수록 이득이므로 속력을 1 증가시킵니다.
2. \(V_i\)가 현재 속력보다 작거나 같습니다. 이때에는 \(V_i\)의 속력을 초과할 수 없으므로 현재 속력을 \(V_i\) 이하로 낮추어야 합니다. 이때 속력이 클수록 이득이므로, \(V_i\) 미만으로 낮추는 것은 의미 없습니다. 따라서 정확히 \(V_i\)로 낮추어야 합니다.

 이를 시뮬레이션하여 매 중간 지점의 속력을 더하여 문제를 해결할 수 있습니다. 시간 복잡도는 \(O(N)\)입니다.

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

int n, a[500006];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + n - 1 - i);
    int v = 0;
    long long res = 0;
    for (int i = 0; i < n; i++) {
        ++v;
        v = min(v, a[i]);
        res += v;
    }
    printf("%lld", res);
}

지그재그

문제

부분 문제 4

 매 \(g(z)\)의 값을 \(O(N)\) 시간에 계산하면 됩니다. 이는 \(f(x, y, z)\)의 값이 다음 원소의 개수와 같기 때문입니다.

• 첫 원소와 마지막 원소
• 이전 원소와 이 원소, 그리고 이 원소와 다음 원소의 대소 관계가 반대인 원소

 이는 임의의 지그재그 부분 수열이 주어졌을 때 각 원소의 위치를 적절히 조절하여, 양옆 원소에 비해 값이 큰 원소의 값을 더 크게 하고, 값이 더 작은 원소의 값을 더 작게 함으로써 길이가 같은 지그재그 부분 수열을 만들어 낼 수 있기 때문입니다.

 이제 \(g(z)\)의 값의 계산은 다음과 같이 진행합니다.

1. \(A_i\leq z\)인 \(A_i\)만을 차례로 나열합니다.
2. 이전 원소와 이 원소, 그리고 이 원소와 다음 원소의 대소 관계가 반대인 원소들을 찾습니다.
3. 첫 원소와 마지막 원소와 더불어, 찾은 원소들의 개수를 셉니다. 이 값이 \(g(z)\)입니다.

 각 과정이 \(O(N)\) 시간이 걸리므로 전체 시간 복잡도는 \(O(N^2)\)입니다.

부분 문제 5

 부분 문제 4와 달리, 매 \(g(z)\)의 값을 독립적으로 계산하면 안 됩니다. \(z\)의 값을 1부터 \(N\)까지 증가시키며 \(g(z)\)를 찾는 과정에서, 이전에 찾은 값을 이용할 것입니다. 이를 위해서는 \(z\)의 값이 1 증가했을 때 생기는 변화량을 알아야 합니다. 이를 위해 각 원소가 \(f(x, y, z)\)에 얼마나 영향을 주는지 알아보겠습니다. 편의상 모든 인덱스는 0부터 시작합니다.

1. 이전 원소와 이 원소, 그리고 이 원소와 다음 원소의 대소 관계가 반대인 원소: 이 원소를 포함하면 지그재그 부분 수열의 최대 길이가 1 증가합니다. 따라서, 이 원소의 인덱스가 \(i\)일 때 \(f(x, y, z)\)에 주는 영향은 \((i+1)(N-i)\)입니다.
2. 1.에 해당하지 않는 원소: 이 원소가 \(f(x, y, z)\)에 주는 영향은 이 원소를 첫 원소로 포함하는 부분 수열의 개수와 마지막 원소로 포함하는 부분 수열의 개수의 합에 이 둘 모두에 해당하는 부분 수열의 개수를 뺀 값입니다. 이때 둘 모두에 해당하는 부분 수열의 개수는 이 원소 하나만 포함하는 부분 수열 하나뿐입니다. 이 원소의 인덱스가 \(i\), 이 원소 이전에 마지막으로 1.에 해당한 원소의 인덱스가 \(p\)(없으면 -1), 그리고 이 원소 다음에 처음으로 1.에 해당하는 원소의 인덱스가 \(q\)(없으면 \(N\))일 때 이 원소를 첫 원소로 포함하는 부분 수열의 개수는 \((i-p)(N-i)\)이며 이 원소를 마지막 원소로 포함하는 부분 수열의 개수는 \((i+1)(q-i)\)입니다. 따라서 이 원소가 \(f(x, y, z)\)에 주는 영향은 \((i-p)(N-i)+(i+1)(q-i)-1\)입니다.

 이때, 하나의 원소의 값이 바뀌었을 때 각 원소가 \(f(x, y, z)\)에 주는 영향이 바뀌는 원소는 값이 바뀐 원소를 기준으로 앞뒤 두 개씩 모두 다섯 개입니다. 다섯 원소에 대하여 위 1.과 2.에 해당하는 영향을 갱신해 주면 문제를 해결할 수 있습니다. 자세한 구현은 std::set을 이용해 \(O(N\log N)\)에 이루어집니다.

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

int n, a[200006], idx[200006];
bool imp[200006];
long long update1[200006], sum1;
long long update2[200006], sum2;
set<int> s;

void up1(int x) {
    int pv = *--s.find(x), nx = *++s.find(x);
    imp[x] = pv != -1 && nx != n && (a[pv] < a[x]) != (a[x] < a[nx]);
    sum1 -= update1[x];
    if (imp[x]) update1[x] = 1LL * (x + 1) * (n - x);
    else update1[x] = 0;
    sum1 += update1[x];
}

void up2(int x) {
    int pv = *--s.find(x), nx = *++s.find(x);
    sum2 -= update2[x];
    if (imp[x]) update2[x] = 0;
    else update2[x] = 1LL * (x - pv) * (n - x) + 1LL * (x + 1) * (nx - x) - 1LL * (x - pv) * (nx - x);
    sum2 += update2[x];
}

void up(int x) {
    up1(x);
    up2(x);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i), a[i]--;
    for (int i = 0; i < n; i++) idx[a[i]] = i;
    s.insert(-1);
    s.insert(n);
    for (int i = 0; i < n; i++) {
        s.insert(idx[i]);
        int pv = *--s.find(idx[i]);
        int nx = *++s.find(idx[i]);
        up(idx[i]);
        if (pv != -1) {
            up(pv);
            int ppv = *--s.find(pv);
            if (ppv != -1) up(ppv);
        }
        if (nx != n) {
            up(nx);
            int nnx = *++s.find(nx);
            if (nnx != n) up(nnx);
        }
        printf("%lld\n", sum1 + sum2);
    }
}

잔디밭의 개미굴

문제

부분 문제 5

 모든 가능한 배치에서 개미가 반드시 살아야 하는 방의 개수를 \(k\)라고 합시다. 추가할 수 있는 통로를 분류하겠습니다.

• 통로가 연결하는 두 방 모두에 개미가 반드시 살아야 하는 \(_{k}\mathrm{C}_2\) 가지의 경우: 어떻게 해도 개미를 적절히 재배치하여 조건에 맞게 할 수 없습니다.
• 통로가 연결하는 두 방 중 하나 이상에 개미가 반드시 살지 않아도 되는 \(_{N}\mathrm{C}_2-_{k}\mathrm{C}_2\) 가지의 경우: 두 방 중 하나 이상에 개미가 살지 않는 경우의 배치로 개미를 재배치하여 조건에 맞게 할 수 있습니다.

 따라서 문제의 답은 \(_{N}\mathrm{C}_2-_{k}\mathrm{C}_2\)입니다. \(k\)의 값을 구하면 이 값을 구할 수 있습니다. 이는 트리에서의 동적 계획법의 역추적을 통해 가능합니다. 다음과 같은 동적 계획법을 정의합니다.

• \(f_{i,\,0}\): \(i\) 번 방에 개미를 배치하지 않을 때, \(i\) 번 방의 서브 트리에 배치되는 개미의 수의 최댓값
• \(f_{i,\,1}\): \(i\) 번 방에 개미를 배치할 때, \(i\) 번 방의 서브 트리에 배치되는 개미의 수의 최댓값

 이때 \(f\)는 다음과 같이 계산됩니다.

$$f_{i,\,j}=\begin{cases}\sum \max(f_{\text{child}(i),\,0},f_{\text{child}(i),\,1})&j=0\\\sum f_{\text{child}(i),\,0})&j=1\end{cases}$$

 이 동적 계획법 배열을 얻은 뒤, 이를 역추적하여 각 방에 개미가 반드시 살아야 하는지를 알 수 있습니다. 전체 시간 복잡도는 \(O(N)\)입니다.

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

int n, dp[250006][2], pv[250006];
vector<int> adj[250006];
bool visited[250006][2];

int f(int x, int y, int prev = -1) {
    if (dp[x][y] + 1) return dp[x][y];
    dp[x][y] = y;
    for (auto &i: adj[x]) if (i != prev) {
        if (y) dp[x][y] += f(i, 0, x);
        else if (f(i, 0, x) > f(i, 1, x)) dp[x][y] += f(i, 0, x);
        else dp[x][y] += f(i, 1, x);
    }
    return dp[x][y];
}

void g(int x, int y, int prev = -1) {
    if (visited[x][y]) return;
    visited[x][y] = true;
    pv[x] = min(pv[x], y);
    for (auto &i: adj[x]) if (i != prev) {
        if (y) g(i, 0, x);
        else if (f(i, 0, x) > f(i, 1, x)) g(i, 0, x);
        else if (f(i, 0, x) < f(i, 1, x)) g(i, 1, x);
        else g(i, 0, x), g(i, 1, x);
    }
}

int main() {
    memset(dp, -1, sizeof dp);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) pv[i] = 1;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if (f(0, 0) > f(0, 1)) g(0, 0);
    else if (f(0, 0) < f(0, 1)) g(0, 1);
    else g(0, 0), g(0, 1);
    int cnt = 0;
    for (int i = 0; i < n; i++) cnt += pv[i];
    printf("%lld", 1LL * n * (n - 1) / 2 - 1LL * cnt * (cnt - 1) / 2);
}

바보 자물쇠

문제

부분 문제 5

\(Q\leq 10\)입니다. 각 쿼리를 선형 시간에 풀어도 무방합니다. 다음과 같은 동적 계획법을 이용합니다. 편의상 알파벳 소문자의 개수를 \(C\)로 두겠습니다.

• \(f_{i,\,j}\): \(i\) 째 문자가 \(j\)일 때 \(i\) 째 이하 문자들에 시행해야 하는 연산의 최소 횟수

 이는 전체 상태의 개수가 \(O(CN)\)이고 각 전이마다 \(O(C)\)의 시간이 걸리므로 전체 시간 복잡도가 \(O(C^2N)\)이라고 생각할 수 있지만, 여기에서 동적 계획법 식을 하나 더 정의하여 \(C\) 항을 하나 제거할 수 있습니다.

• \(f_{i,\,j}\): \(i\) 째 문자가 \(j\)일 때 \(i\) 째 이하 문자들에 시행해야 하는 연산의 최소 횟수
• \(g_{i,\,j}\): \(i\) 째 문자가 \(j\) 이하일 때 \(i\) 째 이하 문자들에 시행해야 하는 연산의 최소 횟수

 상태 전이 식은 다음과 같습니다.

$$f_{i,\,j}=\begin{cases}\min(g_{i-1,\,j})+|S_i-j|&i>1\\|S_i-j|&i=1\end{cases}$$

$$g_{i,\,j}=\begin{cases}\min(f_{i,\,j},g_{i,\,j-1})&j>\text{‘a'}\\f_{i,\,j}&j=\text{‘a'}\end{cases}$$

 이를 구현하여 \O(CN)\) 풀이를 얻을 수 있습니다.

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

int dp[100006][26];
char s[100006];
int n, q;

void solve() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) dp[i][j] = abs(s[i] - 'a' - j) + (i ? dp[i - 1][j] : 0);
        for (int j = 1; j < 26; j++) dp[i][j] = min(dp[i][j], dp[i][j - 1]);
    }
    int res = *min_element(dp[n - 1], dp[n - 1] + 26);
    printf("%d\n", res);
}

int main() {
    scanf("%s%d", s, &q);
    n = strlen(s);
    solve();
    for (int i = 0; i < q; i++) {
        int x;
        char t;
        scanf("%d %c", &x, &t);
        x--;
        s[x] = t;
        solve();
    }
}

부분 문제 6

 부분 문제 5의 식을 유심히 보면, 크기 26의 배열에 대하여 다음과 같은 과정으로 계산될 수 있음을 알 수 있습니다.

• 각 원소에 \(|S_i-j|\)를 더한다.
• 각 원소를 누적 최솟값으로 바꾼다.

 따라서, 이 배열의 인덱스에 따른 값의 기울기를 보면, 기울기가 음수에서 점차 증가하여 결국 0에 도달하는 것을 알 수 있습니다. 그리고 구하는 값은 0에 도달하는 수렴값이 됩니다. 이를 통해 a, b만 등장하는 경우를 해결합시다. 기울기를 관리하고 있다는 가정하에서 위의 과정은 다음 과정으로 변환됩니다. 앞으로 기울기의 절댓값만을 고려하겠습니다.

• \(S_i=\text{‘a'}\)이면 \(|S_i-j|=\begin{cases}0&j=0\\1&j=1\end{cases}\)입니다. 따라서, 기울기에서 1을 빼고 답에 1을 더합니다.
• \(S_i=\text{‘b'}\)이면 \(|S_i-j|=\begin{cases}1&j=0\\0&j=1\end{cases}\)입니다. 따라서, 기울기에 1을 더합니다.

 이제 이 일련의 과정에서 변화하는 기울기의 목록을 세그먼트 트리로 관리하여 쿼리를 처리할 수 있습니다.

• a를 b로 바꾸는 쿼리의 경우 주어진 인덱스에서 시작하여 a로 인해 기울기가 0이 되기 전까지 기울기에 1을 더합니다. 이를 2회 반복하고 답에 1을 더합니다.
• b를 a로 바꾸는 쿼리의 경우 주어진 인덱스에서 시작하여 a로 인해 기울기가 0이 되기 전까지 기울기에서 1을 뺍니다. 이를 2회 반복하고 답에서 1을 뺍니다.

 이는 느리게 갱신되는 세그먼트 트리와 세그먼트 트리에서의 이분 탐색을 이용해 해결할 수 있습니다. 시간 복잡도는 \(O(N\log N)\)입니다.

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

int tree[262144], lazy[262144];

void propagate(int i, int b, int e) {
    if (b != e) for (auto j: { i * 2 + 1, i * 2 + 2 }) lazy[j] += lazy[i];
    tree[i] += lazy[i];
    tree[i] = max(tree[i], -1);
    lazy[i] = 0;
}

int query(int i, int b, int e, int l, int r) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return (int)1e9;
    if (l <= b && e <= r) return tree[i];
    int m = (b + e) / 2;
    return min(query(i * 2 + 1, b, m, l, r), query(i * 2 + 2, m + 1, e, l, r));
}

int update(int i, int b, int e, int l, int r, int v) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return tree[i];
    if (l <= b && e <= r) {
        lazy[i] = v;
        propagate(i, b, e);
        return tree[i];
    }
    int m = (b + e) / 2;
    return tree[i] = min(update(i * 2 + 1, b, m, l, r, v), update(i * 2 + 2, m + 1, e, l, r, v));
}

int binGE(int i, int b, int e, int v) {
    propagate(i, b, e);
    if (b == e) {
        if (tree[i] <= v) return b;
        else return -1;
    }
    int m = (b + e) / 2;
    propagate(i * 2 + 1, b, m);
    if (tree[i * 2 + 1] <= v) return binGE(i * 2 + 1, b, m, v);
    else return binGE(i * 2 + 2, m + 1, e, v);
}

int findGE(int i, int b, int e, int l, int r, int v) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return -1;
    if (l <= b && e <= r) {
        if (tree[i] <= v) return binGE(i, b, e, v);
        return -1;
    }
    int m = (b + e) / 2;
    int t = findGE(i * 2 + 1, b, m, l, r, v);
    if (t != -1) return t;
    return findGE(i * 2 + 2, m + 1, e, l, r, v);
}

char a[100006];
int n, q, res, cntb;

void ins(int x) {
    int it = findGE(0, 0, 131071, x, n, -1);
    if (it == -1 || it >= n) {
        update(0, 0, 131071, x, n - 1, 1);
        return;
    }
    update(0, 0, 131071, x, it, 1);
    res++;
}

void rem(int x) {
    int it = findGE(0, 0, 131071, x, n - 1, 0);
    if (it == -1 || it >= n) {
        update(0, 0, 131071, x, n - 1, -1);
        return;
    }
    update(0, 0, 131071, x, it, -1);
    res--;
}

int main() {
    memset(tree, -1, sizeof tree);
    scanf("%s%d", a, &q);
    n = strlen(a);
    for (int i = 0; i < n; i++) if (a[i] == 'b') {
        ins(i), ins(i);
        cntb++;
    }
    printf("%d\n", res - cntb);
    for (int i = 0; i < q; i++) {
        int x;
        char t;
        scanf("%d %c", &x, &t);
        x--;
        if (a[x] == t) {
            printf("%d\n", res - cntb);
            continue;
        }
        a[x] = t;
        if (t == 'b') ins(x), ins(x), cntb++;
        else rem(x), rem(x), cntb--;
        printf("%d\n", res - cntb);
    }
}

부분 문제 9

 전체 문제는 a, b만의 상황을 \(O(C)\)회 시행하여 해결할 수 있습니다. 부분 문제 6에서 기울기가 갱신되는 과정을 살펴보면 문자 간의 종속성이 없으므로, 다음 \(O(C)\) 가지의 상황을 각각 시행하면 됩니다.

• a의 경우 기울기에서 1을 빼고, b, c, \(\cdots\)의 경우 기울기에 1을 더하는 상황
• a, b의 경우 기울기에서 1을 빼고, c, d, \(\cdots\)의 경우 기울기에 1을 더하는 상황
• \(\vdots\)
• a, b, \(\cdots\), y의 경우 기울기에서 1을 빼고, z의 경우 기울기에 1을 더하는 상황

 시간 복잡도는 \(O(CN\log N)\)입니다.

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <tuple>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int tree[25][262144], lazy[25][262144];

void propagate(int u, int i, int b, int e) {
    if (!lazy[u][i]) return;
    if (b != e) for (auto j: { i * 2 + 1, i * 2 + 2 }) lazy[u][j] += lazy[u][i];
    tree[u][i] += lazy[u][i];
    tree[u][i] = max(tree[u][i], -1);
    lazy[u][i] = 0;
}

int query(int u, int i, int b, int e, int l, int r) {
    propagate(u, i, b, e);
    if (r < l || r < b || e < l) return (int)1e9;
    if (l <= b && e <= r) return tree[u][i];
    int m = (b + e) / 2;
    return min(query(u, i * 2 + 1, b, m, l, r), query(u, i * 2 + 2, m + 1, e, l, r));
}

int binGE(int u, int i, int b, int e, int v, int up) {
    propagate(u, i, b, e);
    if (b == e) {
        if (tree[u][i] <= v) {
            lazy[u][i] += up;
            propagate(u, i, b, e);
            return b;
        } else return -1;
    }
    int m = (b + e) / 2;
    propagate(u, i * 2 + 1, b, m);
    if (tree[u][i * 2 + 1] <= v) {
        int t = binGE(u, i * 2 + 1, b, m, v, up);
        tree[u][i] = min(tree[u][i * 2 + 1], tree[u][i * 2 + 2]);
        return t;
    } else {
        lazy[u][i * 2 + 1] += up;
        propagate(u, i * 2 + 1, b, m);
        int t = binGE(u, i * 2 + 2, m + 1, e, v, up);
        tree[u][i] = min(tree[u][i * 2 + 1], tree[u][i * 2 + 2]);
        return t;
    }
}

int findGE(int u, int i, int b, int e, int l, int r, int v, int up) {
    propagate(u, i, b, e);
    if (r < l || r < b || e < l) return -1;
    if (l <= b && e <= r) {
        if (tree[u][i] <= v) return binGE(u, i, b, e, v, up);
        lazy[u][i] += up;
        propagate(u, i, b, e);
        return -1;
    }
    int m = (b + e) / 2;
    int t = findGE(u, i * 2 + 1, b, m, l, r, v, up);
    if (t != -1) {
        tree[u][i] = min(tree[u][i * 2 + 1], tree[u][i * 2 + 2]);
        return t;
    }
    t = findGE(u, i * 2 + 2, m + 1, e, l, r, v, up);
    tree[u][i] = min(tree[u][i * 2 + 1], tree[u][i * 2 + 2]);
    return t;
}

char a[100006];
int n, q, res;

void ins(int u, int x) {
    int it = findGE(u, 0, 0, n, x, n, -1, 1);
    if (it == -1 || it >= n) return;
    res++;
}

void rem(int u, int x) {
    int it = findGE(u, 0, 0, n, x, n - 1, 0, -1);
    if (it == -1 || it >= n) return;
    res--;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    memset(tree, -1, sizeof tree);
    cin >> a >> q;
    n = strlen(a);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < a[i] - 'a'; j++) {
            ins(j, i);
            ins(j, i);
            res--;
        }
    }
    cout << res << '\n';
    for (int i = 0; i < q; i++) {
        int x;
        char t;
        cin >> x >> t;
        x--;
        for (int j = a[x] - 'a'; j < t - 'a'; j++) {
            ins(j, x);
            ins(j, x);
            res--;
        }
        for (int j = t - 'a'; j < a[x] - 'a'; j++) {
            rem(j, x);
            rem(j, x);
            res++;
        }
        a[x] = t;
        cout << res << '\n';
    }
}