Codeforces Round #1068 (Div. 2) 후기

A. Sleeping Through Classes

풀이 보기

풀이

이 문제는 수업 중에 조는 횟수를 최대화하는 문제다. 문자열에서 1은 반드시 깨어 있어야 하는 수업을 의미하며, 한 번 깨어나면 이후 $k$개(총 $k+1$개)의 수업 동안은 졸 수 없다는 제약이 있다.

1. 문자열을 순회하면서 1을 만날 경우, 현재 인덱스 $i$부터 $i+k$까지는 “졸 수 없는 구간”으로 설정한다 (cant_skip = i + k + 1)
2. 현재 인덱스가 cant_skip보다 작다면 해당 수업은 강제로 들어야 하므로 건너뛴다
3. 만약 0이면서 현재 인덱스가 cant_skip 이상이라면, 해당 수업 시간에는 졸 수 있으므로 카운트를 증가시킨다

코드

#include <stdio.h>

#define MAX_LEN 100
char str[MAX_LEN + 1];
int n, k;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %s", &n, &k, str);

        int cnt = 0;
        int cant_skip = 0;
        for (int i = 0; i < n; ++i) {
            if (str[i] == '1') {
                cant_skip = i + k + 1;
            } else if (i < cant_skip) {
                continue;
            } else {
                cnt += 1;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

B. Niko’s Tactical Cards

풀이 보기

풀이

매 턴마다 빨간색 카드 혹은 파란색 카드를 선택하여 점수를 업데이트할 때, 마지막 턴 이후 얻을 수 있는 최대 점수를 구하는 문제이다.

매 단계에서 가능한 점수의 최솟값(min_score)과 최댓값(max_score)의 범위를 관리하는 동적 계획법(DP) 방식으로 해결할 수 있다.

• 빨간색 카드를 선택할 경우: 새로운 점수는 old_score - red_card[i]
• 파란색 카드를 선택할 경우: 새로운 점수는 blue_card[i] - old_score​

이 두 가지 선택지에 대해 현재의 $[min, max]$ 범위를 대입하면 새로운 범위는 다음과 같이 갱신할 수 있다:

• new_min = min(old_min - red, blue - old_min)
• new_max = max(blue - old_min, old_max - red)​

최종적으로 $n$번의 턴을 모두 마친 후의 max_score를 출력하면 된다.

코드

#include <stdio.h>

typedef long long ll;

#define MAX_TURN (int)(1e5)

ll red_card[MAX_TURN];
ll blue_card[MAX_TURN];
int n;

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &red_card[i]);
        }
        for (int i = 0; i < n; i++) {
            scanf("%lld", &blue_card[i]);
        }

        ll min_score = 0LL;
        ll max_score = 0LL;

        for (int i = 0; i < n; ++i) {
            ll old_min = min_score;
            ll old_max = max_score;

            min_score = min(old_min - red_card[i], blue_card[i] - old_max);
            max_score = max(blue_card[i] - old_min, old_max - red_card[i]);
        }

        printf("%lld\n", max_score);
    }
    return 0;
}

C. Kanade’s Perfect Multiples

풀이 보기

풀이

주어진 집합의 모든 원소를 “특정 수 $b$의 배수”들의 합집합으로 표현할 수 있는 최소한의 $b$들을 찾는 문제이다.

1. 입력 정렬 및 중복 제거: 이진 탐색(lower_bound)을 활용하기 위해 입력받은 값들을 정렬하고 유일한 값들만 vals 배열에 저장한다
2. 후보 $b$ 검증: vals에 포함된 각 값 $b$에 대해 다음 조건을 확인한다
   • $k/b$의 몫이 최대 원소를 $b$로 나눈 몫과 같은지 확인하여 범위 내에 있는지 체크한다
   • $1 \cdot b, 2 \cdot b, \dots, (k/b) \cdot b$ 에 해당하는 모든 값들이 원래 집합(vals)에 포함되어 있는지 확인한다
   • 모두 포함되어 있다면 $b$는 Good한 base가 될 수 있으며, 해당 배수들을 Covered 상태로 표시한다
3. 정당성 확인: 모든 입력 원소 $a_i$가 어떤 $b$의 배수로서 Covered 되었는지 확인한다. 만약 하나라도 커버되지 않았다면 -1을 출력한다
4. 최소 base 선택: 중복된 커버리지를 피하기 위해, Good한 $b$들 중 다른 $b’$의 배수인 것들은 제외하고 가장 작은 단위의 $b$들만 선택하여 출력한다

코드

#include <stdio.h>
#include <stdlib.h>

typedef long long ll;

#define MAX_IDX (int)(2e5)

int a[MAX_IDX];
int vals[MAX_IDX];
int n;
ll k;

char is_good[MAX_IDX];
char is_covered[MAX_IDX];
char has_small[MAX_IDX];

int cmp_int(const void* p, const void* q) {
    int x = *(const int*)p;
    int y = *(const int*)q;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

int lower_bound(int* arr, int m, int x) {
    int lo = 0, hi = m;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (arr[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %lld", &n, &k);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            vals[i] = a[i];
        }
        qsort(vals, n, sizeof(int), cmp_int);
        int m = 0;
        for (int i = 0; i < n; ++i) {
            if (i == 0 || vals[i] != vals[i - 1]) vals[m++] = vals[i];
        }
        for (int i = 0; i < m; ++i) {
            is_good[i] = is_covered[i] = has_small[i] = 0;
        }
        int maxA = vals[m - 1];
        for (int i = 0; i < m; ++i) {
            int b = vals[i];
            ll qk = k / b;
            if (qk != (ll)maxA / b || qk > m) continue;
            int ok = 1;
            for (ll j = 1; j <= qk; ++j) {
                ll val = j * b;
                int pos = lower_bound(vals, m, (int)val);
                if (pos == m || vals[pos] != (int)val) { ok = 0; break; }
            }
            if (!ok) continue;
            is_good[i] = 1;
            for (ll j = 1; j <= qk; ++j) {
                int pos = lower_bound(vals, m, (int)(j * b));
                is_covered[pos] = 1;
            }
        }
        int possible = 1;
        for (int i = 0; i < n; ++i) {
            int pos = lower_bound(vals, m, a[i]);
            if (pos == m || vals[pos] != a[i] || !is_covered[pos]) { possible = 0; break; }
        }
        if (!possible) { printf("-1\n"); continue; }
        static int B[MAX_IDX];
        int Bcnt = 0;
        for (int i = 0; i < m; ++i) {
            if (!is_good[i] || has_small[i]) continue;
            int b = vals[i];
            B[Bcnt++] = b;
            for (ll val = 2LL * b; val <= maxA; val += b) {
                int pos = lower_bound(vals, m, (int)val);
                if (pos < m && vals[pos] == (int)val) has_small[pos] = 1;
            }
        }
        printf("%d\n", Bcnt);
        for (int i = 0; i < Bcnt; ++i) printf("%d%c", B[i], i == Bcnt - 1 ? '\n' : ' ');
    }
    return 0;
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#1068 (Div. 2)	2025/12/05 23:35	1861	3	+24	1570