서론

올해도 역시 AC 자동기 문제에서 고배를 마셨다. 사실 ST3 문제에서 AC 자동기 접근 방식이 매우 자연스럽게 떠올랐고, 절반 정도는 해결했음에도 불구하고 T4 문제로 방향을 틀어 결국 300점 이상의 고득점을 놓치고 말았다. Trie 트리와 실패(Fail) 포인터가 어쩌면 운명적인 조합처럼 느껴지지 않는가? 최종 결과는 100 + 100 + 20 + 0으로 아쉬운 성적으로 마무리됐다.

T1: 피아노 연주

문제 개요

길이가 \( n \)인 수열 \( a \)가 주어지고, 매개변수 \( k \)를 기준으로 새로운 수열 \( b \)를 구성한다:

• \( b_1 = a_1 \)
• \( a_{i-1} < a_i \) 이면 \( b_i = b_{i-1} + k \)
• \( a_{i-1} > a_i \) 이면 \( b_i = b_{i-1} - k \)
• 그 외에는 \( b_i = b_{i-1} \)

여기서 \( b \)의 점수는 \( \sum_{i=1}^{n} [a_i = b_i] \)이며, 이 점수를 최대화하는 \( k \) 값을 구해야 한다.

접근 방법

핵심은 수열 전체에 상수를 더하거나 빼도 결과에 영향을 주지 않는다는 점이다. 따라서 \( a_1 \)을 기준으로 모든 원소에서 \( a_1 \)을 빼서 \( a_1 = 0 \), \( b_1 = 0 \)으로 정규화할 수 있다.

이후 각 인덱스 \( i \)에 대해 \( b_i \) 값은 \( k \)의 배수 형태로 표현되며, \( a_i = b_i \cdot k \)가 성립해야만 점수가 증가한다. 이 조건을 만족하려면 \( k = a_i / b_i \)이고, 몫이 음수가 아니어야 한다.

모든 가능한 \( k \)값에 대해 점수를 세기 위해 맵(map)을 사용하여 등장 횟수를 카운팅하고, 가장 많은 점수를 주는 \( k \)를 선택하면 된다.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // a[1] 기준 정규화
    for (int i = 2; i <= n; ++i) a[i] -= a[1];
    a[1] = 0;

    vector<long long> b(n + 1);
    b[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (a[i-1] < a[i]) b[i] = b[i-1] + 1;
        else if (a[i-1] > a[i]) b[i] = b[i-1] - 1;
        else b[i] = b[i-1];
    }

    map<long long, int> scoreMap;
    int baseScore = 0;

    for (int i = 1; i <= n; ++i) {
        if (b[i] == 0) {
            if (a[i] == 0) baseScore++;
        } else if (a[i] % b[i] == 0 && a[i] / b[i] >= 0) {
            scoreMap[a[i] / b[i]]++;
        }
    }

    long long bestK = 0;
    int maxScore = baseScore;

    for (const auto& [k, score] : scoreMap) {
        if (score > maxScore) {
            maxScore = score;
            bestK = k;
        }
    }

    cout << maxScore << '\n' << bestK << '\n';
    return 0;
}

T2: 색상 필터 선택

문제 개요

각각 RGB 값을 가지는 \( n \)개의 삼원조가 주어진다. 두 튜플 간 거리는 다음과 같이 정의된다:

\[ \text{diff}(i,j) = \max(|R_i - R_j|, |G_i - G_j|, |B_i - B_j|) \]

여기서 \( k \)개의 튜플을 선택하여 이들 사이의 최대 diff 값을 최소화하는 문제다.

해결 전략

각 튜플을 3차원 공간의 점으로 해석하면, diff 값은 해당 점들을 모두 포함하는 최소 크기 정육면체의 한 변 길이와 같다. 즉, 모든 선택된 점이 어떤 정육면체 안에 들어가야 하며, 그 크기를 최소화해야 한다.

RGB 값의 범위가 0~255로 제한되어 있으므로, 전체 공간 탐색이 가능하다. 정육면체의 크기 \( d \)에 대해 이분 탐색을 수행하고, 각 후보 \( d \)에 대해 3차원 누적합 배열을 이용해 크기 \( d \)의 박스 내에 최소 \( k \)개의 점이 포함되는지 확인한다.

