제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를 사용하여 풀었다.

 

 

다이아는 나중에~