Codeforces Round #697 (Div. 3)

Codeforces Round #697 (Div. 3)

Codeforces Round #697 (Div. 3)

 

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

 

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

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

 - codeforces.com/contest/1475 [ 바로 가기 ]

 

[2021.01.27] 초판 발행

 

 대회 기간 중에 채점이 크게 지연되는 상황이 있었습니다. 그 여파로 인한 것인지, 기술적인 문제로 rating에 반영되지 않은 대회가 되었습니다.

 

[A번] Odd Divisor

 

[문제 및 풀이]

 

 주어진 수가 홀수인 약수를 갖는지 알아보는 문제이다. 결국 주어진 수가 $2$의 거듭제곱인지 확인하는 것과 동일하다.

 

[구현]

 

 문제에서 원하는 바를 잘 구현하면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
long long N;
 
bool process() {
    scanf("%lld", &N);
 
    for (; N > 1; N /= 2) if (N % 2) return true;
    return false;
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) printf("%s\n", (process()) ? "YES" : "NO");;
 
    return 0;
}
 

 

[B번] New Year's Number

 

[문제 및 풀이]

 

 주어진 수가 $2021$과 $2022$의 합으로 표현할 수 있는지 알아보는 문제이다.

 

[구현]

 

 주어진 수를 $2011$과 $2011+1$의 합으로 나타내는 방식으로 접근하면 쉽다. 즉, 주어진 수 $N$이 다음과 같이 표현된다고 하자.

 

$N = 2011 \times a + b$

 

 이렇게 표현이 된다면 주어진 수를 $a-b$개의 $2011$과 $b$개의 $2022$로 표현할 수 있다는 것이다. 즉, 주어진 수를 위와 같이 표현하였을 때, $a$가 $b$보다 같거나 크다면 표현할 수 있다는 것을 의미한다. 이 말은 다른 말로, 주어진 수를 $2011$로 나눈 몫과 나머지를 구했을 때, 몫이 나머지보다 크면 확인하고자 하는 조건을 만족하고 그렇지 않다면 만족하지 않는다고 보면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
int N;
 
bool process() {
    int a, b;
 
    scanf("%d", &N);
    a = N / 2020, b = N % 2020;
 
    return a >= b;
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) printf("%s\n", (process()) ? "YES" : "NO");;
 
    return 0;
}
 

 

[C번] Ball in Berland

 

[문제 및 풀이]

 

 $K$개의 순서쌍이 주어졌을 때, 각 순서쌍을 구성하는 수가 서로 모두 다른 '순서쌍의 쌍'의 수를 구하는 문제이다.

 

[구현]

 

 포함-배제의 원리를 이용하면 된다. 순서쌍 $(a,b)$와 쌍이 될 수 있는 순서쌍의 수는 전체 순서쌍에서 $a$를 포함하는 순서쌍의 수와 $b$를 포함하는 순서쌍의 수를 빼고, $a$와 $b$를 모두 포함하는 순서쌍의 수를 더하는 것이다. $a$와 $b$를 모구 포함하는 순서쌍은 중복된 순서쌍이 없으므로 항상 $1$이다.

 

 참고로, $(a,b)$가 $(c,d)$를 선택하는 것과 $(c,d)$가 $(a,b)$를 선택하는 것이 중복되어서 선택하게 된다. 악수 정리(Handshaking lemma)에 의해서 최종적으로는 $2$로 나누어야 한다.

 

[예시 답안]

 

#include <stdio.h>
#define Max 300000
 
int N, M, K;
long long Ans;
int ac[Max], bc[Max], a[Max], b[Max];
 
void process() {
    int i;
 
    scanf("%d%d%d", &N, &M, &K);
    for (i = 0; i <= N; i++) ac[i] = 0;
    for (i = 0; i <= M; i++) bc[i] = 0;
 
    for (i = 0; i < K; ac[a[i]]++, i++) scanf("%d", &a[i]);
    for (i = 0; i < K; bc[b[i]]++, i++) scanf("%d", &b[i]);
 
    for (i = 0, Ans = 0; i < K; i++) Ans += K - (ac[a[i]] + bc[b[i]]) + 1;
 
    printf("%lld\n", Ans / 2);
}
 
int main() {
    int T;
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[D번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

[E번] Advertising Agency

 

[문제 및 풀이]

 

 $N$개의 수 중에서 $K$개의 수를 선택하였을 때, 그 수들의 합이 최대가 되도록 선택하는 경우의 수를 구하는 문제이다. 

 

[구현]

 

 $N$개의 수를 내림차순으로 정렬하였을 때, $K$번째 수를 $a_i$라고 하자. 경우의 수는 $a_i$와 같은 값을 갖는 수가 그 수가 선택하고자 하는 $K$개의 수에 포함되는지로 결정이 된다. $N$개의 수 중에서 $a_i$와 동일한 값을 $A$이고, $K$개의 수 중에 $a_i$와 동일한 값을 $B$라고 한다면 정답은 $_A C _B$이다.

 

 전(前)처리 과정으로 파스칼의 삼각형을 만들고, 각 case별로 $A$와 $B$를 구해서 해결할 수 있다.

 

[예시 답안]

 

#include <stdio.h>
#include <algorithm>
#include <functional>
#define Max 1500
#define Res 1000000007
 
using namespace std;
 
int N, M, A, B;
int d[Max];
long long D[Max + 100][Max + 100];
 
void make_set() {
    int i, u;
 
    D[0][0] = 1;
    for (i = 0; i < Max; i++) for (u = 0; u < Max; u++) D[i + 1][u] += D[i][u], D[i + 1][u + 1] += D[i][u], D[i + 1][u] %= Res, D[i + 1][u + 1] %= Res;
}
 
void process() {
    int i;
    long long n;
 
    scanf("%d%d", &N, &M);
    for (i = 0; i < N; i++) scanf("%d", &d[i]);
    sort(d, d + N, greater<int>());
 
    for (i = A = 0; i < N; i++) if (d[i] == d[M - 1]) A++;
    for (i = B = 0; i < M; i++) if (d[i] == d[M - 1]) B++;
 
    printf("%lld\n", D[A][B]);
}
 
int main() {
    int T;
 
    make_set();
 
    scanf("%d", &T);
    while (T--) process();
 
    return 0;
}
 

 

[F번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

[G번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]