전처리로 3D 프리픽스 섬을 구성하고, 각 위치에서 \( (x+d, y+d, z+d) \)까지의 합을 계산하면 \( O(1) \)에 쿼리 가능하다. 전체 시간복잡도는 \( O(V^3 \log V) \)이며, \( V = 256 \)이므로 충분히 빠르다.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> points(n);
    int cube[257][257][257] = {};

    for (int i = 0; i < n; ++i) {
        cin >> points[i][0] >> points[i][1] >> points[i][2];
        cube[points[i][0]+1][points[i][1]+1][points[i][2]+1]++;
    }

    // 3D 프리픽스 섬
    for (int x = 1; x <= 256; ++x)
        for (int y = 1; y <= 256; ++y)
            for (int z = 1; z <= 256; ++z)
                cube[x][y][z] += cube[x][y][z-1];

    for (int x = 1; x <= 256; ++x)
        for (int y = 1; y <= 256; ++y)
            for (int z = 1; z <= 256; ++z)
                cube[x][y][z] += cube[x][y-1][z];

    for (int x = 1; x <= 256; ++x)
        for (int y = 1; y <= 256; ++y)
            for (int z = 1; z <= 256; ++z)
                cube[x][y][z] += cube[x-1][y][z];

    auto query = [&](int x1, int y1, int z1, int x2, int y2, int z2) {
        if (x1 < 0 || y1 < 0 || z1 < 0) return 0;
        int res = cube[x2][y2][z2];
        if (x1 > 0) res -= cube[x1-1][y2][z2];
        if (y1 > 0) res -= cube[x2][y1-1][z2];
        if (z1 > 0) res -= cube[x2][y2][z1-1];
        if (x1 > 0 && y1 > 0) res += cube[x1-1][y1-1][z2];
        if (x1 > 0 && z1 > 0) res += cube[x1-1][y2][z1-1];
        if (y1 > 0 && z1 > 0) res += cube[x2][y1-1][z1-1];
        if (x1 > 0 && y1 > 0 && z1 > 0) res -= cube[x1-1][y1-1][z1-1];
        return res;
    };

    int low = 0, high = 256;
    while (low < high) {
        int mid = (low + high) / 2;
        bool valid = false;
        for (int x = 0; x + mid <= 256; ++x)
            for (int y = 0; y + mid <= 256; ++y)
                for (int z = 0; z + mid <= 256; ++z) {
                    if (query(x, y, z, x+mid, y+mid, z+mid) >= k) {
                        valid = true;
                        break;
                    }
                }
        if (valid) high = mid;
        else low = mid + 1;
    }

    cout << low << '\n';
    return 0;
}

T3: 홍수 대피 계획

문제 설명

n개의 정점으로 구성된 트리에서 k개의 정점에 표시가 되어 있다. 각 정점에서 출발하여 모든 표시된 정점을 방문하고 멈추는 최단 경로의 길이를 구해야 하며, 경로 중간에 다시 돌아올 필요 없고, 간선은 여러 번 지나도 된다.

풀이 아이디어

정답은 다음 세 요소로 나뉜다:

1. 모든 표시된 정점을 포함하는 최소 연결 부분 트리 내의 간선 길이의 총합 × 2
2. 출발점에서 이 부분 트리까지의 거리 × 2
3. 출발점에서 가장 먼 표시된 정점까지의 거리

최종 답은 (1) + (2) - (3)이다. (1)과 (2)는 서브트리 탐색과 BFS로 쉽게 구할 수 있지만, (3)은 각 정점마다 다름으로 효율적인 처리가 필요하다.

DFS 도중 각 정점에서 다른 정점으로 이동할 때, 자식 서브트리에 속한 표시된 정점은 거리가 줄어들고, 그 외는 늘어난다. 이를 위해 각 표시된 정점의 DFS 방문 순서(dfn)를 기록하고, 세그먼트 트리를 통해 구간 갱신 및 최댓값 쿼리를 수행한다.

각 노드 진입 시 현재 상태에서 가장 먼 거리(세그먼트 트리의 글로벌 최댓값)를 저장하면, 그것이 그 정점에서의 (3)번 항목이 된다.

// 세그먼트 트리 클래스 생략 (lazy propagation 지원)
// 주요 로직만 요약

// 1. 표시된 정점 포함하는 최소 서브트리 찾기 (dfs1)
// 2. 그 서브트리로부터 모든 정점까지 거리 계산 (BFS)
// 3. dfn 배열 구성 및 세그먼트 트리 초기화
// 4. dfs3로 각 정점 방문 시 세그먼트 트리 업데이트 및 최댓값 저장

for (int i = 1; i <= n; ++i) {
    long long ans = cycleSum + 2 * distToCore[i] - maxDistFromStart[i];
    cout << ans << '\n';
}

마무리

T4 문제는 시간 부족으로 분석하지 못했으며, T3까지 해결하는 데 집중했다. 알고리즘 설계에서 관찰력과 자료구조 활용 능력이 여전히 부족함을 느꼈다. 특히 트리 문제에서의 동적 정보 관리 기법은 추가 학습이 필요하다.