제1회 블롭컵

 

문제 난이도 분포가 다양하여 생각보다는 많은 문제인 6솔을 했다.

 

컴퓨터 업데이트가 자동적으로 되어 날아갔다.... 다시 써본다...

 

 

 

Editorial

 

제1회 블롭컵 해설

 

 

A. blobnom

 

24498번: blobnom

 

각각의 높이가 주어진 N개의 탑이 있다.

 

i번째 탑에 대해, i + 1번째 탑과 i - 1번째 탑의 높이를 1씩 줄이고, i번째 탑의 높이를 1 높이는 operation이 있다.

 

(첫 번째 탑과 마지막 탑을 i번째로 고를 수는 없다.)

 

operation을 0번 이상하여 탑의 최대 높이를 구하여라.

 

 

\( max \) \( h_i + min(h_{i - 1}, h_{i + 1}) \) 을 구하면 된다.

 

첫 번째와 마지막 탑의 경우 min 부분 없이 고려한다.

 

 

 

B. blobyum

 

24499번: blobyum

 

N개의 애플파이가 원 모양으로 배치되어 있다.

 

각각 애플파이의 맛있는 정도가 주어진다.

 

연속된 K개를 먹는다고 하였을 때 맛있는 정도의 합의 최댓값을 구하여라.

 

 

애플파이가 원형으로 배치되어 있기 때문에 N개 애플파이를 2N - 1개로 확장시켜 생각한다.

 

\( a_i = a_{i - N} \) for \( N + 1 \leq i \leq 2N \)

 

그리고 누적값을 계산한다.

 

그리고 배열을 순회하며 K개만큼의 합의 최댓값을 구하면 된다.

 

 

 

C. blobblush

 

24500번: blobblush

 

1부터 \( N \) 까지의 양의 정수가 적힌 숫자 카드가 있다.

 

다음과 같은 조건으로 카드를 뽑을 때, 뽑는 카드의 수와 적힌 각 수를 구하여라.

• 뽑은 카드들에 적힌 수를 모두 ⊕한 값이 최대가 되어야 한다. ⊕는 배타적 논리합(xor)을 의미한다.
• 첫 번째 조건에 맞게 카드를 뽑는 방법이 여러 가지인 경우, 카드를 최대한 적게 뽑아야 한다.
• 두 번째 조건에 맞게 카드를 뽑는 방법이 여러 가지인 경우, 사전 순으로 가장 앞서도록 뽑아야 한다.

 

 

\( N \) 을 이진수로 표현하였을 때의 길이를 n이라고 하였을 때, 1부터 \( N \)까지의 카드를 뽑아 xor하여 만들 수 있는 최댓값은 \( 2^n - 1 \)이다.

 

따라서 \( N \)이 \( 2^n - 1 \)이라면 \( N \)만 뽑으면 된다.

 

그렇지 않다면, 조건에 부합하도록 \( 2^n - 1 - N \)과 \( N \)을 뽑으면 된다.

 

 

 

D. blobaww

 

24501번: blobaww

 

문자 E, S, M으로 구성된 N x M 2차원 행렬이 있다. (그 행렬을 \( ESM \) 이라고 하자)

 

\( ESM_{x_1, y_1} = E \), \( ESM_{x_2, y_2} = S \), \( ESM_{x_3, y_3} = M \) ( \( 1 \leq x_1 \leq x_2 \leq x_3 \leq N \), \( 1 \leq y_1 \leq y_2 \leq y_3 \leq M \) ) 을 만족하는 \( (x_1, y_1) \), \( (x_2, y_2) \), \( (x_3, y_3) \) 의 쌍의 개수를 구하여라.

 

 

2차원 누적값을 구하는 것을 3번 반복하면 된다.

 

처음에는 E의 개수를 누적하여 2차원 배열으로 만든다.

 

\( E_{x, y} \) = \( \| \{ (x_1, y_1) | ESM_{x_1, y_1} = E, 1 \leq x_1 \leq x, 1 \leq y_1 \leq y \} \| \)

 

