Code Jam 2019

작년과 마찬가지로 올해도 Code Jam 예선을 참 했다. 예선은 하루종일 진행되어 시간날때 틈틈히 풀면 되서 딱히 부담스럽지 않았다.

예선 문제 리뷰

올해도 파이썬을 이용해 Code Jam에 참여했다.

문제1. Foregone Solution (17점)

4가 들어간 입력을 적절히 분리하여 출력하는 문제였다. 아래와 같이 4를 1과 3이든 2와 2로 분리하든 N = A+B 형태로만 출력하면 되는 문제였다.

4     Case #1: 2 2
940   Case #2: 852 88
4444  Case #3: 667 3777

1 ≤ T ≤ 100.
Time limit: 10 seconds per test set.
Memory limit: 1GB.
At least one of the digits of N is a 4.

Test set 1 (Visible)
1 < N < 10^5.

Test set 2 (Visible)
1 < N < 10^9.

Test set 3 (Hidden)
1 < N < 10^100.

단순히 첫 문자부터 4를 찾을때마다 2와 2로 나누어주는 식으로 구현했고, AC판정을 받았다.

문제2. You Can Go Your Own Way (24점)

미로찾기 문제였는데, 처음 간 사람의 경로를 따라가지 않아야 하는 조건이 붙어있었다. 제일 먼저 떠오른 생각은 그래프로 미로를 표현한 후 BFS로 경로를 탐색하는 것이었는데, 마지막 테스트 셋의 크기가 부담스러웠다. 메모리 제한 및 시간제한에 분명히 걸릴 것 같아서, (안그래도 파이썬으로 풀고있는데..) 다른 방법을 생각해 보았다.

Test set 1 (Visible)
2 ≤ N ≤ 10.

Test set 2 (Visible)
2 ≤ N ≤ 1000.

Test set 3 (Hidden)
For at most 10 cases, 2 ≤ N ≤ 50000.
For all other cases, 2 ≤ N ≤ 10000.

1 ≤ T ≤ 100.
Time limit: 15 seconds per test set.
Memory limit: 1GB.

어떠한 경로든지 겹치지만 않으면 된다고 해서 단순히 처음 간 사람의 경로를 대칭으로 이동하는 방법으로 구현, AC 판정을 받았다.

문제3. Cryptopangrams (25점)

알파벳 암호화와 관련된 문제였다. N까지의 소수중 알파벳 갯수만큼 소수를 선택해 작은 순부터 ABCD에 매핑하고, 이후 그 두 수의 곱을 입력으로 주면 그 입력에서 원래의 문자열을 추출하는 문제였다. 문자열에는 ABC..Z가 최소 한번은 포함되어 있다.

A B C D가 3 5 7 11이라 하면, CAD라는 문자열은 73 311해서 21 33이 주어지는 식이다

 1 ≤ T ≤ 100.
 Time limit: 20 seconds per test set.
 Memory limit: 1 GB.
 25 ≤ L ≤ 100.
 The plaintext contains each English alphabet letter at least once.
 
 Test set 1 (Visible)
 101 ≤ N ≤ 10000.
 
 Test set 2 (Hidden)
 101 ≤ N ≤ 10^100.

제일 먼저 든 생각은 암호화 된 숫자들에서 제일 작은 숫자를 골라서 소인수 분해를 해보자는 생각. 문제는 큰 수에 대한 소인수 분해가 힘들다는것.. 테스트 셋 2를 통과할 가망이 없었다 그다음으로 생각한 것은 숫자들이 AB, BC, C*D와 같은 형태로 이루어져 있고 나머지 두 수는 소수이니, 두 수의 공약수를 찾으면 되겠다는 생각. 공약수야 아무리 큰 수라도 유클리드 호제법을 사용하면 빠르게 찾을 수 있으니, 이걸로 풀면 되겠다는 생각이 들었다. 그래서 처음에는 두 수의 공약수를 찾아가면서 마지막까지 찾아내고, 처음과 끝에 나머지 글자들을 붙여주게 구현을 했는데 실패. 다시 생각해보니 최초 하나의 공약수만 찾아낸 후 그걸로 나머지 숫자들을 계속 나누어주면 더 쉽게 풀리는 문제였다.

