$$100 + 90 + 65 + 0 = 255$$점, 학내 $$rk7$$. 링크

T1

분류: 가볍게 풀 수 있는 문제 (노란색 난이도)

문제의 핵심은 반전 연산의 특성이다. 두 위치가 서로 다르다면, 그 중 하나만 바꾸는 것이 아니라, 인접한 두 위치가 서로 순서가 잘못되어 있을 때에만 동시에 교환하는 것이 최적임을 알 수 있다. 따라서 단순한 그리디 시뮬레이션으로 해결 가능하며, 시간 복잡도는 $$O(n)$$.

코드 보기

#include <bits/stdc++.h>
using namespace std;

string s1, s2;
int n, ans;

signed main() {
    cin >> n >> s1 >> s2;
    for (int i = 0; i < n; ++i) {
        if (s1[i] != s2[i]) {
            ++ans;
            if (i + 1 < n && s1[i+1] != s2[i+1] && s1[i+1] != s1[i]) {
                ++i;
            }
        }
    }
    cout << ans;
    return 0;
}

T2

분류: 정상적인 난이도 문제 (파란색 난이도)

문제를 재해석하면, 배열 $$a$$ 에서 $$m$$개의 인덱스를 선택하여, 모든 쌍 $$(i,j)$$ 에 대해 $$|p_j - p_i| < k$$ 이고, 각 선택된 위치에서 값 $$b_i \leq a_{p_i}$$, 그리고 $$b_i$$ 들이 모두 서로 달라야 한다. 또한, $$b_i$$ 를 최대화하되, 조건 내에서 가능한 배치 수를 구해야 한다.

이 경우, 선택된 인덱스들을 $$a_{p_i}$$ 기준으로 오름차순 정렬했을 때, 가능한 배치 수는 $$\prod_{i=1}^{m} (a_{p_i} - i + 1)$$ 로 표현된다. 이는 전에 선택된 $$i-1$$개의 위치가 이미 차지되었음을 의미한다.

이제 제약을 강화하여, $$a_{p_i} \geq i$$ 를 만족하도록 하면, 정렬 여부가 중요하지 않게 된다. 그리디로 판단할 수 있으며, 동적 계획법을 사용해 상태를 관리할 수 있다.

상태: $$f_{i,s}$$ — 첫 번째부터 $$i$$번째 원소까지 고려하고, 선택된 인덱스의 패턴이 비트 마스크 $$s$$ 일 때의 최대 배치 수.

전처리를 통해 $$O(nm2^m)$$ 에 해결 가능하며, 큰 수 연산을 위해 1억 단위로 압축한 고정밀도 정수를 사용하면, $$O(n m^2 2^m)$$ 으로 처리 가능하다.

경기 중 write 함수를 잘못 구현하여 10점만 획득.

코드 보기

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
int a[MAXN], n, m, k;
long long jw;

struct bigint {
    int a[10], n;

    friend bigint operator*(bigint x, int y) {
        if (x.n == 0) return x;
        jw = 0;
        for (int i = 0; i < x.n; ++i) {
            jw = 1LL * x.a[i] * y + jw;
            x.a[i] = jw % 1000000000;
            jw /= 1000000000;
        }
        while (jw) {
            ++x.n;
            x.a[x.n - 1] = jw % 1000000000;
            jw /= 1000000000;
        }
        return x;
    }
};

bigint f[MAXN][1024], mx[1024];

void chkmax(bigint& x, bigint y) {
    if (x.n < y.n) x = y;
    else if (x.n == y.n) {
        for (int i = x.n - 1; ~i; --i) {
            if (x.a[i] > y.a[i]) return;
            else if (x.a[i] < y.a[i]) {
                x = y;
                return;
            }
        }
    }
}

void out(bigint x) {
    if (x.n == 0) {
        cout << "1\n";
        return;
    }
    cout << x.a[x.n - 1];
    for (int i = x.n - 2; ~i; --i) {
        int cnt = 0, p = x.a[i];
        while (p) ++cnt, p /= 10;
        for (int j = 9; j > cnt; --j) cout << '0';
        if (x.a[i]) cout << x.a[i];
    }
    cout << '\n';
}

signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        for (int j = 0; j < (1 << m); ++j)
            f[i][j].n = 0;
    }

    for (int j = 0; j < (1 << m); ++j) mx[j].n = 0;
    mx[0].n = 1; mx[0].a[0] = 1;

    for (int i = 1; i <= n; ++i) {
        if (i - k > 0) {
            for (int j = 0; j < (1 << m); ++j)
                chkmax(mx[j], f[i - k][j]);
        }

        for (int mask = 0; mask < (1 << m) - 1; ++mask) {
            int limit = min(m - 1, a[i] - 1);
            for (int bit = limit; bit >= 0; --bit) {
                if ((mask & (1 << bit)) == 0) {
                    chkmax(f[i][mask ^ (1 << bit)], mx[mask] * (a[i] - bit));
                }
            }
        }
    }

    for (int i = n - k + 1; i <= n; ++i)
        chkmax(mx[(1 << m) - 1], f[i][(1 << m) - 1]);

    out(mx[(1 << m) - 1]);
    return 0;
}

T3

분류: 상대적으로 간단 (초록~파랑 난이도)

집합을 비우는 조건은 다음과 같다: 집합 크기가 짝수이고, 가장 많이 등장하는 원소의 빈도가 전체 크기의 절반 미만이어야 한다.

모든 가능한 최빈값 $$x$$ 를 고려한다. $$a_i = x$$ 인 원소는 $$-1$$, 그렇지 않은 원소는 $$1$$ 로 치환한다. 그러면, 짝수 크기의 연결 요소 개수에서, $$x$$ 의 빈도가 절반 이상인 짝수 크기 연결 요소를 빼면 답이 된다.

첫 번째 부분은 $$O(n^2)$$ 에 처리 가능. 두 번째 부분은 트리 위에서의 동적 계획법을 사용하며, $$f_{i,2j}$$ 의 합을 계산하여 감소시킨다. 전체 복잡도는 $$O(n \sum_x cnt_x) = O(n^2)$$.

경기 중 트리 DP의 복잡도를 잘못 추정하여 실수.

코드 보기

#include <bits/stdc++.h>
char *p1, *p2, buf[1 << 21];
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;

const int MAXN = 5510, mod = 1e9 + 7;
int a[MAXN], n, k, head[MAXN], g[MAXN][2], cnt[MAXN], q;
int ans, mx, f[MAXN][MAXN << 1], tot, sz[MAXN], b[MAXN << 1];
struct edge {
    int v, nxt;
} e[MAXN];

void adde(int u, int v) {
    e[++k] = {v, head[u]};
    head[u] = k;
}

void dp(int u) {
    g[u][1] = 1;
    for (int i = head[u], v; i; i = e[i].nxt) {
        v = e[i].v;
        dp(v);
        int x = g[u][1];
        g[u][1] = (1LL * g[u][1] * (g[v][0] + 1) + 1LL * g[u][0] * g[v][1]) % mod;
        g[u][0] = (1LL * x * g[v][1] + 1LL * g[u][0] * (g[v][0] + 1)) % mod;
    }
    ans += g[u][0];
    if (ans >= mod) ans -= mod;
}

void dfs(int u) {
    f[u][q + (a[u] == tot ? 1 : -1)] = sz[u] = 1;
    for (int i = head[u], v; i; i = e[i].nxt) {
        v = e[i].v;
        dfs(v);
        for (int j = -min(sz[v], q); j <= min(sz[v], q); ++j) {
            if (!f[v][q + j]) continue;
            if (j < 0) {
                for (int k = q - min(sz[u], q); k <= q + min(sz[u], q); ++k) {
                    if (!f[u][k]) continue;
                    b[k + j] = (b[k + j] + 1LL * f[u][k] * f[v][q + j]) % mod;
                }
            } else {
                for (int k = q + min(sz[u], q); k >= q - min(sz[u], q); --k) {
                    if (!f[u][k]) continue;
                    b[k + j] = (b[k + j] + 1LL * f[u][k] * f[v][q + j]) % mod;
                }
            }
            f[v][q + j] = 0;
        }
        sz[u] += sz[v];
        for (int i = q - min(sz[u], q); i <= q + min(sz[u], q); ++i) {
            f[u][i] += b[i];
            b[i] = 0;
            if (f[u][i] >= mod) f[u][i] -= mod;
        }
    }
    for (int i = q + 2; i <= 2 * q; i += 2)
        ans = (ans - f[u][i] + mod) % mod;
}

int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

signed main() {
    n = read();
    for (int i = 2, x; i <= n; ++i) {
        x = read();
        adde(x, i);
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        ++cnt[a[i]];
        mx = max(mx, a[i]);
    }

    dp(1);

    for (tot = 1; tot <= mx; ++tot) {
        q = cnt[tot];
        dfs(1);
        for (int j = 0; j <= q * 2; ++j)
            f[1][j] = 0;
    }

    cout << ans << endl;
    return 0;
}

T4

분류: 매우 어려움 — 경기 중 포기. 후속 보완 필요.

종합 평가

전반적인 집중력은 유지되었으나, 세부 사항 처리와 복잡도 분석 능력이 보완 필요.