그런다음 위 배열을 이용하여 다음을 만족하는 \( (x_1, y_1) \), \( (x_2, y_2) \) 쌍의 개수를 누적하여 2차원 배열으로 만든다.

 

\( S_{x, y} \) = \( \| \{ ( (x_1, y_1), (x_2, y_2) ) | ESM_{x_1, y_1} = E, ESM_{x_2, y_2} = S, 1 \leq x_1 \leq x_2 \leq x, 1 \leq y_1 \leq y_2 \leq y \} \| \)

 

그런다음 위 배열을 이용하여 \( (x_1, y_1) \), \( (x_2, y_2) \), \( (x_3, y_3) \) 쌍의 개수를 구해준다.

 

 

 

E. blobsad

 

24502번: blobsad

 

1 x 1 정사각형 \( N \)개로 나누어진 1 x \( N \) 크기의 직사각형 통 안에 블롭을 키우고 있다.

 

i번째 1 x 1 정사각형에는 블롭 \( a_i \)마리를 키운다.

 

1초마다 하나의 블롭을 인접한 칸으로 옮길 수 있다.

 

각 칸에 있는 블롭의 수가 \( K \)의 배수가 아니면 블롭이 슬퍼한다.

 

블롭이 슬퍼하지 않게 블롭을 옮기는 일을 마칠 수 있는 최소 시간을 구하여라.

 

 

그리디로 해결되는 문제이다.

 

왼쪽부터 오른쪽으로 순회하며 블롭의 수의 합이 K 이상이 되는 구간 (i, j)를 찾는다.

 

결국 구간 (i, j) 사이의 한 칸에 블롭을 K마리 몰아야 할것이다.

 

이를 그리디하게 계산해준다.

 

다시 구간 (i, j)에서 왼쪽부터 오른쪽으로 순회하며 i번째 칸에 K 마리 블롭을 옮겼을 때와 i + 1번째 칸에 K 마리 블롭을 옮겼을 때의 시간을 구하여 시간이 덜 걸리는 방향으로 블롭들을 옮겨서 처리한다.

 

변수명이 더럽긴 한데 코드는 아래와 같다.

 

#include <bits/stdc++.h>

using namespace std;

long long n, k;
long long cnt[1000000];

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%lld %lld", &n, &k);

    long long acc = 0;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &cnt[i]);
        cnt[i] %= k;
        acc += cnt[i];
    }

    if (acc % k) {
        printf("blobsad");
    } else {
        long long ret = 0;

        for (int cur = 0; cur < n;) {
            if (cnt[cur]) {
                int right = cur + 1;
                long long rest_cnt = k - cnt[cur];
                long long sofar_cnt = 0, cost = 0;

                while (sofar_cnt < rest_cnt) {
                    sofar_cnt += cnt[right];
                    cost += (cnt[right] * (right - cur));
                    right++;
                }

                long long unn_cnt = 0;
                if (sofar_cnt > rest_cnt) {
                    unn_cnt = sofar_cnt - rest_cnt;
                    cost -= (unn_cnt * (right - cur - 1));
                }

                long long move_cost = cnt[cur];
                while (2 * move_cost < k) {
                    cur++;
                    ret += move_cost;
                    cost -= (k - move_cost);
                    move_cost += cnt[cur];
                }

                ret += cost;
                cnt[right - 1] = unn_cnt;
                cur = right - 1;
            } else {
                cur++;
            }
        }
        printf("%lld", ret);
    }
}

 

 

 

F. blobfearful

 

24503번: blobfearful

 

i일에는 블롭의 수가 전날의 i배만큼 늘어난다.

 

1일에는 블롭이 \(a_i\)마리가 있다.

 

블롭의 수가 K의 배수가 아니면 블롭들이 불안해 한다.

 

처음으로 블롭들이 불안해 하지 않는 날을 구하여라.

 

 

충분히 풀수 있는 문제인데 시간복잡도 계산을 잘못했다.

 

