Home Codeforces Round #698 (Div. 2) 후기
Post
Cancel

Codeforces Round #698 (Div. 2) 후기

By Joe2357
Posted 2021-01-29 11 min read

specialist에 다시 도달하기 위한 도전을 하였다. 2점만 올려도 복귀할 수 있었지만, 최대한 풀 수 있는만큼 풀어내야겠다고 생각했다.

A. Nezzar and Colorful Balls

풀이 보기

풀이

문제가 어렵게 쓰여있었다. 바로 이해하지 못해 B번 문제를 먼저 풀고 다시 시도했던 문제이다.

요점은 아래와 같다.

  • 공에는 색깔을 모두 칠해야한다.
  • 색깔들은 strictly increasing sequence를 띠어야한다.

2번 요점은 다르게 말하면, 같은 숫자의 공은 다른 색깔을 사용하여야한다이다. strictly increasing sequence는 같은 숫자가 존재해서는 안되기 때문이다.

결론적으로 숫자가 같은 공들끼리의 색깔만 다르게 칠하면 된다. 최소의 색깔만을 사용하려하기 때문에, test case에서의 정답은 숫자가 같은 가장 많은 공의 수만큼의 색깔이 필요하다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <stdio.h>
 
int main() {
    int t;
    scanf("%d", &t);
    for (; t; t--) {
        int arr[101] = { 0 };
        int n;
        scanf("%d", &n);
        for (; n; n--) {
            int a;
            scanf("%d", &a);
            arr[a]++;
        }
        int max = 0;
        for (int i = 0; i <= 100; ++i) {
            if (arr[max] < arr[i])
                max = i;
        }
        printf("%d\n", arr[max]);
    }
    return 0;
}

B. Nezzar and Lucky Number

풀이 보기

풀이

주어지는 숫자 $d$가 포함된 숫자는 모두 lucky number로 지정할 수 있다. 만약 $d=7$이라면 기본적으로 $7,17,27,…$ 등이 있다. 또 $70,71,72,…,79$ 등도 lucky number이다.

만약 만들어야하는 숫자가 $d\times 10$보다 크거나 같다면, 그 숫자는 lucky number의 합으로 항상 만들 수 있다. 증명은 아래의 단계를 통해 할 수 있다.

  • lucky number들 중 십의 자리가 $d$은 두자리 수는 $d\times 10+x$로 나타낼 수 있다.
  • $d\times 10+x$는 $d$ 자체가 lucky number이므로 $d\times 10+d+y$로도 나타낼 수 있다. ($0≤y≤d$)
    • 위의 조건에 의해, $x$의 범위는 $0≤x≤2\times d$
    • 위의 조건을 계속해서 넓힐 수 있고, 그 때의 $x$ 범위는 $0≤x$

따라서 $d\times 10$ 이상의 모든 수는 lucky number의 합으로 만들 수 있다.

이후는 $d\times 10$보다 작은 수를 lucky number의 합으로 구할 수 있는지를 판별하면 된다. 이 경우 만약 답이 존재한다면 그 수들은 일의 자리가 $d$인 수들의 합으로 이루어지므로, 일의 자리를 비교하면 어떤 수의 합으로 구할 수 있는지를 알 수 있다.

  • 사용할 lucky number의 일의 자리는 항상 $d$이므로, $d$를 여러 번 더하여 구해야 할 수 $n$의 일의 자리를 만들 수 있는지를 먼저 검사한다. 만약 가능하다면 그 때의 더한 횟수를 $i$라고 한다.
  • $n$와 $d\times i$의 대소를 검사한다. $n≥(d\times i)$인 경우에는 lucky number의 합으로 $n$을 만들 수 있다.
    • 만약 $n≤(d\times i)$라면, $n$은 만들 수 없다.
    • 만약 $n=(d\times i)$라면, $n=d\times i$이다.
    • 만약 $n≥(d\times i)$라면, $n=d\times i + z\times 10$이므로, $z$를 적절히 분배하여 lucky number들의 합으로 조절할 수 있다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <stdio.h>
 
typedef char boolean;
#define True 1
#define False 0
 
int main() {
    int t;
    scanf("%d", &t);
    for (; t; --t) {
        int q, d;
        scanf("%d %d", &q, &d);
        for (; q; --q) {
            int n;
            scanf("%d", &n);
            boolean r = False;
            int a = n;
            while (a) {
                if (a % 10 == d)
                    r = True;
                a /= 10;
            }
            if (n >= d * 10)
                r = True;
            for (int i = 1; i <= 10; ++i) {
                if (n % 10 == (d*i) % 10) {
                    a = n - (d*i);
                    if (a >= 0) {
                        r = True;
                        break;
                    }
                }
            }
 
            if (r) {
                printf("YES\n");
            }
            else {
                printf("NO\n");
            }
        }
    }
    return 0;
}

