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

#405부터 시작한 나는 17년 03월 24일 #406 코드포스 콘테스트를 참가했다.

아쉽게 specialist에서 pupil이 되었지만 많은 경험을 했다.

우선 시험 시간 2시간 동안 1, 2번 문제를 접할 수 있었고 3번 문제부터는 시간 할애조차 할 수 없었다.

이 블로그를 계기로 나의 콘테스트 이야기를 적어두고 싶다.

1번 문제는 매우 쉬워보였다.

A. The Monster :: http://codeforces.com/contest/787/problem/A

문제를 요약해서 설명하자면 다음과 같았다.

a b

c d를 입력받고 b + x*a == d + y*c를 만족하는 b + x*a가 존재하나? 존재한다면 최솟값을 출력, 존재하지 않는다면 -1을 출력하라

참 어리석게도 빨리 문제를 풀어야한다는 생각에 pretest만 통과하고 lock을 걸어버렸다.

코드포스가 처음인지라 너무 전략적으로 하지 못한 점도 있고, 너무 코딩을 대충하고 pretest를 통과하기 위한 코딩을 한 감이 없지않아 있다.

그렇게 lock을 해버리고 최종 테스트에서 틀리고 난 뒤 다시 문제를 해결하였다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
long long int sumA, sumC;
int cntA, cntC;
 
int main()
{
    int a, b;
    int c, d;
 
    scanf("%d %d", &a, &b);
    scanf("%d %d", &c, &d);
    
    while (cntC <= 100)
    {
        sumA = b + a * cntA++;
 
        while (sumA > sumC)
            sumC = d + c * cntC++;
 
        if (sumA == sumC)
        {
            printf("%lld\n", sumA);
            return 0;
        }
    }
 
    printf("-1");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

해결 전략

라인 스위핑 :: O(n+m)

라인 스위핑으로 문제를 해결 할 수 있었고, 처음에는 cntC의 범위를 정확히 해석할 수 없어서 1000만을 두고 풀었더니

AC를 받았다. 하지만 문제를 풀고도 cntC의 정확한 범위를 알지 못해 계속 줄여나간 결과 100까지 가능하였다.

그 이유를 생각해보니 cntC가 100까지만 돌아도 되는 이유는 a,b,c,d의 최대 범위가 100이고

따라서 공차가 최대 100이기 때문에 cntC가 최대 100인동안 그 사이에서 모든 값을 다 밝혀 낼 수 있다고 생각하였다.

a번 문제를 풀면서 느낀것은 매우 쉬운 문제이기도 하지만, 세밀한 코딩 과정에서는 아직 많이 부족한 감이 보이는 것 같다.

두번째 문제도 시간내에 확인하고 풀었지만, 결국 최종 테스트에서 틀렸다.

하지만 이 문제는 정말 내가 아직 시험에 많이 적응하지 못했다고 느껴지는게 map STL을 써서 빠르게 끝낼 수 있는데

긴장을 해서인지 코드가 눈에 잘 안들어오고 코딩을 잘 해내지 못하였다.

이 부분에 대해서는 반성하기 보다는 나중에 코드 시험을 칠 때 긴장감을 지금부터라도 컨트롤 할 수 있는법을 배워갈 수 있다는것에 많이 다행으로 생각되었다.

B. Not Afraid :: http://codeforces.com/contest/787/problem/B

문제를 요약해서 설명하자면 다음과 같다.

입력 방식은

n m이 주어지고

아래 m줄에 대해 input이 또 주어진다.

각 줄마다 첫번째 수를 입력받고 그 수만큼 값을 입력하는 방식이다.

구하고자 하는 것은

입력 받은 값에 대해 하나의 수가 양수, 음수로 함께 한쌍 이상 존재하는가? 를 묻는 문제이다.

예를들어

4 2

1 -3

4 -2 3 2 -3 를 보면 

n이 빨간 4, m이 푸른 2, 각 줄마다 첫번째 수가 초록색 1, 4이다.

1에서 보면 -3을 받는데 -3은 3과 한쌍이 되지 않고 혼자 존재하기에 "YES"를 출력해야 된다.

4에서 보면 -2 3 2 -3이면 2와 2, 3과 -3이 서로 쌍으로 존재하기에 "NO"를 출력할 수 있다.

하지만 이 문제에서 요구하는 사항은 하나라도 "YES"가 나올 수 있다면 무조건 "YES"를 출력해야 한다.

따라서 이 문제는 map STL로 아주 명료하게 풀 수 있다.

(하지만 실제 코드포스 콘테스트 시간에 풀지 못한 점이 아쉽긴 하다.)

#include <iostream>
#include <cstdio>
#include <map>
#include <math.h>
 
using namespace std;
 
 
int main()
{
    int n, tc;
    bool chk;
    scanf("%d %d", &n, &tc);
 
    while (tc--)
    {
        chk = true;
        map<int, int> m;
        int k;
        scanf("%d", &k);
 
        for (int i = 0; i < k; i++)
        {
            int val;
            scanf("%d", &val);
 
            if (m[val] == 0)
                m[val]++;
 
            if(m[val] == 1 && m[-val] == 1)
                chk = false;
        }
 
        if (chk == true)
            break;        
    }
 
    chk ? printf("YES") : printf("NO");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

해결 전략

map STL :: O(mlgn)

chk가 true면 같은 쌍이 존재하지 않는다는 의미, false면 하나라도 같은 쌍이 존재한다는 의미이다.

하지만 우리가 찾아야 할 것은 true가 나오냐가 매우 중요한 사안이다.

따라서 각 쌍이 존재한다면 false로 chk를 만들지만 true가 아닌이상 계속해서 tc번 while문을 돌아야한다.

만약 하나의 케이스에서 쌍으로 존재하는 수가 나오지 않았다면 true를 반환하고 종료할 수 있게된다.

이렇게 간단한 문제도 콘테스트 시간에는 해결하기가 어려웠다.

rating도 오르면 좋지만, 현재 나는 rating을 보면서 문제를 풀기 보단, 

내가 어떻게 하면 더 발전하고 시간내에 더 정갈한 코딩을 할 수 있을지 많은 고민을 한 콘테스트 였던 것 같다.