다시 구현해서 제출하니 또 실패. 정답이라고 생각한 아이디어였는데 계속해서 오답처리가 나니 짜증나서 암호화 문장을 제작하는 프로그램을 작성. TC를 몇개 돌려보니 ABABA와 같은 반복적인 문자열이 나올때, 같은 숫자가 연속되고 최대 공약수가 그냥 그 숫자 자체가 되어버리는 경우가 있다는 것을 발견했다. 이럴 경우 A~Z가 한번은 나오게 되어있다는 가정을 이용하면, 다른 숫자가 나오는 경우가 반드시 있으므로 이때 최대공약수를 구해서 반대로 값을 메꾸어 나가면 된다. 이를 이용한 코드를 제출하여 AC 판정을 받았다.

문제4. Dat Bae (34점)

N개의 컴퓨터 중 고장난 B 대의 컴퓨터를 찾아내는 문제, F번 만큼 쿼리를 날려 응답을 받을수 있다. TEST_STORE 01101 returns 111. TEST_STORE 00110 returns 010. TEST_STORE 01010 returns 100. TEST_STORE 11010 also returns 100. 0번째 3번째 컴퓨터가 고장났다고 가정했을때의 응답은 위와 같다.

4번은 인터렉션 문제이며 채점 서버에 출력을 날린 후 다시 입력을 받아 그걸 가지고 정답을 찾아내야 한다.

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 1024.
1 ≤ B ≤ min(15, N-1).

Test set 1 (Visible)
F = 10.
Test set 2 (Hidden)
F = 5.

작년에 새로 등장한 인터렉션 문제는 뭔가 로컬에서 테스트 하는 방법부터가 번거로운 느낌이라 영 적응이 되지 않는다. 사실 문제 4번까지 올 시점이 되면 이미 예선은 통과한 시점이라 파이팅이 좀 떨어지기도 한다. (어렵기도 하고…) 하지만 이번 문제들이 접근만 올바르면 몇 줄 안되는 코드로 풀려버리는 문제들이 많아 흥미로웠고, 마지막까지 도전해보기로 했다.

처음 봤을때 든 생각은 비트마스크를 이용하는 문제인가라는 생각. 1,2,3번과 마찬가지로 각각의 테스트 셋을 관통하는 풀이를 찾고 싶었는데 쉽게 접근 방법이 떠오르지 않았다. 일단 N의 크기가 2^1에서 2^10라는 점에서 테스트 셋 1의 F=10이 관련이 있겠구나 싶었는데, 그럼 5번안에는 어떻게 고장난 컴퓨터들을 분별해야 할지 잘 떠오르지 않았다. 고장난 컴퓨터의 수가 min(2^4-1, N-1)이라는 점을 이용할 수 있을 것 같았는데… 결국 해당 문제는 풀지 못했다.

나중에 풀이 접근을 보니 01010… 00110… 00001… 00000… 00000… 00000… 00000… 00000… 00000… 00000… 와 같이 각 10줄의 쿼리에 2진수 0부터 N-1 까지 날려보내면 출력에서 사라진 숫자를 통해 고장난 컴퓨터의 번호를 알수 있다.

문제는 F=5인 경우인데, 5bit으로 표현할 수 있는 크기가 2^5 = 32 뿐이다. 이때 중요한 점은 고장난 컴퓨터의 수가 min(2^4-1, N-1)이므로 고장난 최대 컴퓨터의 수는 15를 넘지 못한다. 이는 5비트 안에 충분히 포함할 수 있는 수이고, 이점을 이용해 01010…010101…10101 00110…001100…10011 00001…000011…01111 00000…000000…11111 00000…111111…11111 0, 1, 2, 3, 4… 16, 17, 18, 19, 20, 21… 27, 28, 29, 30, 31
을 반복해서 날리면, 한 구간이 통제로 소멸될 일이 없으므로 고장난 번호를 알아낼 수 있다.

마치며

알고리즘을 손에서 놓지 않기 위해 매년 참가 신청을 했고, 예선 통과라는 소기의 목표도 이미 달성했지만, 1라운드도 참가해야겠다. 부족한 점은 많고 알고리즘은 항상 어렵지만, 아이디어를 통해 문제를 명쾌하게 풀어낼 때의 쾌감이 있다.