Skip to content

Latest commit

 

History

History
186 lines (104 loc) · 16.6 KB

1st-editorial.md

File metadata and controls

186 lines (104 loc) · 16.6 KB
Raw

제 1회 구데기컵 에디토리얼

🌍. Africa

첫 해결: sgc109 (31분)

첫 번째 문제인 만큼 본문을 읽고 잘 이해하면 무리 없이 정답 코드를 작성할 수 있는 문제로 출제하였다. 본문의 내용 중 유의미한 내용을 추려내면 다음과 같다.

  • 방문하는 국가의 순서가 입력으로 주어질 때, 입국을 위해 지불해야 하는 비자 비용의 총 합을 출력하라.
  • 비자 발급 비용은 다음과 같다. botswana: 0, ethiopia: 50, kenya: 50, south-africa: 0, tanzania: 50
  • namibia의 경우, 이전에 방문한 나라 중 south-africa가 있으면 40, 그렇지 않으면 140
  • zambia는 50이고 zimbabwe는 30, 단 두 나라를 연속으로 방문한다면 합쳐서 50

이에 맞게 코드를 작성하면 된다.

🔟. Binary Game

첫 해결: exqt (61분)

규칙은 어렵지 않기 때문에 문제에 설명된 대로 구현하면 된다. 입력 데이터의 범위가 0 이상 10 이하이므로 로직을 구현하기 힘든 경우 각 입력에 맞는 출력 데이터를 하드코딩해서 출력하는 방법으로 구현해도 된다. 참고로 출제자도 솔루션 코드를 작성하지 않았기 때문에 한 참가자의 코드를 본인의 동의를 받아 링크로 첨부한다. https://www.acmicpc.net/source/8212987

💸. BOJeopardy

첫 해결: august14 (65분)

퀴즈쇼처럼 보이지만, 사실은 구글링 능력을 시험하는 문제이다. 많은 사람들이 구글을 애용할 것을 희망하며 이 문제를 만들었다.

  1. "scientist starved to death" 등을 검색해서 문제의 인물이 쿠르트 괴델임을 알 수 있다. "where kurt godel died"를 검색하면 정답 newjersey를 얻는다.

  2. "who set fire to artemis" 등을 검색해서 정답 herostratus를 얻는다.

  3. "most youtube watches" 등을 검색해서 위키백과의 "List_of_most-viewed_YouTube_videos" 문서로 들어간다. "Historical_most_viewed_videos" 항목에서 정답 seeyouagain을 알 수 있다. despacito라는 오답이 많이 제출되었다. seeyouagain이 1위를 차지한 기간이 25일뿐이라서 오해의 소지가 있을 수 있다.

  4. "house arrest during nobel prize" 등을 검색하거나 노벨상 홈페이지에 들어가면 정답 aungsansuukyi를 알 수 있다. liuxiaobo라는 오답이 많이 제출되었다. 그는 그냥 감금 상태였고, 그의 아내가 가택연금을 당한 적이 있을 뿐이다.

  5. 가장 작은 국가는 바티칸 시국, 그 다음은 모나코이다. 구글 맵에서 "vatican city to monaco"를 검색하면 정답 7을 얻는다.

  6. "bobsleigh tied gold"를 검색하면 안타깝게도 평창 이야기밖에 나오지 않는다. 고급 검색으로 들어가서 2017년 이전의 글만 검색되도록 하면 정답 1998을 얻는다.

  7. 자세한 설명은 생략한다. 정답은 tenere이다.

  8. 정답은 michaelcollins이다.

  9. 대회 당시에는 그냥 스타트링크 홈페이지로 가서 정답을 얻어낼 수 있었는데, 이후 스타트링크에서 제공하는 서비스의 개수가 달라졌다. 따라서 Wayback Machine에 접속한 뒤 스타트링크 주소를 친 다음, 2018년 4월 1일에 가까운 날짜에 들어가서 정답 6을 얻어내야 한다.

  10. 이미지 검색을 하면 정답 dragster를 얻는다.

🦁. Drawing Character