C. Nezzar and Symmetric Array

풀이 보기

풀이

한 줄로 요약하면 수학문제이다.

주어진 조건에서, 구해야 하는 symmetric array $a$는 모두 다른 원소로 이루어져있다. 따라서 원소 중 $0$은 존재할 수 없다. 기본 조건에 의해 $a$는 아래와 같은 형태를 띠게 된다.

  • $a=[x,y,-x,-y]$ ($0<x<y$)
  • 원소의 개수는 계속해서 늘릴 수 있다.

이를 이용하여 배열 $d$를 제작한다면, 아래와 같은 결론에 도달할 수 있다.

  • 절댓값이 같은 두 원소의 배열값 $d_i$는 같다.
  • 절댓값이 다른 두 원소의 배열값은 서로 다르다.

이 조건을 이용하여, $d$의 원소들은 같은 값이 2번 등장한다는 것을 알 수 있다. 만약 아니라면 $d$를 이용하여 $a$를 만들 수 없다. 코드에서는 set을 사용하여 1차적으로 분류해주었다.

$d_i$를 좀 더 탐구해보자. 만약 만들게 될 $a=[x,y,-x,-y]$인 경우, 문제에 제시된 정의에 의해 $d=[(2x+2y), 4y, (2x+2y), 4y]$가 된다. 정확한 값은 아래와 같다.

  • 원소의 개수가 $2n$개인 배열 $a$에서, 원소들 중 절대값이 가장 큰 원소 $x$의 배열값 $d_x=2n\times x$이다.
  • 이외의 원소들은, 자신보다 절댓값이 큰 양의 원소의 개수를 $y$라고 할 경우, $d_x=(2n-2y)\times x + \sum_{i=1}^{y}2\times a_i$이다.

이해를 돕기 위한 test case로 아래와 같이 주어진다고 가정하자.

1

8 12 8 12

위의 test case는 같은 값이 2번 반복되는 것을 알 수 있다. 하지만 $a$를 만들 가능성이 있다는 것이지, 무조건적으로 만들 수 있다는 것은 아니다.

위의 경우에서 $a$를 만든다면, 그 형태는 $a=[x,y,-x,-y]$ ($0<x<y$) 일 것이다. $d=[(2x+2y), 4y, (2x+2y), 4y]$일 것이고, 따라서 $x=1,y=3$이다. 위의 경우에는 정답이 존재한다.

위의 경우를 모두 정리하면, 아래와 같은 조건을 만들 수 있다. 만약 모두 만족한다면 정답이 존재하는 것이다.

  • $d$의 원소들은 같은 값이 2번 반복되는 구조이다.
  • $d$의 원소들을 이용하여 $a$의 원소의 절댓값을 구할 수 있어야 한다. ( 각 원소는 짝수이어야 한다. )
  • $a$의 원소들은 양의 정수여야한다. ( $0$은 불가능하다. )

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <iostream>
#include <set>
#define MAX 1000
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        set<long long, greater<long long> > s;
        for (int i = 0; i < 2 * n; ++i) {
            long long a;
            cin >> a;
            s.insert(a);
        }
        bool remained = true;
        if (s.size() != n) {
            remained = false;
        }
 
        int len = 0;
        long long sum = 0;
        for (long long ll : s) {
            if (remained) {
 
                long long temp = ll - (2 * sum);
                if (temp % (2 * (n - len)) != 0) {
                    remained = false;
                }
                else {
                    long long a = temp / (2 * (n - len));
                    if (a <= 0) {
                        remained = false;
                    }
                    else {
                        sum += a;
                        ++len;
                    }
                }
            }
        }
 
        if (remained) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
}

결과

ContestStart timeRankSolvedRating changeNew rating
#698 (Div. 2)2021/1/28
23:35		11323+1031501

specialist에 복귀하였다! rate도 큰 폭으로 상승하였다. 이번 contest가 구현에는 큰 문제 없이 수학문제와 같은 느낌을 주었고, 오히려 증명하며 풀어가는 과정이 매우 재밌었다.

더 높은 rate에 도전하고 싶지만, 논문세미나의 일정이 빠듯하여 당분간은 contest를 쉬려고 한다. 파란색 닉네임을 얻을 때까지 공부하여 도전해봐야겠다.

Problem Solving, Codeforces
Contest Codeforces
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents