[Codeforces] Codeforces Round #407 (Div. 2) 이야기

늘 아쉬우면 아쉬운 콘테스트인 것이고 아니라고 생각하면 아닐 수 있지만, 오늘도 아쉬운 콘테스트인 것 같다.

오늘은 점수가 살짝 하락한 1291(-21)로 마무리를 했다.

오늘은 3번 문제까지 보고, 알고리즘 설계까지 마무리하고 있었는데 2번 문제에서 Hack을 당해버리니 그 뒤로 머리가 정지 된 것 같다.

1번 문제는 해석도 쉬웠고 문제 자체도 쉬웠지만 막상 접하려 하니 조금 까다로운 것 같았다. 

2번 문제도 오늘따라 알고리즘 측면 보다는 많은 경우의 수를 요구하는 문제인 듯 하였다.

하지만 2번은 결국 메모리 overflow로 핵 당했는데 마지막에 내가 틀린 testcase를 보고 바로 수정하였더니 콘테스트 후 통과하였다.

3번 문제는 구간에 대한 이야기를 보니 Prefix Sum 혹은 Segtree로 해결하면 될 것이라고 생각했고, 알고리즘 설계를 하던 도중 2번으로 넘어가는 바람에 3번은 해결하지 못했다.

A번문제는 다음과 같았다.

A. Anastasia and pebbles :: http://codeforces.com/contest/789/problem/A

n개 종류의 자갈이 각각 개수만큼 주어지고, 주머니가 2개 있는데 각 주머니에는 k개씩 넣을 수 있다.

이때 주머니에는 다른 종류의 자갈을 넣지 못한다.

하루에 한번만 주머니가 리셋된다. 이때 최소 몇일이 지나야 모든 자갈을 다 가져갈 수 있을까?

자갈을 a주머니, b주머니에 담는 방식만 잘 구현하면 아무 문제없이 끝나는 문제이다.

시간 복잡도는 O(n^2)이고 n이 최대 10000이기에 시간 복잡도 면에서는 간신히 통과하였다.

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

#include <iostream> #include <cstdio> using namespace std;   int arr[100002];   int main() {     int n, m;     int day = 1;     int pocket = 0;       scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       while (pocket < n)     {         int a = m;         int b = m;           if (arr[pocket] > a)             arr[pocket] -= a;           else             arr[pocket++] = 0;           if (arr[pocket] > b)             arr[pocket] -= b;           else if (arr[pocket] <= b)             arr[pocket++] = 0;           day++;     }       printf("%d", day - 1);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

B번 문제는 다음과 같았다.

B. Masha and geometric depression :: http://codeforces.com/contest/789/problem/B

문제에 대해 한글로 설명하자하니 조금 까다로워 예제를 통해 설명 해 본다.

3 2 30 4

6 14 25 48

일 때, 아래줄에 있는 값은 선택되면 무시해야 할 값들이다.

3은 시작 값이고 2는 곱해질 값, 30은 최댓값 4는 아래 줄에 입력할 개수이다.

결국 예제는

3, 3*2(6), 3*2*2(12), 3*2*2*2(24), 3*2*2*2*2(48) ... , 로 흘러가는데

6은 무시할 값이니 넘기고 48은 30을 넘었으니 표시하면 안된다.

따라서 답은 3, 12, 24로 3가지인 3이다.

이 문제는 결국 금지 수는 map STL로 받아내고, 위의 값에서 b가 0일때, q가 1, 0, -1일때의 조건만 잘 처리 해준다면 AC를 받을 수 있다.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <vector>
 
using namespace std;
typedef long long ll;
 
map<ll, bool> MAP;
vector<ll> ans;
 
int main()
{
    ll b, q, l, m;
 
    scanf("%lld %lld %lld %lld", &b, &q, &l, &m);
 
    for (int i = 0; i < m; i++)
    {
        ll val;
        scanf("%lld", &val);
 
        MAP[val] = 1;
    }
 
    while (1)
    {
        if (abs(b) > l)
            break;
        
        if (MAP[b] != 1 && abs(b) <= l)
            ans.push_back(b);
 
        b *= q;
 
        if (b == 0)
        {
            if(MAP[b] != 1)
            {
                printf("inf");
                return 0;
            }
            if (MAP[b] == 1)
                break;
        }
        if (q == 0)
        {
            if (MAP[b] != 1)
            {
                printf("inf");
                return 0;
            }
 
            if(MAP[b] == 1)
                break;
        }
 
        else if (q == 1)
        {
            if (MAP[b] != 1)
            {
                printf("inf");
                return 0;
            }
            else if (MAP[b] == 1)
            {
                printf("0");
                return 0;
            }
        }
 
        else if (q == -1)
        {
            if (MAP[b] == 1 && MAP[-b] == 1)
            {
                printf("0");
                return 0;
            }
 
            else if (MAP[b] == 1 && MAP[-b] != 1)
            {
                printf("inf");
                return 0;
            }
 
            else if (MAP[b] != 1 && MAP[-b] == 1)
            {
                printf("inf");
                return 0;
            }
 
            else if (MAP[b] != 1 && MAP[-b] != 1)
            {
                printf("inf");
                return 0;
            }
        }
    }
 
    printf("%d", ans.size());
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

오늘은 2번 문제를 Hack당하기도 해봤고, 아쉬운 부분이 있었지만,

처음으로 3번까지 내가 생각을 해보았다는 점, 긴장을 많이 하지 않고 차근차근 풀어나갔던 점은 마음에 드는 것 같다.

그런데 코드가 정갈하지 못하고 많은 조건문을 이용하여 작성하는게 이 문제의 핵심이었는지는 잘 모르겠다.

다음 #408때는 좀 더 좋은 성적을 받기위해 더 노력해야겠다.