Codeforces Round #702 (Div. 3)

Codeforces Round #702 (Div. 3)

 

Codeforces Round #702 (Div. 3)

 

Codeforces Round #702 (Div. 3)에 대한 해설입니다.

 

 * 이 글은 code-review 항목의 포스트입니다. code-review 항목에 대해 자세히 알아보고 싶다면, 클릭!

 * 문항 원문은 아래 주소에서 확인 가능합니다.

 

codeforces.com/contest/1490

Dashboard - Codeforces Round #702 (Div. 3) - Codeforces

 

[2021.02.18] 초판 발행

 

Codeforces Round #702 (Div. 3)에 대한 해설입니다.

 

[A번] Dense Array (Codeforces 1490A)

 

[문제 및 풀이]

 

 $n$개의 수에서 $a \times 2^m \leq b$을 만족하는 $m$의 최댓값을 구하는 문제이다. 모든 경우의 수를 고려하면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
int N, Ans;
int d[100];
 
int min(int a, int b) { return (a < b) ? a : b; }
int max(int a, int b) { return (a > b) ? a : b; }
 
int Cnt(int a, int b) {
    int c;
 
    for (c = 0; a < b; a *= 2, c++);
    return c - 1;
}
 
void process() {
    int i;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%d", &d[i]);
 
    for (i = 0, Ans = -1; i < N - 1; i++) if (max(d[i], d[i + 1]) > 2 * min(d[i], d[i + 1])) Ans += Cnt(min(d[i], d[i + 1]), max(d[i], d[i + 1]));
 
    printf("%d\n", Ans + 1);
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[B번] Balanced Remainders (Codeforces 1490B)

 

[문제 및 풀이]

 

 $n=3k$개의 수를 $3$으로 나눈 나머지에 따라서 세 개의 묶음을 나누었다. 각 수를 적절히 옮겨서 세 묶음을 구성하는 수의 개수가 동일해졌을 때, 필요로 하는 최소의 이동 횟수를 구하는 문제이다. 경우에 따라 욕심쟁이 기법으로 최선의 경우를 상정하 수 있다.

 

 애초에 동일한 경우에는 아무 시행을 하지 않아도 된다. 그 이외에는 다음 두 가지 경우가 있다.

 1. $k$보다 작은 묶음이 하나인 경우 : $k$보다 작은 묶음이 $i$번째라면, $i+1$번째 묶음에서 $k$보다 초과한 양의 $2$배와 $i+2$번째 묶음에서 $k$보다 초과한 양을 더한 것이 정답이다.

 2. $k$보다 작은 묶음이 둘인 경우 : $k$보다 큰 묶음이 $i$번째라면, $i+1$번째 묶음에서 $k$보다 부족한 양과 $i+1$번째 묶음에서 $k$보다 초과한 양의 $2$배를 더한 것이 정답이다.

 

 $i+1$과 $i+2$가 $2$를 초과하면 각각 $3$으로 나눈 나머지를 취한다. 가령, $i+1=3$이면 $0$, $i+1=4$이면 $1$이고 $i+1=5$이면 $2$를 취한다. 

 

[예시 답안]

 

#include <stdio.h>
 
int N;
int d[35000], a[3];
 
void process() {
    int i, Cnt;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%d", &d[i]);
 
    a[0] = a[1] = a[2] = 0;
    for (i = 0; i < N; i++) a[d[i] % 3]++;
 
    for (i = Cnt = 0; i < 3; i++) if (a[i] < N / 3) Cnt++;
 
    if (!Cnt) printf("0\n");
 
    else if (Cnt == 1) {
        for (i = 0; i < 3; i++) if (a[i] < N / 3) break;
        printf("%d\n", (a[(i + 1) % 3] - N / 3) * 2 + (a[(i + 2) % 3] - N / 3));
    }
 
    else {
        for (i = 0; i < 3; i++) if (a[i] > N / 3) break;
        printf("%d\n", (N / 3 - a[(i + 1) % 3]) + (N / 3 - a[(i + 2) % 3]) * 2);
    }
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[C번] Sum of Cubes (Codeforces 1490C)

 

[문제 및 풀이]

 

 주어진 수 $n$에 대해서, $a^3 + b^3 = n$을 만족하는 정수 순서쌍 $(a,b)$가 존재하는지 확인하는 문제이다. 정수 하나를 잡고, 나머지 정수가 존재하는지 확인하는 방식으로 구하면 된다.

 

 한 가지 방법으로는 세제곱수를 모아놓은 배열을 준비한다. 정수 $i$를 잡고($O( \sqrt[3]{n} )$), $n - i^3$를 미리 준비한 세제곱수 배열에서 이분검색으로 찾는다.

 

[예시 답안]

 

#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
long long N;
vector<long long> b;
 
void make_set() {
    long long i;
 
    for (i = 0; i <= 10000; i++) b.push_back(i*i*i);
}
 
void process() {
    int p;
    long long i, Val;
 
    scanf("%lld", &N);
    for (i = 1; i*i*i < N; i++) {
        Val = N - i * i*i;
        p = upper_bound(b.begin(), b.end(), Val) - b.begin();
        if (b[p - 1] == Val) break;
    }
 
    printf("%s\n", (i*i*i < N) ? "YES" : "NO");
}
 
int main() {
    int T;
 
    make_set();
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[D번] Permutation Transformation (Codeforces 1490D)

 

[문제 및 풀이]

 

 $n$개의 수가 주어질 때, 다음을 만족하는 이진트리(binary tree) 구조를 구성하는 문제이다. 구성한 트리의 각 원소의 깊이(depth)를 출력하는 문제이다.

 

 1) 주어진 값의 최댓값을 해당 트리의 루트(root)로 한다.

 2) 최댓값을 중심으로 왼쪽에 있는 원소를 이용해서 왼쪽의 서브트리(sub-tree)를 만들고, 오른쪽에 있는 원소를 이용해서 오른쪽의 서브트리를 만든다.

 

[예시 답안]

 

#include <stdio.h>
 
int N;
int d[150], Ans[150];
 
void dnq(int s, int e, int dep) {
    int i, p;
 
    if (s > e) return;
 
    for (i = p = s; i <= e; i++) if (d[p] < d[i]) p = i;
 
    Ans[p] = dep;
    dnq(s, p - 1, dep + 1);
    dnq(p + 1, e, dep + 1);
}
 
void process() {
    int i;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%d", &d[i]);
 
    dnq(0, N - 1, 0);
 
    for (i = 0; i < N; i++) printf("%d ", Ans[i]);
    printf("\n");
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[E번] Accidental Victory (Codeforces 1490E)

 

[문제 및 풀이]

 

 $n$명의 참가자가 있고, $n-1$번의 게임이 이루어진다. 각 참가자에게는 능력치가 주어지는데, 능력치가 다른 사람이 게임을 하면 능력치가 큰 사람이 이기게 된다. 능력치가 같은 경우에는 두 사람 다 이길 가능성이 있다. 구하고자 하는 것은 주어진 사람 중에서 우승할 수 있는 사람의 수를 구하는 문제이다.

 

 참가자가 어떤 참가자보다 능력치가 같거나 크다면 그 참가자를 이길 수 있다. 능력치 순서대로 오름차순으로 정렬을 한다. 그리고 오름차순 순서대로 누적합을 구하고^[각주:1], 각 누적합이 능력치 최댓값보다 크다면 우승 가능한 사람으로 분류할 수 있다.

 

 우승할 수 있는 사람을 출력하는 것은, 각 우승 가능성과 참가자 번호를 구조체로 묶어서 다루면 좋다.

 

[예시 답안]

 

#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
struct item { long long p, v; };
bool operator < (const item &A, const item &B) { return A.v < B.v; }
 
int N;
item d[250000];
long long Sum[250000];
vector<int> Ans;
 
void process() {
    int i, Size;
 
    scanf("%d", &N);
    for (i = 0; i < N; d[i].p = i, i++) scanf("%lld", &d[i].v);
    sort(d, d + N);
 
    Ans.clear();
 
    Sum[0] = d[0].v;
    for (i = 1; i < N; i++) Sum[i] = Sum[i - 1] + d[i].v;
 
    for (i = N - 2; i >= 0; i--) if (d[i].v == d[i + 1].v) Sum[i] = Sum[i + 1];
 
    Ans.push_back(d[N - 1].p + 1);
 
    for (i = N - 2; i >= 0; i--) {
        if (Sum[i] < d[i + 1].v) break;
        Ans.push_back(d[i].p + 1);
    }
 
    Size = Ans.size();
    sort(Ans.begin(), Ans.end());
 
    printf("%d\n", Size);
    for (i = 0; i < Size; i++) printf("%d ", Ans[i]);
    printf("\n");
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[F번] (작성 전) (Codeforces 1490F)

 

[문제 및 풀이]

 

 

 

[예시 답안]

 

 

 

[G번] (작성 전) (Codeforces 1490G)

 

[문제 및 풀이]

 

 

 

[예시 답안]

 

 

 

1. 동일한 능력치를 가진 사람을 동일한 누적합으로 하는 과정이 필요하다. [본문으로]