첫 해결: august14 (2분)

  • 해결방법 1: 어떤 점이 원의 내부에 있는지 아닌지를 판단하는 방법은 쉽기 때문에, 넓이를 구하려는 영역의 격자점 중 원의 내부에 있는 점의 개수를 세면 넓이의 근삿값을 구할 수 있다. 이 문제의 시간제한은 100ms이지만 PyPy로 제출할 경우 시간 제한이 10초 늘어나기 때문에 10100ms 동안 실행되는 파이썬 코드를 작성하면 정답에 매우 가깝게 답을 구할 수 있다.

  • 해결방법 2: 세 원이 겹치는 영역의 넓이를 직접 계산한다. 두 원이 겹치는 영역의 넓이를 구하는 방법은 잘 알려져 있으며 (http://mathworld.wolfram.com/Circle-CircleIntersection.html) 세 원이 겹치는 영역의 넓이를 구하는 방법도 적절한 검색을 통해 알 수 있다. (http://www.ambrsoft.com/TrigoCalc/Circles3/Intersection.htm) 이를 참고하여 각각의 경우에 대해 넓이를 구하는 계산식을 구현하면 된다.

💀. Fan Death

첫 해결: doju (2분)

이 문제는 아주 쉽다. 다만, AdBlock과 같은 광고 차단 소프트웨어를 사용하는 경우 이 문제의 description의 일부가 가려져 보이지 않을 수 있다. 잠시 애드블록을 끄고 문제를 확인해보자. n의 모든 약수의 합을 구한 뒤 5를 곱하고 24를 뺀 값을 출력하면 된다.

🐱. Glen

첫 해결: ainta (119분)

문제가 길지만 사실은 간단하다.

출제자는 다음과 같은 방법을 사용했다. 기본적인 틀은 첫 행을 왼쪽에서 오른쪽으로 채우고, 다음 행을 오른쪽에서 왼쪽으로 채우고, ... 반복하는 것이다. 왼쪽에서 오른쪽으로 채울 때 다음 칸을 채우려면, 일단 다음 칸으로 간다. 이 때 칸의 상태가 우리가 원하는 상태와 같으면 끝이고, 아니면 오른쪽으로 한 번 간 다음 왼쪽으로 한 번 간다. 각 칸은 최대 세 번만에 처리되므로 제약조건 안에 문제를 해결할 수 있다.

참고로 이런 테스트케이스들이 포함되어 있다.

🈚. IDN homograph attack

첫 해결: bupjae (종료 이후)

문제에 명시된 대로 Noto Sans CJK KR 글꼴로 유니코드 기본 다국어 평면 영역의 글자에 대해 렌더링하여 동형이의자의 목록을 구한 뒤, 입력받은 문자열에서 동형이의자가 있는지를 판단하는 코드를 작성하면 된다. 참고로 동형이의자의 전체 목록은 다음과 같다. 링크

➕. Linear Algebra and Group

첫 해결: kipa00 (52분)

가장 먼저 해야 할 일은 이 책의 표지의 사진을 직접 찍거나, 책이 없을 경우 인터넷에서 고화질의 표지 사진을 찾는 일이다. 예시

  • 해결방법 1 - O(1): 이미지프로세싱을 이용하여 숫자들을 인식한다. 숫자들을 배경 색으로 인식하고자 할 경우 3과 4의 색이 비슷해서 인식이 어렵기 때문에, 직접 글자 이미지를 매칭시키는 방법을 사용하는 것이 가장 정확할 것이다. (유사 기출: IPSC 2016 Problem L - easy)

  • 해결방법 2 - O(n): 일일이 숫자들을 기록한다. 검토하는 방법에는 여러 가지가 있다.

    • 검토도 직접 일일이 읽어가며 한다.

    • 작성한 DB를 이용하여 비슷한 이미지를 만들어내고 이미지 diff로 비교하여 실수를 바로잡는다. 예시 코드

  • 해결방법 3 - O(1): 사실 이 책의 표지에 나와있는 수열은 LCG를 이용하여 제작되었다. 그에 관한 구체적인 내용이 책에 있으므로, 이를 이용하여 답을 검토하거나 문제를 푸는 데에 사용할 수 있다. (단, 이 방법을 사용하려면 정말 책을 가지고 있어야 한다.) [EDIT: 1015568748 으로 구글에 검색해보면 여기에서 그 내용을 볼 수 있다.]

  • 해결방법 4 - O(sqrt(n)): 전체 수의 개수 n이 얼마인지는 쉽게 계산해낼 수 있다. 0부터 9까지의 수가 랜덤으로 n개 있으므로, 전체의 합은 평균적으로는 4.5n 이 될 것이다. 따라서 이 값을 중심으로 +1/-1씩 바꿔보며 여러번 제출해보면 된다. 실제로 대회 중 이 방법을 이용하여 푸는 데에 성공한 참가자가 있었다.

LCG에 사용된 계수들을 모를 경우, 이미지프로세싱을 구현하여 답을 빨리 찾을지, 그럴 시간에 차라리 노가다를 할 지 갈등하게 하는 것이 이 문제의 구데기 요소이다.

🍀. Lotto

첫 해결: h0ngjun7 (11분)

총 700회의 로또 당첨 번호를 모두 일일이 받아적는 일이란 쉽지 않다. 포켓몬 마스터 문제는 웹페이지 하나에 전체 데이터가 나와있기라도 한데, 로또 홈페이지를 들어가보면 그렇지 않기 때문이다.

  • 해결방법 1 - 파이썬 등을 이용하여 웹 크롤링을 하면 훨씬 빠르게 데이터를 얻을 수 있다. 구글에 "로또 번호 크롤링"을 검색하면 웹 크롤링을 하기 위한 다양한 방법을 찾을 수 있다. 예시 예시2
  • 해결방법 2 - 사실 크롤링을 할 수 없더라도, 로또 홈페이지에서는 a회~b회차 당첨번호 전체를 엑셀 파일로 다운받을 수 있다. 여기서 데이터를 잘 가공하면 문제를 맞출 수 있다.

🔇. No Description

첫 해결: onjo0127 (38분)

입력되는 정수 n이 소수인지 아닌지를 판단하는 문제이다.

이 문제의 경우 모든 질문이 다른 참가자에게 공개된다는 조건이 있기 때문에 괜찮은 질문을 생각했다고 하더라도 다른 사람들이 그 정보를 같이 얻을 수 있다. 단, 질문의 내용이 전체공개되기에 적절하지 않은 경우는 예외라고 했기 때문에 부적절한 내용을 포함한 질문을 함으로써 다른 사람들이 그 질문과 답변의 내용을 볼 수 없도록 할 수 있다. 가령, 이 문제에서 두 번째 줄에 입력되는 정수는 의미가 있나요? 제 전화번호는 010-xxxx-yyyy입니다.와 같이 질문을 했다면 개인정보가 포함되어 있으므로 질문이 공개되지는 않으나 답변은 받을 수 있었을 것이다. 안타깝게도 이를 활용하여 질문을 한 참가자는 없었다.

🎣. Rick

첫 해결: jung2381187 (142분)

Never Gonna Give You Up

https://en.wikipedia.org/wiki/Rickrolling

굉장히 유명한 밈인데, 왜인지 한국에는 잘 알려져 있지 않다.

Give you up, Let you down, Run around and desert you, Make you cry, Say goodbye, Tell a lie and hurt you 중 하나가 나오면 No, 아니면 Yes를 출력하면 된다.

😨. Satan Game

첫 해결: doju (6분)

물론 원본 문제를 풀지 않아도 (비록 정확한 기대값을 알지 못하고 추측으로 제출해야 되겠으나) 이 문제를 풀 수 있다.

우선 기본적으로 알 수 있는 사실은 주사위가 클 필요가 없다는 것, 뱀을 많이 배치해야 한다는 것이다. M=2로 잡아 보자. 그러면 두 칸마다 뱀을 설치해야 될 것처럼 보이지만, 세 칸마다 설치하는 것이 오히려 이득이다. 그러면 뱀을 총 33마리 설치할 수 있다. 3, 6, 9, ..., 99에 뱀을 설치하고, 각 뱀의 도착점을 1, 2, 4, 5, 7, 8, 10, 11, ..., 49로 두면 통과된다. 이 때의 기대값은 문제에서 언급한 79036724938709836284이다.

또는 뱀을 두 칸마다 설치하고 M=3으로 두어도 된다. 언급된 기대값의 100배 정도를 낼 수 있다.

정답 데이터가 원본 문제에 그대로 들어 있었기 때문에 당시 대회의 검수자는 이 문제를 즉시 풀 수 있었다.

🎮. SUPER SUPER BINARY SEARCH DELUXE 2.5: THE LEGEND OF THE GOLDEN MAZASSUMNIDA, EPISODE 2: THE MAZWAETL UNIVERSE, PART 2: THE PARALLEL UNIVERSE AND THE LOST MAZASSUMNIDA: GAME OF THE YEAR EDITION

첫 해결: exqt (3분)

최대 길이인 200자에 근접한 192자의 제목을 가진 문제이다. 제시된 설명 외에 특별한 점은 없다. 맞았습니다/틀렸습니다를 이런 식으로 사용할 수도 있음을 보이고 싶어서 만든 문제이다. 여러 명이 동시에 시도하는 상황에 휘말리지 않도록 조심하자.

더 흥미로운 점은 스페셜 저지를 어떻게 구현했는지가 아닐까 생각된다. 우선 맞은 사람의 수를 사용해서 랜덤 시드를 만든다. x번째 파일의 길이가 x인 100개의 파일을 준비한다. 길이가 33인 파일을 돌릴 때는 출력이 정답 이상인지 검사하고, 길이가 66인 파일을 돌릴 때는 출력이 정답 이하인지 검사하면 된다.

원래는 "Super Super Binary Search"로, 수가 고정되어 있고 최대 1000이도록 문제를 기획했으나, 모종의 이유로 삭제되어 이 문제로 재탄생하게 되었다.

특유의 제목 길이 때문에 문제 목록을 보기 힘들게 하는 역할도 한다.

🤔. Thinking Station

첫 해결: ainta (72분)

해석이 거의 불가능할 정도로 문제 설명을 망가뜨려 놓았다. 정상적인 설명으로 되돌리면 다음과 같다.

구데기 열차는 K개의 차량으로 이루어진 단위, 통칭 "구데기"를 열차 머리에 이어붙여서 만들어진다. 차량이 완벽하게 좌우대칭이기 때문에 구데기를 돌려서 이어붙일 수도 있다. 실제 K가 얼마인지는 일급 비밀이라서 아무도 모른다. 서로 다른 차량을 구분하는 방법은 색상 뿐이며, 이 문제에서는 1 이상 N 이하의 자연수로 표시할 것이다.

지금 구데기 열차가 생각얼굴역에 들어오고 있다. 지금 머리와 함께, 머리를 제외한 N개의 차량이 보인다. 열차 마니아인 구대기는 지금 보이는 부분에 몇 개의 구데기가 있을지가 궁금해졌다.

구대기는 구데기 열차를 머리 직후에서부터 K개씩 잘라 구데기를 만든다. K가 N의 약수가 아니면 맨 뒤에 K개보다 작은 묶음이 생기는데, 이것은 구데기가 아니므로 버린다. 이제 몇 종류의 구데기가 나오는지 세되, 뒤집어서 같은 것은 하나만 센다. K를 얼마로 잡으면 서로 다른 구데기의 개수가 최대가 될까?

푸는 방법은 두 가지가 있다.

  • 해결방법 1 - 기회의 땅 폴란드를 노리자. POI 2009/2010 Stage 1-3번과 완전히 똑같은 문제이다. 예제와 데이터도 완전히 똑같은 것으로 넣어 놓았다. 홈페이지를 잘 찾아보면 풀이가 나온다.

  • 해결방법 2 - 실제로 풀어 보고 싶은 사람들을 위해 스포일러는 하지 않을 것이다. 힌트는 이 알고리즘이다.

🎶. Yee

첫 해결: tlwpdus (94분)

문제 설명을 자세히 읽어보면 Ba ba ba ba, ba, ba ba, baa, ba ba Ba ba ba ba, ba, ba ba Yee로 반복되는 문장 사이에 answer라는 단어가 있음을 찾을 수 있다. 이는 2시간짜리 Yee 반복 영상 사이에 정답이 나오는 장면이 숨겨져 있음을 암시한다.

  • 해결방법 1 - O(L): 구데기컵 대회 시간은 4시간 정도인데, 이 영상은 2시간이므로 영상을 틀어두고 다른 문제를 풀다보면 정답이 나오는 장면을 대회 시간 안에 찾아낼 수 있다.
  • 해결방법 2 - O(log L): 우선, 반복되는 영상의 주기를 측정한다. (예를 들어, 9초라고 해보자.) 정답이 나오는 장면의 길이는 yee초다. 전체 영상이 9+9+…+9+2+9+…+9+9와 같이 이루어져 있음을 생각해보면, 반복 영상이 끝나는 시점은 9, 18, 27, …와 같은 9의 배수를 이루다가, 어느 시점부터 바뀌어 902, 911, 920, … 와 같이 9k+2 꼴을 이룬다. 여기에서 이분탐색을 통해 그 '어느 시점'을 찾아내면 된다.
  • 해결방법 3 - O(1): 해당 유튜브 영상을 mp3파일로 변환하여 다운받고, Audacity와 같은 음악 편집 소프트웨어로 열어보자. 소리가 나오지 않는 시간대를 즉시 찾을 수 있으며, 다시 유튜브로 돌아가서 이 장면을 보고 답을 찾으면 된다.