결국 답이 D라면 \( a_i * \) D!가 K로 나누어질 것이다.

 

그말은 즉은 K의 소인수 중 하나인 \( p \)에 대해 \( a_i * \) D!를 p로 소인수분해한 값 \( p_D \)와 K를 소인수분해 한 값 \( p_K \)의 관계가 \( p_D \geq p_K \) 을 만족해야 한다는 것이다.

 

K의 소인수 \( p \)와 제시된 \( a_ i \)을 \( p \)로 소인수분해한 값 \( p_a \)에 대하여 \( p_a \geq p_K \)라면 넘기고 \( p_a < p_K \)라면 D!를 \( p \)로 소인수분해 했을 때의 인수가 \( p_K - p_a \)개 이상인 최솟값 D를 찾는다.

 

모든 \( p \)에 대하여 구한 D의 최댓값이 정답이 된다.

 

최적화는 더 할수 있을건데 D를 찾는 로직을 이상하게 짜서 시간낭비가 너무 심했어서 스킵.

 

#include <bits/stdc++.h>

using namespace std;

long long k;
vector<long long> p, factor;

void set_p(long long tmp_k) {
    int end_idx = sqrt(tmp_k);
    for (int i = 2; i <= end_idx && (tmp_k != 1); i++) {
        if (!(tmp_k % i)) {
            p.push_back(i);
            factor.push_back(0);

            while (!(tmp_k % i)) {
                tmp_k /= i;
                factor.back()++;
            }
        }
    }

    if (tmp_k != 1) {
        p.push_back(tmp_k);
        factor.push_back(1);
    }
}

long long get_factor(long long target, long long p_i) {
    long long ret = 0;
    while (!(target % p_i)) {
        ret++;
        target /= p_i;
    }

    return ret;
}

long long get_cnt(long long cur, long long div) {
    long long cnt = 0;
    long long cur_div = div;

    while (cur_div <= cur) {
        cnt += (cur / cur_div);
        cur_div *= div;
    }

    return cnt;
}

int main() {
    // freopen("input.txt", "r", stdin);

    int q;
    scanf("%lld %d", &k, &q);

    set_p(k);

    int factor_size = p.size();
    while (q--) {
        long long a;
        scanf("%lld", &a);

        long long ret = 1;

        for (int i = 0; i < factor_size; i++) {
            long long cur_factor = get_factor(a, p[i]);

            if (cur_factor < factor[i]) {
                long long cnt = factor[i] - cur_factor;

                long long left = 2, right = cnt * p[i];
                long long target = right;

                while (left <= right) {
                    long long mid = (left + right) / 2;

                    if (get_cnt(mid, p[i]) >= cnt) {
                        target = mid;
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }

                if (target > ret) {
                    ret = target;
                }
            }
        }
        printf("%lld ", ret);
    }

    return 0;
}

 

 

 

G. blobcry

 

24504번: blobcry

 

단절선을 지웠을 때 component의 vertex 개수를 구하는 것을 공부한 다음 풀 예정.

 

 

 

H. blobyperthink

 

24505번: blobhyperthink

 

길이가 N인 수열 A가 있다.

 

다음 조건을 만족하는 \( (i, j, k, l, m, o, p, q, r, s, t) \) 쌍의 개수를 \( 10^9 + 7 \) 로 나눈 나머지를 구하여라.

 

• \(  i < j < k < l < m < o < p < q < r < s < t  \) 이고, \( A_i < A_j < A_k < A_l < A_m < A_o < A_p < A_q < A_r < A_s < A_t \) 이다.

 

D번 blobaww처럼 하나씩 하나씩 조건을 늘려나가면서 풀면 된다.

 

처음에는 \( (i, j) \) 쌍의 개수를, 그 다음에는 \( (i, j, k) \) 의 쌍의 개수를 구하면서 변수를 하나씩 추가시켜준다.

 

11중 segment tree를 사용하여 풀었다.

 

 

다이아는 나중에~