Codeforces April Fools Day Contest 2020 review

1. 대회 소개

대회 링크

4/1일에 진행된다.. 레이팅에 반영되지 않는다¹.. 출제자와 유머 코드가 맞아야 한다..? 등의 내용입니다.

세계 각국에서 19470 분이나 참가하셨습니다.

2. 목차

문제 목차입니다. 초록색은 제가 맞힌 문제, 빨간색은 제가 시도했지만 틀린 문제입니다.

총 8문제로 구성되었고, 우리나라 시계 기준 4/1 밤 11시 35분부터 2시간 동안 진행되었습니다.

3. 문제 풀이

A번 문제입니다. 첫 문제부터 입출력 예제와 문제에 대한 설명이 하나도 없습니다…

풀이

문제 이름이 “Is it rated?” 입니다.

대회 소개에서 "... and it will be unrated." 라 했으므로, NO를 출력하면 되는 문제였습니다.

#include <cstdio>
using namespace std;
 
int main()
{
    printf("NO");
    return 0;
}

B번 문제입니다. 문제 설명은 풀이와 아무 관련이 없는듯합니다..

풀이

input과 output간의 규칙을 보면,

Test case	input	output
#1	35	57 (5*7)
#2	57	319 (3*19)
#3	391	1723 (17*23)

output은 소수의 오름차순 곱으로 이루어져 있다는 것을 알 수 있습니다!

#include <cstdio>
using namespace std;
 
int prime[12] = { 2,3,5,7,11,13,17,19,23,29,31 };
 
int main(void)
{
    int a;
    scanf("%d", &a);
    for (int i = 0; i <= 10; i++)
    {
        if (a % prime[i] == 0)
            while (a % prime[i] == 0)
            {
                printf("%d", prime[i]);
                a /= prime[i];
            }
        if (a == 1)
            break;
    }
    if (a != 1)
        printf("%d", a);
    return 0;
}

C번 문제입니다. 풀이를 생각해내는 데 한참 걸렸습니다.

문제 이름을 해석하면 “… 그리고 그들은 행복하게 살았답니다.” 정도인 것 같습니다.

동화의 마무리 멘트 같은 느낌이네요.

풀이

a의 범위가 0~63 인 것에 착안하여, input과 output을 6개의 2진수 비트 로 나타내면 다음과 같습니다.

Test case	input(binary)	output(binary)	비트 이동
#1	000010	000010	2->2
#2	000101	011000	1->5, 3->4
#3	100011	110010	1->5, 2->2, 6->6

표의 비트 이동과 같은 규칙으로 비트가 이동했음을 알 수 있습니다.

예시만으로는 4번째 비트와 5번째 비트가 어디로 이동하는지 알 수 없으므로, ~~운으로 찍었습니다.~~

(더 정확한 풀이를 아시는 분은 dongbin1999@inu.ac.kr 로 알려주세요!)

#include <cstdio>
using namespace std;
 
int main(void)
{
    int a;
    scanf("%d", &a);
    int b[6] = { 0 };
    for (int i = 0; i < 6; i++)
        if ((a & (1 << i)) != 0)
            b[i] = 1;
    int ans = 0;
    if (b[0])
        ans += 16;
    if (b[1])
        ans += 2;
    if (b[2])
        ans += 8;
    if (b[3])
        ans += 4;
    if (b[4])
        ans += 1;
    if (b[5])
        ans += 32;
    printf("%d", ans);
    
    return 0;
}

D번 문제입니다. 오른쪽 아래Problem tags에 chinese remainder theorem²라고 나와있는데, 저게 왜 필요한지 잘 모르겠습니다. 만우절 디테일에 신경 쓴 듯합니다.

풀이

A 뒤에 나오는 숫자를 2로 나눈 나머지를 출력하면 됩니다.

#include <cstdio>
using namespace std;
 
int main(void)
{
    int a;
    char c;
    scanf("%c", &c);
    scanf("%d", &a);
    printf("%d", a % 2 == 0 ? 0 : 1);
    return 0;
}

여기서부터는 제가 풀지 못한 문제들이라 짧게 리뷰하고 넘어가겠습니다.

E번 문제입니다. 푸는 데 상당히 많은 시간이 걸릴 것 같은 문제입니다.

풀이

input좌표가 그림 속 얼굴 안쪽이면 IN을, 바깥쪽이면 OUT을 출력하는 문제 같습니다.

저는 주어진 시간인 2시간 내에 풀지 못할 것 같아 넘겼습니다. ~~귀찮아서~~

F번 문제입니다. 풀이가 너무 궁금하여 다른 분들의 코드를 참고했는데, 저는 대회 시간이 10시간이었더라도 못 풀었을 문제입니다. 풀이를 보시기 전에 한 번 고민해보세요!

풀이

풀이 보기

주기율표의 원소기호만 사용하여 `input`의 단어를 만들 수 있으면 `YES`를, 아니면 `NO`를 출력하는 문제입니다. 예를 들어, GENIUS -> 'Ge(저마늄)' + 'N(질소)' + 'I(아이오딘)' + 'U(우라늄)' + 'S(황)'으로 표현이 가능하므로 'YES'입니다.

G번 문제, H번 문제는 코드를 참고해도 모르겠습니다..

특히 H번 문제는 UnknownX라는 언어로 제출 언어 제한이 걸려있습니다.

H번 문제의 풀이 자체는 n의 double factorial을 mod로 나눈 나머지를 구하라는 문제인데, C++ 코드를 그대로 제출하니 Compilation error를 받았습니다.

제출했던 코드는 아래와 같습니다.

#include <cstdio>
using namespace std;
 
int main(void)
{
    int temp;
    scanf("%d", &temp);
    int n = temp / 1000;
    int mod = temp % 1000;
    int ans = 1;
    for (int i = n; i > 0; i -= 2)
        ans = (ans * i) % mod;
    
    printf("%d", ans);
    return 0;
}

4. 결과

제 성적입니다.

초록색 + 는 맞힌 문제, + 뒤의 숫자는 틀린 횟수를 나타냅니다.
틀린 횟수 당 10분의 패널티가 주어집니다.
-2 는 2번 틀리고 풀지 못했음을 나타냅니다.
Tried는 각 문제당 제출된 코드 수, Accepted 는 그중 맞힌 사람의 수를 나타냅니다.

혹시 코딩에 관심 있으신 분은 코드포스 대회에 참여해보시는 걸 추천합니다!

여기까지 후기였습니다. 긴 글 봐주셔서 감사합니다!

Codeforces는 대회 성적을 반영한 rating시스템이 있습니다. ↩
중국인의 나머지 정리 ↩