[Codeforces] VK Cup 2017 - Wild Card Round 1 (Unofficial Public Mirror) 이야기

뭐가 뭔지 모르는 채로 VK Cup 2017을 해보았다.

팀별로 나갈 수 있는 VK Cup은 Unofficial로 나가면 그냥 개인적으로 대회를 참가해 볼 수 있다.(비공식이라 레이팅 반영은 없다.)

그리고 처음에는 무슨 말인지 몰랐지만 VK Cup에서 특별한 룰을 제시했는데,

A~L번 문제에 대해 서로 다른 언어를 이용하여 문제를 풀어야 한다는 것이었다.

룰도 제대로 읽어보지 않은 채 마냥 제출이 되지 않아 화가 나서 댓글에 이런 경우가 다있냐고 화를 낸건 Codeforces 유저들에게 매우 미안한 마음이다. (화를 냈던 나는 당연히 부끄럽고 미안하고, 보는 입장에서는 기분이 좋지 않았을 수도 있다.)

나는 C, C++, Java를 알고있지만, 자바로는 따로 제출해본적이 없어 VK Cup이 끝나고 룰에 대한 제한이 풀리고 나서(다시 Vitual Participation을 하면 된다.) 3문제를 해결하였다.

A번은 수학적 지식이 녹아있는 것 같았지만, 무슨 내용인지 잘 몰라 패스를 하였고, 사람들이 많이 푸는 순서대로 참여를 하여 C, D, K번을 해결하였다.

C번 문제는 다음과 같다.

C. Maximum Number :: http://codeforces.com/contest/795/problem/C

디지털 시계가 표현되어있고, input에는 쓸 수 있는 디지털 시계에서의 라인 최대수가 주어진다.

이 라인은 무조건 써야하고, 이때 최대 수를 구하는 문제이다.

2일때는 1에 2개의 라인이 필요하기에 1이 답이고

3일때는 7에 3개의 라인이 필요하기에 답이 7이다.

이 문제를 공책에 적어가며 규칙을 찾아보니 다음과 같은 규칙이 있었다.

짝수일때는 1로 이루어 진 것이 가장 큰 수이고,

홀수일때는 7로 시작하여 1을 계속 넣으면 된다.

예를들어

8이면

1111이 최대이고

9이면

7111가 최대이다.

이 내용을 코드화 시키면 다음과 같이 O(N)에 간단하게 해결 할 수 있었다.

#include <stdio.h>
 
long long arr[10] = { 0,0,1,7,11,71,111 };
int main()
{
    int n;
    scanf("%d", &n);
 
    if (2 <= n && n <= 6)
        printf("%d", arr[n]);
 
    else if (n % 2 == 0)
    {
        for (int i = 0; i < n / 2; i++)
            printf("1");
    }
 
    else if (n % 2 == 1)
    {
        printf("7");
        for (int i = 0; i < n / 2 - 1; i++)
            printf("1");
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

D. Lie or Truth :: http://codeforces.com/contest/795/problem/D

D번 문제를 input을 통해 확인해보면 다음과 같다.

input

5 2 4
3 4 2 3 1
3 2 3 4 1

output

TRUTH

5 2 4는 5개의 수, 2~4만 바꿨다고 말했을 때 아래 두 5개의 수가 진짜 2~4만 바뀌었을까?

3 4 2 3 1과 3 2 3 4 1은 2~4부분이 4 2 3, 2 3 4이기에 4 2 3을 적절히 바꾸면 다시 2 3 4로 만들 수 있기에 TRUTH이다.

하지만 만약 다음과 같은 값이 있다 생각해보자

input

5 3 4
1 2 3 4 5
1 5 4 3 2

output

LIE

이 문제는 LIE다. 3~4가 3 4, 4 3이지만 1 2 5와 1 5 2부분이 이미 바뀌었는데 3~4만 바뀌었다고 말한 것 자체가 거짓말이기 때문이다.

따라서 이 두가지 규칙을 생각하고 코드를 작성하면 O(N)에 해답을 얻을 수 있다.

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

K. Stepan and Vowels :: http://codeforces.com/contest/795/problem/K

K번 문제는 다음과 같다.

a, e, i, o, u는 중복되어 계속 표시되면 1개로 축약시키는 문제이다. 단, e, o는 2개면 2개를 표시한다.

문자열 처리에 대해 잘 할 수 있느냐에 대한 문제였고, 그냥 e, o가 2개일때 2개를 표시하고 그 외에는 다 지울 수 있는 코드를 작성하면 된다. 이 문제 또한 O(N)에 해결된다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
char ch[100001];
int main()
{
    int n;
    scanf("%d", &n);
 
    scanf("%s", ch);
 
    for (int i = 0; i < n; i++)
    {
        if (ch[i] == 'e' && ch[i + 1] == 'e')
        {
            if (ch[i + 2] != 'e')
                continue;
            while (ch[i + 2] == 'e')
            {
                ch[i] = '.';
                ch[i + 1] = '.';
                i++;
            }
        }
        else if (ch[i] == 'o' && ch[i + 1] == 'o')
        {
            if (ch[i + 2] != 'o')
                continue;
            while (ch[i + 2] == 'o')
            {
                ch[i] = '.';
                ch[i + 1] = '.';
                i++;
            }
        }
        else if (ch[i] == 'a' && ch[i + 1] == 'a')
            ch[i] = '.';
 
        else if (ch[i] == 'i' && ch[i + 1] == 'i')
            ch[i] = '.';
 
        else if (ch[i] == 'u' && ch[i + 1] == 'u')
            ch[i] = '.';
 
        else if (ch[i] == 'y' && ch[i + 1] == 'y')
            ch[i] = '.';
    }
 
    for (int i = 0; i < n; i++)
    {
        if (ch[i] != '.')
            printf("%c", ch[i]);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

쉬운 문제들로만 계속 접해본 것 같아 알고리즘 측면으로 못 다가간게 아쉽지만, 대회라는게 무조건 알고리즘만 요구하는 것은 절대 아닌 것 같다는 생각이 계속 든다.