대회 이름에 대한 좋은 아이디어가 없어서 대회 이름에 공백 하나만 넣었습니다. 이렇게 했더니 12906번 문제처럼 대회 목록에서 대회 링크를 클릭할 수 없게 되었습니다. 따라서 대회를 참가하기 위해서는 개발자 도구 등을 통해 대회 링크를 찾거나, BOJ 대회 링크 형식인 https://www.acmicpc.net/contest/view/ 뒤에 대회 번호인 965를 입력하여 진입해야 했습니다. 대회 진입부터 어려웠기 때문에, 참가자의 편의를 위해 대회 홍보글에 대회 링크를 걸어두었고, 대회 시작 직전에 한 번 더 홍보 게시판에 대회 링크를 올렸습니다.
- 문제 출처를 클릭하는 것도 어렵게 되었습니다...
- 문제 번호 역시 좋은 아이디어가 없어서 문제에 할당할 BOJ 번호를 그대로 문제 번호로 사용했습니다. 문제 배점도 문제 번호와 같도록 했습니다. 이로 인해 문제별 배점의 차이가 약간 있었습니다.
- 문제 번호의 순서는 문제를 정할 당시에 등록했던 순서로, 난이도와 큰 관련이 없습니다. 다만 더 많은 사람들이 solved.ac 배경과 뱃지를 얻을 수 있도록, 쉽게 부분 점수를 받을 수 있는 문제를 맨 앞에 배치하기로 하여, 대회 문제 순서는 문제 번호의 역순으로 정했습니다.
- 하지만 점수를 받지 못하더라도 solved.ac 배경과 뱃지를 얻도록 조건을 정하면서 큰 의미는 없어졌습니다.
출제자: cozyyg, 최고 득점자: parkky (3분, 27907점)
문제 제목은 그린-타오 정리를 증명한 논문의 제목을 그대로 가져왔습니다. 하지만 문제 지문에서도 언급했듯이 그린-타오 정리는 이 문제를 푸는 데 별 도움을 주지 못합니다. 출력하려는 등차수열의 초항을
일단
전세계의 많은 사람들(그리고 컴퓨터들)이 소수만으로 이루어진 등차수열을 찾는 노력을 했으며, 2023년 4월 30일까지 발견된 가장 긴 소수 등차수열은 길이가
아무리 구데기컵이라고 해도 세계 기록을 깨라고 할 수는 없으니, 무언가 함정이 있음을 유추할 수 있습니다.
출제자: jh05013, cozyyg, 최고 득점자: mickeyjung (437분, 27906점)
이 문제는 원래 UCPC의 call for task에 출제하려고 계획했던 문제였으나, 예제 설명이 한 페이지를 차지한다는 것을 깨닫고 포기했습니다. 지문에 그 흔적이 남아 있습니다.
질문이 1개밖에 없습니다. 첫 번째 질문을 하기 전에 각 출제자가 알고 있는 사실은 "흰색 모자가
서브태스크 2로 넘어가기 전에, 일단 예제 1을 이해하는 것부터 쉽지 않습니다. 아무것도 볼 수 없는 세 번째 출제자가 대체 어떻게 자신의 모자 색을 안 것일까요? 이는 나머지 출제자가 자신의 모자 색에 대한 정보를 주기 때문입니다. 출제자를 차례로 A, B, C라고 합시다.
- 첫 질문에서, 만약 B와 C의 모자가 모두 검은색이었다면 A는 자신의 모자가 흰색임을 알 수 있었을 것입니다. 그런데 A가 자신의 모자 색을 모르겠다고 했으므로 B와 C 중 적어도 한 명은 모자가 흰색이어야 합니다. 이 사실은 C뿐만 아니라 B도 도출해낼 수 있습니다.
- 두 번째 질문에서, 만약 C의 모자가 검은색이었다면 B는 자신의 모자가 흰색임을 알 수 있었을 것입니다. B와 C 중 하나는 모자가 흰색이기 때문입니다. 그런데 B도 자신의 모자 색을 모르겠다고 했으므로 C 자신의 모자는 흰색입니다.
즉 C가 자신의 모자가 흰색임을 알 수 있는 이유는, 자신의 모자가 검은색이라면 나머지가 어떻게 모자를 쓰든 A와 B가 모두 모르겠다고 대답할 수 없기 때문입니다.
우선 자신의 모자 색을 안다는 것이 무엇을 의미하는지 생각할 필요가 있습니다. 모든 출제자가 완전히 논리적으로 사고하므로, 이 문제의 입력으로부터 출력을 정확하게 알아낼 수 있다고 가정합시다. 지금까지의 질문 및 자신이 볼 수 있는 모자의 색은 정확히 알고 있으므로, 자신의 모자를 포함하여 자신이 볼 수 없는 모자
각 사람마다 "후보의 집합"을 관리하고, 대답이 나올 때마다 모든 사람의 모든 조합 후보에 대해 질문을 던진 뒤 같은 대답이 나오지 않는 후보를 모두 제거하면 됩니다. 그런데 어떻게 모든 조합에 질문을 던질까요? 그러려면
위에서 본 풀이는 후보를 관리하는 방법이 너무 복잡합니다. 만점을 받기 위해서는 다음과 같이 후보를 찾는 법을 간소화해야 합니다.
출제자들이 쓰고 있는 모자의 조합
출제자: kipa00, 최고 득점자: lcr7324 (298분, 27905점)
출력 설명을 드래그하여 메모장 등에 복사-붙여넣기하면 아래와 같이 숨겨진 문구가 나옵니다.
첫 줄에, 모의 전투에서 양 선수가 최선을 다하는 경우 이기는 사람의 이니셜을 영어 대문자 두 글자로 출력합니다.
문제 설명 끝에 "서연이"와 "서윤이"가 싸운다고 되어 있었기 때문에, 어떤 언어로든 입력을 읽지 않고 SY를 출력하면 됩니다.
정확히 같은 방식으로 풀 수 있는 기 출제된 문제가 있습니다.
디스크립션을 신경써서 읽기 불편하게 만들었습니다. 힌트를 드리기 위해서였습니다.
- 특히 입력 조건을 굉장히 세심하게 다듬었는데, 입력을 읽는 프로그램을 짜기가 상당히 힘겹게 되어 있습니다. 다음을 참고하세요:
- 입력 각각의 최대 제한이 없고 전체 파일 크기의 최대 제한만 있는 점
- 문제 정보가 서너 줄로 들어온다는 점
- (존재하지도 않는 게임에) 상식적인 수준의 입력이 들어온다는 점
- 트리비아(혹은 말장난)를 일부러 많이 넣었습니다. 아래는 모두 지문만으로 알 수 있는 점들입니다:
- (solved.ac의) 알고리즘 분류는 2023년 4월 1일 현재 196개입니다.
- 196은 142입니다.
- 특별한 말이 없으면, log는 자연 로그입니다.
여러분은 모두 문제를 잘 풀고 싶습니다.
- 변수를 하나의 알파벳으로 쓰지 않고 폰트로 구분한다는 점도 구데기성을 가미하며 지문을 읽기 불편하게 만듭니다.
출제자: kipa00, 최고 득점자: jhuni (670분, 13952점)
동영상을 전부 볼 필요도 없이, 첫 문장만 들으면 해결할 수 있습니다. 이 문장은 "만일 1행 1열, 2행 3열, 4행 1열에 X가 있고, 4행 2열에 O가 있으면 O가 이긴다"로 요약할 수 있습니다.
주어지는 판은 다음과 같습니다:
-
$D=1$ 이므로 O의 차례입니다. - X가 1행 1열, 2행 3열과 4행 1열에만 있으므로, 4행 2열은 X가 아닙니다.
따라서 4행 2열이 O라면 최선을 다할 필요도 없이 O의 승리이고, 아니라면 4행 2열을 O로 채우면 어떻게 해도 O의 승리이므로 이 서브태스크는 O가 최선을 다하면 O가 이기는 판입니다.
그런데 첫 단어만 비교한다는 뜻은 양측이 최선을 다할 때 누가 이기는지 출력하라는 뜻입니다. 모든 테스트 케이스에 대해 KIPA WINS 혹은 KIPA DECLARES A WIN을 출력하면 이 서브태스크를 맞을 수 있습니다.
직간접적으로 동영상을 전부 보아야 합니다. 몇 가지 가능한 방법을 소개합니다.
- 동영상을 전부 받아적습니다. 1.5배속, 2배속 등으로 받아적어도 되고, 필요한 정보만 받아적어도 됩니다. 예를 들어 "아니고 4행 2열이 X라면 O가 이겼습니다"에서 필요한 정보는
42XO(혹은 구현에 따라아니고 42XO)뿐입니다. - 유튜브의 자막 기능을 이용합니다. 자막을 복사-붙여넣기한 후, 들으면서 틀린 부분을 바로잡습니다. 모두 입력해야 직성이 풀리신다면 이 방법이 좋을 수 있습니다.
- 자막을 복사-붙여넣기한 후, 일부 변형을 자동수정한 후 확인합니다. 자막이 잘못된 부분은 "아니고 사행사요를 요구라면 x가 이겼습니다" 등 알아들을 수 있는 정도에서의 변형인 경우가 많기 때문에, 이들을 찾아 바꾸기로 모두 수정한 뒤 틀린 부분만 바로잡습니다.
-
FFT를 활용합니다. 영상을 잘 보다 보면, 같은 구문을 말할 때 어투가 이상하게 비슷한 것을 알 수 있습니다. 따라서, 다음과 같은 방법을 쓸 수 있습니다.
- 공백이 충분히 길 때 음성을 나누어 1 249개의 음성을 얻습니다.
- 같은 음성
${A_{i}}$ 와${B_{i}}$ 에 대해 다음 식이 상당히 최소화되리라고 기대합니다:$\displaystyle \min_{d} \sum_{i} \left(A_{i} - B_{i+d}\right)^{2}$ - 시그마 식 안쪽의 전개
$\displaystyle \sum_{i} \left(A_{i} - B_{i+d}\right)^{2} = \sum_{i}A_{i}^{2} + \sum_{i}B_{i}^{2} - 2 \sum_{i} A_{i} B_{i+d}$ 를 통해, 이 식은$\displaystyle \max_{d} \sum_{i} A_{i} B_{i+d}$ 를 구하는 것과 같고, 이는$A$ 혹은$B$ 중 한 쪽을 뒤집은 후 FFT를 통해 계산할 수 있습니다. - 어차피 제출할 것도 아니므로, FFT는
numpy나scipy등의 라이브러리를 이용합시다.
- 시그마 식 안쪽의 전개
- 계산된 전체 식을 음성의 길이인
$N$ 으로 나눈 평균값을 보면, 적절한 기준점이 반드시 보입니다. 이 위치를 기준으로 같은 음성과 다른 음성을 나누어 107개의 분류를 얻습니다. 이들의 전체 길이는 8분 정도입니다!
FFT를 활용한 방법과 자막을 활용한 방법을 합치면 청력 손실이 있어도 전체 스크립트를 알아낼 수 있음을 확인했습니다.
이들 방법을 활용하여 얻은 스크립트를 통해, 16개 칸이 모두 채워진 경우에 대해 어느 쪽이 승리했는지를 판단하여 KIPA WINS나 HAVANA WINS를 적절히 출력해 주면 됩니다.
현재 상황이 어느 한쪽의 승리 선언 조건을 만족하는지 판단해야 합니다. 이를 위해 불완전한 판으로 승리 조건을 파고들어가는 방법을 사용합니다.
- 판단을 해야 하는 칸이 이미 채워져 있으면,
if와else중 어디로 가야 하는지를 정할 수 있습니다. - 채워져 있지 않으면, 몇 가지 가능성이 있습니다.
- 결정된 칸 중 O가 8개라면, 판단해야 하는 칸은 X로 결정되어야 합니다. 이렇다면 칸이 이미 채워진 경우로 환원됩니다.
- 반대로 결정된 칸 중 X가 8개라면, 판단해야 하는 칸은 O로 결정되어야 합니다. 마찬가지로 칸이 이미 채워져 있다고 생각할 수 있습니다.
- 둘 다 아니라면 그 칸은 O가 되는 것과 X가 되는 것이 모두 가능합니다. 칸을 각각 해당하는 문자열로 채우고, 양쪽을 동시에 탐색합니다.
끝까지 갔을 때, 최종적으로 승자가 결정된 모든 노드가 O이면 KIPA DECLARES A WIN를, X이면 HAVANA DECLARES A WIN을 출력하면 됩니다. 둘 다 아니라면, 이 서브태스크에서는 승리 선언을 할 수 없는 경우를 구분하지 않으므로, KIPA WINS와 HAVANA WINS 중 아무거나 하나를 출력하면 됩니다.
이때, 모든 칸이 다 채워진 경우에 주의하세요. 이 경우는 (당연하게) 탐색한 모든 노드가 같은 승자를 지시하지만, 정답이 * DECLARES A WIN이 아니고 * WINS 꼴입니다.
시간 복잡도는 트리의 노드 개수를
일반적인, "최선을 다할 때 승리하는 사람을 찾는" 방법을 이용하면 됩니다. 다음과 같은 규칙입니다. (P는 키파 혹은 아바나입니다. 원칙대로라면 양 경우를 모두 써야 하지만 귀찮으므로 P로 쓰겠습니다.)
- 열여섯 개의 칸이 모두 채워진 경우, 일단 승리 조건에 따라 승리를 선언한다고 생각합니다.
- 칸이 조금씩 덜 채워진 경우를 생각하며,
- 현재 차례인 사람이 어떤 칸에 두든 P가 승리를 선언한다면, P가 승리를 선언합니다.
- 현재 차례인 사람이 어떤 칸에 두든 P가 [승리를 선언하거나 이긴다면], P가 이깁니다.
- 아니고 현재 차례인 사람이 P이며 P가 이기는 칸이 존재한다면, P가 이깁니다. 그렇지 않으면 P가 아닌 사람이 이깁니다.
서브태스크 3에서와 마찬가지로, 열여섯 개의 칸이 모두 채워진 다음에는 출력을 조심해야 합니다: * DECLARES A WIN이 아니고 * WINS를 출력해야 합니다.
시간 복잡도 계산이 대단히 껄끄럽습니다. 대신 전처리에 사용되는 기초 연산의 수를 생각합니다. 채워진 칸의 수
-
$i < 16$ 이면, 판은 총${16 \choose i}{i \choose \lfloor i/2\rfloor}$ 개의 경우가 있고, 각각의 경우에 대해 빈 칸$(16 - i)$ 개를 고려해야 합니다. 즉,$\displaystyle \sum_{i=0}^{15} {16 \choose i}{i \choose \lfloor i/2\rfloor} \cdot (16-i) = 55\,873\,872$ 회의 기초 연산이 일어납니다. -
$i = 16$ 이면, 판은 총${16 \choose 8}$ 개의 경우가 있고, 각각의 경우에 대해 승리 조건을 최대$16$ 회 확인하므로, 많아야$\displaystyle 16 \cdot {16 \choose 8} = 205\,920$ 회의 기초 연산이 일어납니다.
전처리 이후 시간은
트리를 열심히 압축합니다.
- Python의
base64.b85encode와zlib.decompress를 적극 활용합시다.$M = 2023$ 개의 노드가 있는 트리를 884 바이트에 만들어낼 수 있습니다. - 문자열을 비교할 때
if a=='a':대신if'a'==a:를 이용하면 1바이트를 아낄 수 있습니다. - Performant Python을 이용합시다:
- 메모리와 속도를 위해
bytearray를 사용합니다. C/C++의unsigned char배열과 비슷합니다. - 속도를 위해 list comprehension을 적극 사용합시다.
for문을 그냥 도는 것에 비해 최대 15배까지 빠르다고 알려져 있습니다. -
if는 우리의 주적입니다.1 if'O'==b[x]else 0대신2-('O'==b[x])를 활용해 봅시다. 속도도 빠르고 바이트도 아낍니다. - 한 변수에 타입이 섞이면 느려집니다. 이왕이면
None을 지양합시다.
- 메모리와 속도를 위해
이 방식으로 구현된 출제자의 코드는 1 722 바이트입니다. 코드가 엄청나게 기괴하지는 않습니다. 이와 같은 방식으로 만점을 받은 코드는 여기에서 확인하실 수 있습니다.
시간 복잡도는 서브태스크 4와 같습니다.
다음과 같은 과격한 가정을 하겠습니다:
- 각 칸에 점수가 배정되어 있습니다. O나 X를 그리면 해당 플레이어가 그 칸의 점수를 가져갑니다.
- 모든 칸이 다 채워졌을 때, 점수를 합산하여 높은 쪽이 승리합니다.
- 모든 경우에 대해 점수의 합이 같은 경우는 일어나지 않습니다.
이를 만족하는 점수 배정을 찾으려고 노력해 봅시다. 변수 16개와 부등식 6 435개짜리 linear programming 문제가 되었습니다. 다음과 같은 사실을 활용하면 좋습니다:
- O와 X가 한 쌍만 뒤바뀐 방정식들을 비교하다 보면, 크기 관계를 알아낼 수 있습니다.
- 아이디어는, 예를 들어, 어떤 배치가 O가 이기는 배치였는데 O와 X가 한 쌍만 뒤바뀐 경우 X가 이긴다면, 원래 O가 그려져 있던 그 칸이 X가 그려져 있던 칸보다 점수가 클 수밖에 없다는 점입니다.
- 전체 방정식을 비교하면 각 칸에 배정된 모든 점수의 상대적인 크기를 알아낼 수 있습니다.
- 이는 탐색 공간을
$1/16!$ 로 줄여줍니다!
- 유클리드 거리 공간
$\mathbb{R}^{16}$ 에서, 해와 만족하는 부등식들과의 (최소) 거리$D_{c}$ 와 만족하지 않는 부등식들과의 (최소) 거리$D_{i}$ 에 대해,$D_{c} - D_{i}$ 를 최대화합니다.- 아이디어는 다음과 같습니다: 만일
$D_{c} > D_{i}$ 이면,$D_{i}$ 의 실제 부등식 방향으로$D := (D_{c} + D_{i}) / 2$ 만큼 움직이면 부등식이 최소한 하나 더 만족됩니다. - 이동 거리
$D$ 는$D_{i} < D < D_{c}$ 를 만족하므로,$D$ 만큼 어느 방향으로 움직여도 이미 만족한 부등식은 계속 만족합니다. -
$D_{i}$ 의 실제 부등식 방향으로$D$ 만큼 움직이면, 해는 이 경계를 넘게 되므로 이 (만족하지 않았던) 부등식을 만족하게 됩니다.
- 아이디어는 다음과 같습니다: 만일
- 이 값을 최대화하는 데에 Random Walk, Gradient Descent, Simulated Annealing 등의 방법을 활용할 수 있습니다.
이 점수를 찾으려고 하면, 놀랍게도, 각 칸의 점수를 알아낼 수 있습니다! 점수를 알아내면 각 서브태스크의 코드가 굉장히 간단해집니다.
- 게임이 끝난 경우 승자의 판정은 점수를 모두 더해서 이긴 쪽이 됩니다.
- 게임이 끝나지 않은 경우 P의 승리 선언 조건은 P가 남아 있는 것 중 점수가 가장 작은 (대충) 절반을 가져가고, P가 아닌 사람이 나머지를 가져가도 여전히 최종적으로 P가 이기는 경우입니다.
- 게임이 끝나지 않았고 어느 쪽도 승리를 선언할 수 없는 경우, 현재 차례인 사람부터 번갈아가며 차례로 점수가 가장 높은 것부터 가져갔을 때 최종적으로 이기는 사람이 승리합니다.
PS를 조금만 해 보셨다면 이들 코드는 합해 봐야 천 바이트도 안 나올 것 같다는 생각이 드실 것입니다. 실제로 PS 헤더를 안 쓰기만 해도 무난하게 통과할 수 있습니다. 코드를 길게 짜기로 유명한 출제자가 코드 제한을 전혀 신경쓰지 않고 짜서 1 902 바이트가 나왔습니다. 이와 같은 방식으로 만점을 받은 코드는 여기에서 확인하실 수 있습니다.
시간 복잡도는
이 문제는 1부터 32까지 중에서 합이 홀수가 되는 16개를 골라 점수를 배정한 뒤 노드의 개수가 2 023개인 트리를 만들어 낸 문제입니다. (점수를 정수 형태로 다시 찾을 수 있을까요?)
서브태스크 2를 푸는 방법에서 짐작하셨겠지만, 실제로 1시간 동안 녹음하지는 않았고, 다음의 과정을 거쳐 만들었습니다.
- 다음의 스크립트 중 쓰이는 것을 녹음합니다. 총 8분 30초, 107개였습니다.
- "만일 n행 m열이 O/X라면,"
- "만일 n행 m열이 O/X라면 O/X가 이겼습니다."
- "아니고 n행 m열이 O/X라면,"
- "아니고 n행 m열이 O/X라면 O/X가 이겼습니다."
- "아니라면 O/X가 이겼습니다."
- 노이즈를 제거한 뒤 미리 짜인 스크립트에 맞게 음성을 잘 이어붙입니다.
- 이 과정에서 중간 공백을 적절한 시간 동안 넣어줍니다.
- 중간 공백 시간을 구하기 위해 실제로 스크립트의 일부를 녹음한 다음, 그 공백 길이의 평균과 (표본)표준편차를 갖는 표준정규분포를 이용했습니다.
- 가우시안 노이즈를 적절히 줍니다.
문제 배점은 모두 소수입니다. 비율이 적절한 소수를 찾느라 제 컴퓨터가 고생을 좀 했습니다.
지문의 KIPA IS CUTE와 KIPA WINS A MILLION DOLLAR는 제 바람입니다.
출제자: havana723, 최고 득점자: index (1분, 27903점)
문제를 푸는 계정의 아이디에 따라 다양한 풀이가 존재합니다.
대부분의 아이디에서 가능한 풀이는 아희, Golfscript, Whitespace 등 알파벳을 사용하지 않는 언어로 작성하여 제출하는 것입니다.
아래는 havana723의 Golfscript 예시입니다.
104 96 1+ 118 96 1+ 110 96 1+ 55 50 51 ]""+아래는 kipa00의 아희 예시입니다.
받발밝따따빠북
두벐뻐멓뻐멓더
맣빠밣타맣밦붏
키파하멓멓뻐떠
이외에도 아이디에 특정 문자들이 들어가 있지 않다면 Python, C++, C 등의 언어로 풀이가 가능합니다.
아래는 cozyyg의 Python 예시입니다.
print("\x63",end="")
print("\x6f",end="")
print("\x7a",end="")
print("\x79",end="")
print("\x79",end="")
print("\x67",end="")또한, 아이디에 어떤 문자가 들어있더라도 Python에서 정답을 받을 수 있습니다.
𝓅𝓇𝒾𝓃𝓉(𝒸𝒽𝓇(𝓁𝓮𝓷(" ")))가장 예상하지 못했던 풀이는 rhdqor213님의 C99 풀이로, 다음과 같습니다.
a[]={L'煤'<<8<<8|L'桲',L'ㄲ'<<8<<8|L'牯',L'ਲ਼'};
main(){puts(a);}인생은 불공평합니다.
출제자: jh05013, 최고 득점자: sait2000 (6분, 27902점)
Bigint's really feel like a neat computer science toy most of the time. We've got them, but what actually uses integers larger than 64 or 128 bits?
2020년에 1,000,000 자리 이상의 정수를 파싱하면 제곱 시간 알고리즘으로 인해 매우 오래 걸린다는 점이 보안 결함 목록(CVE)에 등록되었다. 그로부터 2년 후인 2022년, 파이썬이 긴급 패치되면서 4,300 자리보다 긴 정수를 파싱하려고 하면 오류를 내게 되었고, 이는 당시 큰 파장과 논란을 불러일으켰다. 이 제한을 해제하려면 sys.set_int_max_str_digits()을 사용해야 한다.
BOJ에서는 이 제한을 기본적으로 해제하기 때문에, 큰 수 A+B 등의 문제에 재채점이 진행되면서 대부분의 코드가 런타임 에러로 바뀌게 되는 일은 볼 수 없게 되었다.
관련 링크:
- CVE-2020-10735
- cpython issue #95778: CVE-2020-10735: Prevent DoS by large int<->str conversions
- Python doc: Integer string conversion length limitation
- Int/str conversions broken in latest Python bugfix releases
- sympy issue #24033: int/str conversions broken by latest CPython bugfix releases
- A Python security fix breaks (some) bignums
- cpython issue #96834: FAQ for CVE-2020-10735
출제자: jh05013, 최고 득점자: sait2000 (187분, 27901점)
BOJ 1291번 이면수와 임현수를 바탕으로 만들어진 문제이다.
메갈루젼 언어는 구데기 유니버스의 인공어이기 때문에, 이 글을 쓰는 현재 외부 자료가 존재하지 않는다. DODPOLIBIDEPOLHEILA KIEM-ZEIN-JOAN-LI 및 그의 번역 키엠-제인-요엉의 혁명선언을 통해 메갈루젼 언어에 대한 자료를 수집하고, 이를 바탕으로 맨 아래에 있는 박성원숭이와 아이들 문명의 제사 절차 일부를 해석해야 한다.
이 언어에 대한 주목할 만한 점은 다음과 같다.
- 명사는 a, 동사는 u, 형용사는 i로 끝난다. 명사의 복수형은 뒤에 s가 붙는다. 동사의 과거형은 뒤에 k가 붙고, 미래형은 ld가 붙는다.
- 문장은 주어-동사-목적어의 형태이고, 수식어는 대상 단어의 뒤에 붙는다.
- 많은 단어는 여러 기본 단어들의 조합으로 이루어진다. (e.g. lunsu = 배우다, pola = 사람, lunspola = 제자/학생)
- 한 단어가 비슷한 여러 의미로 사용된다. (e.g. zalpotan은 부정을 의미하는 zal과 가능성을 의미하는 potan이 결합된 말로 불가능을 의미한다. 즉 문장의 맨 앞에 zalpotan이 붙으면 (주어)가 (동사)를 할 수 없다는 뜻이다. 그러나 이의 형용사형인 zalpotani는 누군가가 어떤 일을 할 수 없다는 의미로 "어리석은"을 의미한다.)
DODPOLIBIDEPOLHEILA에 여러 수가 나오기 때문에, 이를 바탕으로 메갈루젼 계통의 수 체계를 유추할 수 있다. 특히 도움이 되는 부분은 다음과 같다.
- "1이 하나, 2와 3이 하나, 5가 하나"의 원문에서 1, 2, 3, 5를 알 수 있다. 1과 "하나"는 다른 단어로 표현됨에 유의하자.
- 그 아래 문단에는 6, 5, 25, 125, 625, 3125가 등장하고, 위에서 알아낸 1, 2, 3, 5를 대입하여 진법 및 십, 백 같은 단위 표현을 알 수 있다.
- 메갈루젼 문명은 7진법을 사용한다. 이는 BOJ 1291에도 언급되어 있는 내용이다.
- kaeznona와 boitiolnona에 대한 문단을 해석하려면 각 예시를 설명하는 문장을 먼저 해석하고, 그로부터 용어를 해석한 다음, 정의를 용어에 끼워맞춰야 한다.
- kiemnona는 예시가 없는데, 여기서 사용되는 perdu의 의미를 kaeznona 문단에서 유추해야 한다.
- 마지막으로 alnona는 위의 kaeznona, boitiolnona, kiemnona는 물론 polojgoldu와 dodnonu의 의미도 유추해야 한다. polojgoldu는 boitiolnona의 정의에서, dodnonu는 non-이 수를 뜻한다는 점과 dod-가 DODPOLIBIDEPOLHEILA의 한 문단에서 모임을 뜻하는 의미로 많이 쓰인다는 점으로부터 유추할 수 있다.
출제자: cozyyg, 최고 득점자: easteregg423 (563분, 1047점)
Connect Four는 1974년에 출시되어 많은 연구가 이루어졌으며, 1988년에 먼저 플레이하는 사람에게 필승전략이 있음이 증명되었습니다. 놀랍게도 두 플레이어가 모두 최선을 다한다면,
next_move 함수가 항상
채점기가 어떤 수를 두었는지 알아내기 위해 다음과 같은 방법을 사용할 수 있습니다.
- 채점기가 둘 수 있는 최선의 수
$a_i$ 마다, 이후에 플레이어가 두어야 할 최선의 수 중 하나를$b_i$ 로 정합니다. -
$a_1$ 을 두었을 때는$b_1$ 을,$a_2$ 를 두었을 때는$0$ 을,$a_3$ 를 두었을 때는$-1$ 을 반환하는 등의 방식을 이용하면, 채점기가 어떤 수를 두었는지에 따라 다른 점수가 나오게 됩니다. 이 점수로부터 정보를 얻어내 채점기가 둔 수를 알아낼 수 있습니다. - 이 과정을 게임이 끝날 때까지 반복합니다.
각 테스트 케이스마다 최악의 경우 각 수마다
채점기가 최선의 수를 두는 모든 경우를 처리한다면 시행착오 없이 문제를 해결할 수 있습니다. 출제자는 다음과 같은 방법으로 그러한 코드를 만들었습니다.
- 이 블로그의 글에 첨부된 소스 코드를 다운로드합니다.
- 초기 상태부터 시작해서 최선의 수로 가능한 상태들을 DFS로 방문하도록 소스 코드를 수정합니다.
- 방문할 때 후공의 수는 모두 방문해야 하지만, 선공의 수는 하나만 골라서 방문하면 됩니다.
- 각 상태마다 최선의 수를 비트마스크로 저장합니다. 예를 들어 최선의 수가
$2$ ,$4$ ,$7$ 이라면$2^1 + 2^3 + 2^6 = 74$ 를 저장합니다. - 이제 이렇게 만든 (상태 문자열, 비트마스크)의 쌍이 저장된 배열을 하드코딩하면 됩니다.
다만 상태의 개수가 많아서 이대로는 소스 코드 길이 제한에 걸립니다. 이를 해결하기 위해 두 가지 최적화 과정을 거칩니다.
- 선공의 수를 고를 때 좋은 휴리스틱을 사용하거나 처음 몇 개의 수를 수동으로 선택합니다.
- 상태 문자열을 저장할 필요가 없습니다. DFS를 똑같이 짠다면 비트마스크 값만으로도 방문하는 상태의 정보를 완전히 복원할 수 있습니다.
이렇게 했을 때 대략
채점기가 최선의 수를 두지 않는다 해도 문제를 풀 수 있을까요? 시간이 충분히 많다면 가능하겠지만, 빠른 시간 안에 답을 찾아낼 수 있을까요?
출제자: shiftpsh, 최고 득점자: cdg0228 (47분, 279점)
구데기컵 콜라보레이션 카페에서 받은 리딤 코드를 solved.ac에서 교환하면 정품 인증 키를 받을 수 있습니다. 이 키를 제출하면 정답을 받을 수 있습니다. 정품 인증 키는 핸들에 대한 비대칭 해시입니다.
문제 제목인 proprietary problem은 '사유 소프트웨어'proprietary software라는 단어의 패러디입니다. 오프라인 이벤트에 참가했어야 하는 문제임을 고려해 배점을 다른 문제의 1%로 정했습니다.