preview
8문제 중 interactive 5문제, output only 1문제라는 환상적인 문제 구성에 감동받아서 풀어보기로 했습니다.
제 점수는 아래 표에서 볼 수 있습니다.
| Day 1 | - | 382점 |
|---|---|---|
| Cluedo | Interactive | 100점 |
| Hotter Colder | Interactive | 81점 |
| Quality Of Living | Batch | 100점 |
| Languages | Interactive | 101점 |
| Day 2 | - | 300점 |
| Memory | Interactive | 100점 |
| Traffic | Batch | 100점 |
| Maze | Output Only | 0점 |
| Saveit | Interactive | 100점 |
Maze는 문제 읽자마자 던졌고, 그래서 총 682점입니다. 대회 당시 메달 컷은 금 686, 은 620, 동 538점입니다.
대부분의 참가자가 Maze에서 40점 이상 받은 것으로 보아, 10년 전 대회지만 금메달을 받을만한 성적이 나와 기쁘네요.
Cluedo (interactive, 100점)
Subtask 1은 6×10×6, 즉 360가지의 모든 경우를 시도해보면 됩니다.
Subtask 2는 20번의 추측으로 정답을 맞춰야 합니다.
20이라는 숫자가 주어진 이유를 잘 생각해보면, (Murderer에서 틀린 추측을 하는 경우의 수 5가지) + (Location에서 틀린 추측을 하는 경우의 수 9가지) + (Weapon에서 틀린 추측을 하는 경우의 수 5가지) + (정답인 경우 1가지) = 20이라는 것을 알 수 있습니다.
그러므로 이런 전략를 사용하면 subtask 2를 통과할 수 있습니다.
- 처음에 Theory(1, 1, 1)을 호출한다.
- 0을 반환할 경우 종료, 1을 반환할 경우 Murderer의 번호를 1 증가, 2를 반환할 경우 Location의 번호를 1 증가, 3을 반환할 경우 Weapon의 번호를 1 증가
- 증가된 정보를 반영해 Theory함수 호출
Hotter Colder (interactive, 81점)
50점 풀이
정답이 존재하는 범위를 절반으로 좁히는, 이분 탐색을 생각해볼 수 있습니다.
Naive하게 구현하면 중간 지점 M과 M+2에 대해 순서대로 Guess를 한 뒤 Guess의 반환값에 따라 범위를 조절해주면 됩니다.
- 반환값이 1인 경우 구간의 시작점 S를 min(M+2, E)로 이동
- 반환값이 -1인 경우 구간의 끝점 E를 M으로 이동
- 반환값이 0인 경우 M+1이 정답
이분탐색의 각 단계에서 Guess를 2번씩 호출하기 때문에 [2 lg (500)] = 18번의 Guess 함수 호출로 문제를 풀 수 있습니다.
75~77점 풀이
Guess(S)와 Guess(E)를 한 뒤, Guess(E)의 반환값에 따라 범위를 조절할 수 있습니다.
- 반환값이 1인 경우 S를 M+1로 이동
- 반환값이 -1인 경우 E를 (S+E-1)/2로 이동
- 반환값이 0인 경우 M이 정답
이 방법도 각 단계에서 Guess를 2번씩 호출하지만, 50점 풀이보다 커팅이 조금 잘 되기 때문에 16번의 호출로 문제를 풀 수 있습니다. 이 풀이를 이용하면 Subtask 4에서도 2점을 받아, 총 77점을 얻을 수 있습니다.
80~85점 풀이
삼분탐색을 하면 됩니다. Guess함수를 약 2 × log_3 N번 정도 호출합니다.
구현에 따라 80~85점 정도 받을 수 있는 것 같습니다.
Quality Of Living (batch, 100점)
최악의 경우에는 R×C개의 직사각형을 모두 봐야하기 때문에 O(RC)보다 빠른 풀이를 만들 수 없습니다. 그리고 O(RC)보다 빠른 풀이를 찾기는 힘들어 보입니다.
최솟값을 구하는 문제, 즉 최적화 문제를 결정 문제로 바꿔서 풀어봅시다. 중앙값이 X 이하인 직사각형이 존재하는지 판단하는 문제를 O(f(R, C))만에 풀 수 있다면, 중앙값의 최솟값을 찾는 문제는 O(f(R, C) log RC)에 풀 수 있을 것입니다.
주어진 이차원 배열 A에서, X보다 큰 원소는 1, X보다 작은 원소는 -1, X와 같은 원소는 0으로 바꾼 새로운 배열 T를 생각해봅시다.
- 만약 직사각형의 중앙값이 정확히 X라면 배열 T에서 직사각형 영역의 합은 0이 될 것입니다.
- 직사각형의 중앙값이 X보다 작다면 배열 T에서 직사각형 영역의 합은 음수가 될 것입니다.
- 직사각형의 중앙값이 X보다 크다면 배열 T에서 직사각형 영역의 합은 양수가 될 것입니다.
직사각형 영역의 합을 구하는 것은 누적합 배열을 이용해 O(RC)에 전처리하면 O(1)에 구할 수 있습니다.
결정 문제를 해결하기 위해 배열 T와 T의 누적합을 구하는데 O(RC), O(RC)개의 직사각형의 합을 구하는 데 각각 O(1)이 걸리므로, 결정 문제를 O(RC)에 해결할 수 있습니다.
그러므로 O(RC log RC)에 전체 문제를 해결할 수 있습니다.
Languages (interactive, 101점)
문제에서 Rocchio’s Method라는 알고리즘을 소개해주는데, 이 방법을 그대로 구현하면 약 55점을 받을 수 있습니다. 이 풀이를 발전시켜서 100점에 근접한 점수를 받을 수 있습니다.
위키백과에서 문자열을 발췌했다는 것은, 실제로 사용되고 있는 문장을 긁어온 것을 의미합니다.
문장들은 몇 개의 글자들이 연속해서 구성된 단어들의 집합이라고 볼 수 있습니다. 이 점을 이용해 Rocchio’s Method를 약간 수정해서 연속한 2~4개의 문자들을 해싱해서 함께 봐주는 전략을 생각해볼 수 있습니다.
이 방법을 이용하면 100점에 근접한 점수를 받을 수 있습니다.
Memory (interactive, 100점)
faceup()을 50번 호출해서 각 카드에 적혀있는 알파벳을 확인한 뒤, faceup()을 50번 호출해서 짝을 맞춰주면 됩니다.
Traffic (batch, 100점)
도시를 정점, 도로를 간선으로 보면 트리 구조라는 것을 알 수 있습니다.
아무 정점 하나를 잡고 DFS를 이용해 모든 정점의 서브트리의 가중치의 합을 구해줍시다.
어떤 정점 V를 선택했을 때 Traffic의 최댓값을 구하기 위해서는 V에 달려있는 간선들만 보면 됩니다.
- V에서 자식 정점 U로 가는 간선의 Traffic은 정점 U를 루트로 하는 서브트리의 가중치의 합입니다.
- V에서 부모 정점 P로 가는 간선의 Traffic은 (전체 사람 수 - V를 루트로 하는 서브트리의 가중치의 합)입니다.
두 가지 경우 모두 O(1)에 구할 수 있으므로, O(N)에 문제를 해결할 수 있습니다.
Maze (output only, 0점)
안 풀었습니다.
Saveit (interactive, 100점)
50점 풀이
decode함수에서 복원해야할 데이터는 H×N개, 즉 최대 36000개입니다.
그래프에서 최단 거리는 최대 N이기 때문에 각 데이터는 최대 10비트로 표현할 수 있습니다.
그러므로 H×N개의 데이터를 총 360,000개의 비트로 인코딩하면 50점을 받을 수 있습니다.
75점 풀이
허브 W와 인접한 두 정점 U, V를 생각해봅시다. dst(W, U) - dst(W, V)의 절댓값은 1 이하라는 것을 알 수 있습니다.
그래프의 한 스패닝 트리를 알고, 스패닝 트리에 있는 간선 (u, v)에 대해 dst(W, u) - dst(W, v)의 값들을 알고 있으면 문제의 정답을 구할 수 있습니다.
그래프의 스패닝 트리를 인코딩 하는 것은 각 정점의 부모만 인코딩하면 되기 때문에 10(N-1)개의 비트가 필요합니다.
dst(W, u) - dst(W, v)의 값은 -1, 0, 1 중 하나이므로 간선의 정보는 2개의 비트로 표현할 수 있습니다. 허브가 총 H개 있고 스패닝 트리의 간선은 N-1개이므로 2H(N-1)개의 비트가 필요합니다.
10(N-1) + 2H(N-1)은 최대 81918이기 때문에 75점을 받을 수 없습니다. 약간의 최적화가 필요합니다.
간선의 정보를 나타낼 때 모두 2개의 비트로 나타내는 것이 아니라, 1은 “0”, -1은 “10”, 0은 “11”로 표현해주면 사용하는 비트의 개수를 상당히 많이 줄여줄 수 있습니다.
제 코드에서는 최대 76495개의 비트를 사용합니다.
100점 풀이
75점 풀이를 조금 더 발전시켜 봅시다.
-1, 0, 1을 각각 2비트로 표현하면 간선들의 정보를 2H(N-1)개의 비트로 인코딩할 수 있다고 했습니다. 3가지 종류의 데이터를 2비트로 표현하는 것은 명백한 낭비이기 때문에, 이 낭비만 줄이면 70000비트 이내로 줄일 수 있을 것입니다.
방법은 간단합니다.
-1, 0, 1을 0, 1, 2로 바꾼 다음에 3진법으로 표현하고, 인코딩할 때 다시 2진법으로 바꿔주면 됩니다. 약 H(N-1)lg 3개의 비트를 사용하고, 이는 60000보다 작습니다. (로그의 밑은 2입니다.)
스패닝 트리의 정보를 넘길 때 사용하는 9990비트를 더해도 70000비트 미만이므로 100점을 받을 수 있습니다.