결론 짧게:

100+0+0+0 점수.

T1: 소 Z의 장갑

문제 설명

길이가 \(n\)인 배열 \(a\)와 길이가 \(m\)인 배열 \(b\)가 주어집니다.

이 배열에서 \(\min(n,m)\)개의 쌍 \(a_i, b_j\)를 매칭해야 합니다. 각 숫자는 한 번만 매칭할 수 있습니다.

매칭의 비용은 \(|a_i - b_j|\)이며, 매칭 그룹의 비용은 이들 중 최댓값입니다. 이 최댓값을 최소화해야 합니다.

대회 당시

탐욕법 접근이 틀렸음을 인식하고 이진탐색으로 전환했습니다.

해결 방법

먼저, 탐욕법은 틀렸습니다. 이는 상한을 설정할 때만 적용할 수 있습니다.

최솟값을 찾기 위해 이진탐색을 사용합니다.

'체크' 함수를 통해 중간값이 유효한지 검증합니다.

정렬 후, 현재 수와 가장 가까운 수를 매칭시켜주는 방법을 사용합니다. 이 때, 더 큰 수로는 같은 위치를 매칭할 수 없습니다.

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
using namespace std;

int n, m;
long long arrA[100010];
long long arrB[100010];

bool isValid(long long mid) {
    int ptrB = 1;
    int count = 0;
    for (int ptrA = 1; ptrA <= n; ptrA++) {
        while (ptrB <= m && abs(arrA[ptrA] - arrB[ptrB]) > mid) {
            ptrB++;
        }
        if (ptrB == m + 1) break;
        ptrB++;
        count++;
    }
    return count == n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> arrA[i];
    for (int i = 1; i <= m; i++) cin >> arrB[i];
    sort(arrA + 1, arrA + 1 + n);
    sort(arrB + 1, arrB + 1 + m);

    if (n > m) {
        swap(n, m);
        swap(arrA, arrB);
    }

    long long left = 0, right = 2e9;
    while (left < right) {
        long long mid = (left + right) >> 1;
        if (isValid(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    cout << left << "\n";

    #ifndef ONLINE_JUDGE
    cerr << "\n 사용 시간: " << clock() * 1.0 / CLOCKS_PER_SEC << "초.\n";
    #endif
    return 0;
}

T2: 소 Z의 문자열

문제 설명

어떤 문자열을 주어받았을 때, 인접한 두 문자를 교환할 수 있습니다. 인접한 두 문자가 같은 것이 없도록 만들기 위해 최소의 교환 횟수를 구하세요.

대회 당시

넘어쳤습니다. 아무것도 작성하지 않았습니다.

해결 방법

\(dp_{i,j,k,l}\)를 통해 \(i\)번째 위치까지 고려했을 때, \(j\)개의 \(0\)와 \(k\)개의 \(1\)를 배치했고 마지막 문자가 \(l\)일 때의 최소 이동 횟수를 저장합니다.

이때, 상태 전환은 분명치 않습니다.

마지막에 mhh의 기록을 참고했습니다.

공간이 부족할 수 있어 첫번째 차원을 제거해야 합니다.

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
using namespace std;

int n;
int a[410];

vector<int> vec[3];

int dp[2][410][410][3]; // 이전 i, j x 0, k x 1, 마지막은 l.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    string s; cin >> s; n = s.length();
    for (int i = 1; i <= n; i++) a[i] = s[i-1] - '0';

    for (int i = 1; i <= n; i++) vec[a[i]].push_back(i);

    memset(dp[0], INF, sizeof dp[0]);

    for (int i = 0; i < 3; i++) dp[0][0][0][i] = 0;
    for (int i = 1; i <= n; i++) {
        memset(dp[i & 1], INF, sizeof(dp[i & 1]));

        for (int j = 0; j <= min(i, (int)vec[0].size()); j++) {
            for (int k = 0; k <= min(i, (int)vec[1].size()); k++) {
                int x = i - j - k;
                if (x > (int)vec[2].size()) continue;

                if (j) dp[i & 1][j][k][0] = min(dp[~i & 1][j-1][k][1], dp[~i & 1][j-1][k][2]) + abs(i - vec[0][j-1]);
                if (k) dp[i & 1][j][k][1] = min(dp[~i & 1][j][k-1][0], dp[~i & 1][j][k-1][2]) + abs(i - vec[1][k-1]);
                if (x) dp[i & 1][j][k][2] = min(dp[~i & 1][j][k][0], dp[~i & 1][j][k][1]) + abs(i - vec[2][x-1]);
            }
        }
    }

    int ans = INF;
    for (int i = 0; i < 3; i++) ans = min(ans, dp[n & 1][vec[0].size()][vec[1].size()][i]);
    if (ans == INF) cout << "-1\n";
    else cout << ans / 2 << "\n";

    #ifndef ONLINE_JUDGE
    cerr << "사용 시간: " << clock() * 1.0 / CLOCKS_PER_SEC << "초.\n";
    #endif
    return 0;
}

이상은 틀렸습니다.

呵呵, mhh의 방법이 hxf에 의해 해킹되었습니다.

그래서私も 그냥 패스했습니다.

더 자세히 알고 싶으면 JZ8의 블로그를 방문하세요.

요약

이번 대회는 정말 힘들었습니다. T3에서 선형 구조 분할을 사용한 사람들을 보면서 놀랐습니다.