대충 난이도 순으로 정렬했다. 사실 5번째부터 10번째까지는 이견이 있을 수도 있고 나도 잘 모르겠지만 (…) 푼 사람 수와 개인적인 의견 등을 감안하여 적당히 정렬했다.
마음에 들었던 문제는 D / G / J였다. B도 풀이가 상당히 재미있다.
K. Registration
H. MultiMax
주어지는 숫자들을 크게 음수 / 0 / 양수 로 분류할 수 있는데, 곱하는 수가 많아야 세개이니, 0이 3개를 초과한다면 이들을 무시해도 되고, 양수나 음수 중에서 절댓값이 상위/하위 3등 안에 들지 못하는 수들은 목적에 따라서 그보다 절댓값이 크거나 작은 수로 대체할 수 있다. 이렇게 되면 많아야 15개의 수들이 남기 때문에, brute force로 문제를 해결할 수 있다.
실제로 우리 팀에서 민규가 풀 때는 케이스 처리로 조금 더 간단하게 푼 거 같긴 하다.. 다양한 풀이가 있을 수 있는 문제이다.
A. Closest Pair
두 점 집합이 x축에 평행한 직선 상에 있어서 문제가 단순해진다. y좌표 차이가 항상 일정한 수 (|c1 - c2|) 이기 때문에, x좌표 차이만 고려해 주면 되기 때문이다. 각각의 P점에 대해서, 이분 탐색 등으로 왼쪽 / 오른쪽으로 가장 가까운 Q점을 찾는 것을 반복하면 가장 가까운 점 쌍의 거리와 개수를 모두 셀 수 있다.
P점과 Q점을 같이 정렬한 후, x축으로 인접한 점 쌍 중 속한 집합이 다른 (P - Q / Q - P) 원소들만 봐 주면 조금 더 쉽게 구현할 수 있다.
I. Pizza Boxes
http://koosaga.com/180 의 8번 문제와 동일하다. (각 행 열의 maximum을 취하고, 총 합에서 저 문제의 답을 빼면 쉽게 풀 수 있다.)
C. Flow Graph Complexity
먼저 P가 invalid한지를 문제의 output format에 적혀있는 대로 판별해 주자. 2 / 4번 조건은 자명히 판별할 수 있고, 1번 조건은 열린 괄호를 스택으로 관리하면 어렵지 않다. 3번 조건이 문제인데, B와 L 뒤에는 괄호가 바로 와야 하고, S는 ,나 닫는 괄호로 끝마쳐져야 한다는 조건을 확인하면 된다. 1번 조건과 같이 처리하면 편리하다.
P가 valid하다는 가정을 하면, 문제가 어렵지 않게 바뀐다. Backward edge의 개수는 L의 개수와 똑같고, Forward edge의 개수는 B + (정점 - 1) 의 개수와 똑같다. (L은 정점이 나가는 forward edge를 backward edge로 바꾼 후, forward edge를 만들기 때문에 forward edge의 개수에 기여하지 않는다.) 이를 식에 대입하면 복잡도를 단순 카운팅으로 계산할 수 있다. 결론적으로 P의 validity를 판별하는 것이 문제의 거의 전부라고 할 수 있다.
G. Map Labeling
먼저 입력을 $a_i$ 순으로 정렬하자. 각각의 물체들은 $a_i$가 나열된 순서대로 배치가 될 것이다. 인접한 두 물체는 붙어 있을 수도, 사이에 공간이 있을 수도 있으며, 붙어있는 물체들은 연속된 구간을 이룬다.
$s, s+1, s+2, \cdots, e$가 연속된 구간을 이룬다고 하자. 답을 바꾸지 않고, 이 구간들을 움직여서 1. 왼쪽 / 오른쪽의 다른 구간 ($s-1$ / $e+1$) 에 붙이거나 2. $s \leq i \leq e$인 $i$번 물체의 오른쪽 끝이 $a_i$에 붙게 할 수 있다. 만약 구간들이 왼쪽 / 오른쪽의 다른 구간에 붙었다면, 여기서도 계속 이러한 논리가 반복된다.
결론적으로, $i$번 물체의 위치는 많아야 $n$개로 특정할 수 있는데, "$j$번 물체의 오른쪽 끝이 $a_j$에 붙었고, $i$와 $j$가 같은 구간에 있을 때, i의 위치" 와 같은 형태가 된다. $S_i = W_1 + W_2 + \cdots + W_i$ 로 정의하면, $i$와 $j$가 주어졌을 때 $i$번 물체의 오른쪽 끝 위치를 식으로 풀 수 있다.
이제 동적 계획법을 사용하자. $DP_{i, j} = $($i$번 물체가 $j$번 물체와 같은 구간에 속하고, $j$번 물체의 오른쪽 끝이 $a_j$일 때, $1 ~ i$까지의 최소 꺾임 수) 라고 정의하면, $DP_{n, *}$ 중 최솟값이 답이 된다. 상태 전이는 다음과 같다.
* $i-1$과 $i$가 같은 구간에 속한다. $DP_{i-1, j}$에서 가져온다.
* $i-1$과 $i$가 다른 구간에 속한다. 이러기 위해서는 $i \leq j$를 만족해야 한다. $i-1$번째가 속하는 구간을 $k$라고 했을 때, 두 구간이 겹치지 않는 지를 식으로 확인해서, 겹치지 않는다면 $DP_{i-1, k}$에서 답을 가져온다.
이렇게 상태 전이를 계산한 후, i번 물체의 위치를 확인해서 선이 꼬이는지 아닌지를 판별하면 된다. 이렇게 했을 때 시간 복잡도는 $O(N^3)$이다.
이를 $O(N^2)$로 최적화하려면 식을 풀어봐야 한다. $i-1$번째가 속하는 구간이 $k$이고, $i$가 속하는 구간이 $j$라면, $A_k - S_k \leq A_j - S_j$ 일 때만 답을 가져올 수 있다는 형태로 생각보다 깔끔하게 식이 나온다. 이 때 $k < i, j \geq i$이다. $A_i - S_i$ 순서로 초기에 따로 정렬을 해 놓자. 현재 보고 있는 $A_j - S_j$의 $j$가 $i$보다 작다면, $DP_{i-1, j}$를 참조해 최솟값을 바꿔주고 그렇지 않다면, $DP_{i, j}$에 값을 대입시켜준다. 이러한 식으로 하면 부등식을 만족하는 모든 상태 전이를 $O(N)$에 효율적으로 계산할 수 있다.
L. Telescope
2차원으로 입력이 주어지지만 실제로는 아무 의미 없다. 각각의 줄에 대해서 각 위치의 intensity를 더한 다음에, 이를 모든 줄에 대해서 더해주면 되기 때문이다. 고로 1차원에서 각 위치의 intensity를 구하는 문제를 해결하자. 1 <= p <= n-l+1 에 대해서, [p, p + l - 1] 구간에 망원경을 넣었을 때의 intensity는 sum(A[i] * B[i - p + 1]) 과 같은 형태의 식으로 나온다. 두 배열 위치의 index가 일정한 수만큼 차이가 남을 알 수 있다.
B 배열을 뒤집고 생각하면 이는 sum(A[i] * B[l - i + p]) 의 형태로 다시 쓸 수 있다. C[i] = sum(A[j] * B[i-j]) 라 하면, C[l - p]를 구하면 되는 것이다. C[i]라는 배열은 빠른 푸리에 변환을 사용해서 O(NlgN)에 구할 수 있다. 이에 관해서는 링크1링크2를 참고하라. 고로 총 시간 복잡도 O(MNlgN)에 문제가 해결된다.
빠른 푸리에 변환은 구현에 따라서 동작 시간이 상당히 차이가 나는데, 이 문제는 시간 제한도 1초라서 효율적인 구현이 필요하다. 예를 들어서, 재귀 함수를 사용한 형태의 FFT로는 통과를 받기가 힘들 것이다. 팀노트 구현은 최대한 효율적으로 해서 가자.. 본인 팀은 원래 내가 직접 짠 게 들어 있었는데, 옛날에 갈아 엎고 현재는 전명우님의 구현을 약간 변형한 FFT를 사용 중이다. 대회에서도 이 구현체를 사용했다.
F. Leftmost Segment
x축과 y축을 뒤집어서 처리하는 것이 여러모로 편리하다. 뒤집었을 경우에 문제는 대충 다음과 같은 형태로 정리된다.
" n개의 직선 f_i(x) = a_i * x + b_i가 주어졌을 때, j번 쿼리로 q_j가 주어지면, f_i(q_j) 의 최솟값을 출력하여라 "
Convex Hull Trick 자료구조를 사용하면 된다. 아마 정보올림피아드를 했다면 익숙할 것이고, 그렇지 않아도 꽤 유명한 자료구조이다. 직선들을 기울기가 감소하는 순으로 정렬하고, 스택을 사용하여 교점이 증가하는 순으로 저장해 놓는다. 각각의 쿼리는 이 자료구조에 이진 탐색을 사용하면 해결할 수 있다.
이 자료구조에 대해서는 링크1링크2링크3 을 참고하면 좋다. CHT는 DP Optimization 용도로 자주 쓰이고 그렇게 해석되는 경우가 많지만, 본질적으로 계산기하 자료구조라고 보는 것이 합당하다.
여러 직선들이 교차할 경우 가장 기울기가 작은 것을 찍어야 하는 등 자잘한 귀찮은 부분들이 존재한다. 실수 자료형을 사용하면 오차 문제로 이 부분이 굉장히 골치 아파질 수 있으니, 내부 계산을 모두 정수 자료형으로 구현하는 것을 추천한다. 예를 들어, b * d > 0일 때 a / c >= b / d는 a * d >= b * c와 같다. 다만 실제 대회에서는 실수 자료형으로도 AC가 잘 나왔다고 한다..
F와 L은 모두 중급 수준의 사전 지식이 필요한 문제들이었다. 작년 대전 인터넷 예선에서도 사전 지식을 요구하는 문제들이 나왔고, 주로 본선 대회의 힌트가 되었다. 공부해 두는 것이 좋을 것이다.
E. Jerry and Tom
문제를 해결하는 데 크게 두 가지 요소가 있는데, 먼저 어떠한 쥐가 어떠한 구멍으로 갈 수 있는지를 판별하는 것이 첫번째고, 쥐가 갈 수 있는 구멍을 모두 찾았을 때 쥐를 전부 탈출 시킬 수 있는지를 판별하는 것이 두번째다.
첫번째 파트는 두 점(쥐 - 구멍)을 잇는 선분이 주어진 다각형에 완전히 포함되는지를 묻는 기하 문제이다. 주어진 다각형의 각 변이 선분과 교차한다면 (끝점 포함) 해당 선분은 시선을 가린다고 볼 수 있고, 그렇지 않을 경우 해당 선분은 시선을 가리지 않는다. 이를 모든 변에 대해서 일일이 해주면 된다. 선분 교차는 CCW를 사용해서 O(1)에 판정할 수 있는 잘 알려진 문제이고, 입력이 작기 때문에 이러한 단순한 알고리즘으로도 문제를 해결할 수 있다. 구멍이 위치해 있는 선분을 처리할 때 주의하자.
쥐가 어떤 구멍으로 갈 수 있는지 여부를 찾았다면, 모든 쥐가 탈출할 수 있는 지 여부를 네트워크 플로우로 확인할 수 있다. source에서 쥐로 가는 용량 1 에지, 구멍에서 sink로 가는 용량 k 에지를 만들고, 쥐가 구멍에 갈 수 있다면 에지를 이어준 후 쥐의 수가 최대 유량과 일치하는 지를 확인하면 된다. 입력이 작기 때문에 어떤 플로우 알고리즘을 사용하여도 해결할 수 있다.
D. Grasshopper Route
s와 t가 s - p1 - p2 - p3 .. - t 와 같은 path로 연결되어 있다고 하자. 전략은 대략 다음과 같다. 편의상 t의 차수가 1이라 하자.
* s에서 출발하고, s를 루트로 하는 트리를 순회한 후, s에서 거리 1 이하인 정점에서 끝나는 Grasshopper route를 찾음
* p1에서 출발하고, p1를 루트로 하는 트리를 순회한 후, p1에서 거리 1 이하인 정점에서 끝나는 Grasshopper route를 찾음
* .....
* t에서 도착
실제로 t의 차수는 1이 아니지만, t에서 인접한 정점을 루트로 하는 트리를 비슷하게 순회시킨 후 t로 돌아오면 된다. 그러니까 큰 차이는 없다.. 아무튼, 전략을 이렇게 잡았으니, 이제 s는 루트고, t가 루트에 인접한 정점이라고 생각해도 좋다. 이제 다음과 같은 귀납적인 알고리즘으로 Grasshopper route를 찾을 수 있다.
* s에서 출발.
* s에서 거리 1인 정점이 d1, d2 .... dn이 있을 것이다. d1의 자식 정점들을 루트로 하는 Grasshopper route를 순서대로 찾고, 전부 찾은 후 d1을 방문한다. (자식 정점들이 없으면 d1만 방문하고 종료.)
* d2의 자식 정점들을 루트로 하는 Grasshopper route를 순서대로 찾고, 전부 찾은 후 d2을 방문한다. 여기서 거리가 3 이하로 유지됨을 확인하자.
* 계속..
* dn을 방문하면 s에서 인접한 정점에서 끝난다.
이 알고리즘 자체가 Grasshopper route의 존재성을 보여주는 증명이 되며, 재귀함수로 그대로 옮겨 적으면 구현할 수 있다.
J. Pseudoknot
$S = x^Rayxby^R$ 꼴을 만족하는 $S$의 substring $x, y$가 있을 때, $min(|x|, |y|)$의 값을 최대화하는 문제이다. 이해를 돕기 위해 원문과 다른 기호를 사용하였다.
min(...)를 최대화하는 꼴이기 때문에 답에 대해서 이진 탐색을 하면 도움이 될 것이다. 각각의 이진 탐색에서 풀게 될 문제는 $|x|, |y| \geq T$인 $S$의 부분 문자열이 존재하는가를 찾는 것이다. 이를 찾기 위해서, $x^Ray$와 $xby^R$ 이 갈라지는 위치를 고정시키고 ($i$라 하자) 문제를 해결해 보자. i의 왼쪽으로는 $y$가 존재하고, 오른쪽에는 $x$이 존재한다. 이 때 제약 조건은, $x^R$이 $S$의 prefix이고, $y^R$이 $S$의 suffix라는 것이며, 겹치지 않아야 하기 때문에 $|x| + |y| \leq min(i, |S| - i)$ 를 만족해야 한다는 것이다. $x$와 $y$는 독립적이기 때문에, 각각을 따로 최소화한다고 생각하면 좋을 것이다. 즉, $|x| \geq T$를 넘는 선에서 $|x|$ 를 최소화하고, $|y| \geq T$를 넘는 선에서 $|y|$를 최소화한 후, 둘의 길이 합이 부등식을 만족하는지 검사하는 것이다.
이제 이를 만족하는 $x, y$를 효율적으로 찾아야 하는데, Suffix array를 사용해서 이를 해결하자. $i - |y|$ 위치에서 시작하는 $y$ 문자열이 가능하기 위해서는, 거기서 시작하는 문자열과, $S$를 뒤집은 문자열의 LCP(최장 공통 접두사)가 $|y|$ 이상이어야 한다. 마찬가지로, $i + |x|$ 위치에서 시작하는 $x$ 문자열이 가능하기 위해서는, 거기서 끝나는 문자열과, $S$를 뒤집은 문자열의 LCS(최장 공통 접미사) 가 $|x|$ 이상이어야 한다. 이 접두사와 접미사를 처음에 전처리로 계산해 두자. 최장 공통 접두사 / 접미사는 $SS^R$ 형태로, 문자열 + 뒤집은 문자열을 뭉쳐둔 다음에 Suffix Array를 구해서 LCP를 빠르게 계산하면 된다.
이제, 각각의 위치 i에 대해서, $L[i] = i - $(가장 긴 가능한 $|y|$), $R[i] = i + $(가장 긴 가능한 $|x|$) 라 정의하면, 우리가 구해야 하는 것은, $j \leq i - T$이며 $R[j] \geq i$인 최대 $j$, $j \geq i + T$이며 $L[j] \leq i$인 최소 $j$를 구하는 것이다. 이는 값이 감소하는 순으로 저장된 스택을 가지고 다니면 된다. 시간 복잡도는 구현에 따라 $O(nlgn)$에서 $O(nlg^2n)$ 정도가 될 것이다.
Suffix Array를 사용하지 않고 KMP를 사용한 풀이도 존재한다. 약간 tricky한 풀이인데, 각 i에 대해서 왼쪽에 올 수 있는 가장 긴 $|y|$, 오른쪽에 올 수 있는 가장 긴 $|x|$ 를 찾은 후, 이를 Failure function을 사용해서 점차 줄여나가는 식의 풀이이다. Failure function을 그냥 써서는 안되고, sparse table의 요령으로 전처리해야 한다. 이 풀이에 대해서 자세한 설명은 생략한다. 시간 복잡도는 $O(nlgn)$이다.
B. Cycle Mean
먼저 O(nmlg(nw)) 에 문제를 해결하는 단순한 방법을 서술하고, 이 아이디어에 기반해 더 빠른 O(nm) 알고리즘을 설명하겠다. ACGTeam의 해법이며, 다음 논문에 서술된 알고리즘이기도 하다.
O(nmlg(nw)) 에 문제를 해결할 때는 답에 대해서 이진 탐색을 하는 아이디어가 유용하다. 분수 꼴의 objective function을 최적화 할 때, 결정 문제로 바꿀 경우 훨씬 다루기 편리한 식이 나오는 경우가 많기 때문이다. (이 블로그에 이미 관련 글이 있다.) 고로, 평균 T 이하의 사이클이 있는지를 판별하는 결정 문제를 해결하자.
사이클의 길이를 |C|라 할 때, sum(Wi) / |C| <= T인 사이클이 존재함은 sum(Wi - T) <= 0인 사이클이 존재함과 동치이다. 이는 모든 에지 가중치를 T만큼 감소시켰을 때, 그래프에 음수 사이클이 있는가를 판별하는 것과 동일하다. 그래프에 음수 사이클이 있는지는 벨만 포드로 판별할 수 있는데, 음수 사이클이 있다면 무한한 횟수로 갱신이 되고, 그렇지 않다면 최대 n-1번의 갱신 이후 갱신이 끊기게 된다. 고로, n번째 스텝에서 갱신이 존재하는 지를 판별하면 O(nm)에 각 이진 탐색 루틴을 해결할 수 있다.
이제 O(nmlg(nw)) 알고리즘보다 더 빠른 것을 찾아야 한다. 최소 평균 사이클 문제와 음수 사이클 판별 문제는 여러 모로 유사하니 O(nm)의 벨만 포드 기반 접근법을 계속 활용해 보자.
벨만 포드 알고리즘이, “DP(i, j) : 시작 점에서 i개 이하의 에지를 사용해 j번 정점을 방문하는 최단 경로”로 정의되는 동적 계획법 알고리즘임을 상기하자. 우리는 특별한 시작 점이 없기 때문에 시작 점이 아니라 “임의의 점”으로 테이블이 정의된다. 초기 이 DP 테이블을 만드는 데 O(nm) 시간이 소요된다. 테이블의 크기가 O(n^2) 이니, 이분 탐색은 그대로 유지하되, 이 DP 테이블만을 가지고 O(n^2)에 n번째 테이블에서 갱신이 있는지를 판별하면 효율적일 것이다. 여기서 트릭은, DP 테이블을 약간 변형해, “DPM(i, j) : 시작 점에서 정확히 i개의 에지를 사용해 j번 정점을 방문하는 최단 경로”로 바꾸는 것이다.
만약에 답을 T라고 가정했다면, DP(k,i) = min(j<=k) (DPM(j,i) - jT) 임을 알 수 있다. DP(n-1,i) > DP(n,i) 인 i가 존재할 시 음수 사이클이 있다. 고로 답에 대한 이진 탐색을 그대로 사용하여 O(n^2log(wn))에 문제를 해결할 수 있다.
정답을 받기에는 이것으로 충분하지만, 이분 탐색 없는 더 깔끔한 풀이를 소개한다. DP(n-1,i) > DP(n,i) 이기 위해서는 DP(n-1,i) > DPM(n,i) - nT여야 한다. 식을 풀고 정리하면
T > DPM(n,i) - DPM(n-1,i)
2T > DPM(n,i) - DPM(n-2,i)
3T > DPM(n,i) - DPM(n-3,i)
...
nT > DPM(n,i) - DPM(0,i)
고로, DP(n-1,i) > DP(n,i) 이기 위해서는 T > max(0<=k<N) ((DPM(n,i) - DPM(k,i)/(n-k)) 이어야 한다. 이를 모든 i에 대해 구한 후 이 중 최솟값을 취하면 된다. 이진 탐색 루틴 없이 전처리 후 O(n^2)에 문제가 해결된다.
Timeline (스포일러 주의)
K. 등록 (0분 First solve)
대회 전부터 등록을 0분 안에 풀 수 있는 가장 효율적인 방법에 대해서 팀원들과 많은 상의를 거쳤다. 등록을 0분에 풀지 못하면 등록은 사실상 WA. 등록을 0분에 풀지 못하면 팀 해체 (...) 등 다양한 얘기가 오갔다.
대회를 까보니까 돔저지 아이디와 비밀번호를 찍는 문제로 바뀌어 있었는데, 돔저지 비밀번호를 모두 까먹은 상황이라 다들 비명을 지르면서 급하게 비밀번호를 찾아 다녔다... 팀 존폐가 흔들리는 절체절명의 위기였지만, 결국 AC.
A. 가까운 점 (7분)
앞쪽 문제지는 나한테 와 있었는데, A번 문제가 뭔지 제대로 읽지는 않았지만 정황상 아무리 어려워도 기본 이진 탐색이겠구나 싶어서 등록 풀려고 앉아있던 혜아한테 바로 넘겼다.
H. MultiMax (11분)
대회 중에는 무슨 문제인지 몰랐는데 민규가 쉽대서 컴을 넘겼고 바로 맞았다.
I. Pizza Boxes (16분)
쉬운 문제다. 심지어 최근에 내가 풀어 봤다 (...) 그래서 내가 풀었다.
L. Telescope (31분 First solve)
역시 내가 모르는 문제. 혜아가 그냥 Convolution을 빠르게 구하는 문제라고 했다. 그다지 오래 걸릴 거 같지도 않고 다른 코딩할 문제도 없었기 때문에 혜아한테 핸들을 넘겨주고 그 사이에 G에 대해서 민규랑 고민했다. 31분에 퍼스트 솔브로 AC.
G. Map Labeling (56분)
ACG가 빠르게 G를 시도한 것도 있고 다른 것보다 쉽다는 느낌이 크게 들어서 (한글 번역이 있다던지.. 한글 번역이 있다던지..) 잡았는데 생각보다 잘 안 풀렸다 (...) 민규가 dp 정의를 찾아줬는데, 약간 헷갈리는 식이 가미된 n^3 풀이였다. 내가 식을 잘 풀어보니 초기 정렬 전처리로 n^2에 풀 수 있는 것을 찾아냈고, 한번의 WA 후 (식을 잘못 옮겨적었다) 맞았다.
C. Flow Graph Complexity (112분)
파싱 문제라 사실 일찍 덮어 뒀었는데 ㅋㅋ 민규가 잡더니 그렇게 어렵지 않다는 결론에 도달했는지 바로 코딩에 돌입했다. 하지만 중간에 코딩 및 풀이가 꼬이는 등의 문제가 생겨서, 그 사이에 혜아는 E를 고민 + 코딩, 나는 F를 고민.. 이 때 팀에서 세 문제가 동시에 돌아가고 있었다 (..) 중반부 CEF에서 약간 과도하게 시간을 썼다는 생각이 있다. 이후에 몇번 WA를 봤는데, 실수한 부분을 고치고, 오타 고치고 그러니 AC가 나왔다. 이 때 112분이어서 프리즈 전 퍼포먼스가 생각 이하였기도 하다 ㅠㅠ
F. Leftmost Segment (123분)
민규 혜아가 CE를 잡고 있을 때 내가 고민했던 문제. 난 사실 F가 오래 걸릴 것이라고 생각해서 일찍이 덮어둔 상태였는데, 실제로 까보니까 같은 값이 여럿일 때 최소 인덱스를 찍는 것이 아니라 최소 기울기를 찍는 것이었고, 그 외에 복잡한 부분이 없었으며 좌표 제한도 상당히 관대했다.. 일찍 잡아야 했던 문제였던 것. 일단 컴퓨터가 놀고 있지는 않아서 코딩에 필요한 수식 전개를 종이에 전부 해 뒀다. 민규가 C를 잡고, 말리면 혜아가 E를 잡고, 그것도 말리면 내가 F를 잡으면서 (...) 컴퓨터를 활용하고 있었는데 둘 다 말린 시간 사이에 코딩이 생각보다 일찍 끝났다. 하지만 예제가 안 나와서 프린트 후 다시 바통터치.
코드를 몇십분을 봤는데 도저히 예제가 안 뜨는 이유를 알 수가 없어서, 디버깅을 위해서 잠시 컴퓨터를 달라고 했다. 민폐도 이런 민폐가 없다.. 다행이도 디버깅으로 문제를 찾았다. double 변수를 scanf(“%f”,&x) 로 받았던 것이 문제. 언젠가 printf(“%lf”, x); 로 WA를 먹은 후 double 입출력에 대한 인식이 완전히 꼬여있었는데 결국 중요한 상황에서 그 문제가 터져 버렸다. 그걸 고치니 예제가 다 나왔고 한번에 AC를 맞았다. 정말 정말 화가 났지만 그래도 나름 빠르게 찾았으니 다행이라고 생각한다...
E. Jerry and Tom (138분)
혜아가 풀고 있던 기하+플로우 문제였다. C 하다가 부업으로 풀고, F 하다가 부업으로 풀고 하면서 시간이 조금씩 밀렸다. 코딩량도 많았던 문제고.. 하지만 큰 문제 없이 AC를 받을 수 있었다. 여담으로 혜아가 complex<long long>을 사용해서 문제를 풀었다. complex에 정수형을 넣는 것은 undefined behavior라서 내가 반대를 했지만 본인이 g++ 스펙을 꿰고 있다 그래서.. 아무튼, 아무 문제 없이 AC가 나왔으니 갓혜아인 걸로.
D. Grasshopper Route (154분)
CEF가 연속해서 착착 풀려서 9문제로 빠르게 올라갔다. 프리징 후여서 확실치는 않지만 그 정도면 잘 한 것 같아서 일단 한 시름 놓았고, 남은 시간동안 D를 풀면 좋은 등수가 나올 것이라고 생각되었다. 사실 D는 이거랑 비슷한 거 같아서, 초반에는 폭탄이라 생각하고 엎어뒀지만.. 고려대 DoWF 팀이 굉장히 빠르게 AC를 받고 그 이후에도 솔브가 착실히 나와서 판단이 잘못됐다 느꼈다. 암튼 내가 F를 끝나자 마자 민규랑 같이 상의했고, B를 혜아한테 맡긴 후 둘이 고민하고 있었다.
그럴듯한 접근 방법이 몇 개 나왔는데, 실제로 까보면 허점, 반례, 엄청난 구현량 (..) 등의 다양한 문제들이 있었다. 귀납적인 알고리즘을 잘 설계해야지 좋은 풀이가 나올 것 같아서, 최대한 케이스 없이 블랙 박스에 의존하는 풀이를 찾으려고 했다. 트리의 깊이를 1, 2로 줄이고 푸는 등 문제를 단순화해서 접근하니 실마리가 보였다.
찾은 풀이를 코딩하는 데에서 시간을 굉장히 많이 쓸 것 같아서 걱정이 많았지만, 귀납 가정을 착실하게 지키니까 짤 게 없었다! 생각보다 빠르게 AC를 받았다. 25분이 남았고 한 문제를 더 풀 수도 있을 것 같다는 생각이 들었다.
B. Cycle Mean (177분)
남은 시간과 스코어보드를 봤을 때 절대 두 문제를 다 풀 수는 없고, 그런 욕심을 내서도 안 되었다. J를 앞서 생각해 봤었는데, 도저히 답이 안 나와서 남은 25분동안 건드리기는 쉽지 않아 보일 것이라 생각. 어느 정도 접근 실마리는 보이는 B를 잡았다.
답에 대한 이진 탐색을 통해 O(nmlgx) 에 해결하는 방법은 대부분 알고 있었으나, 그 이상으로 줄일 실마리가 보이지 않았다. 한편, O(nmlgx)가 20억 정도라는 점, SPFA라는 알고리즘의 존재 등 여러 정황상 작정하고 타임커팅을 하면 답이 나올 법도 하다는 생각도 있었다. 시간이 많지 않았고, 리스크를 줄이기 위해서, 내가 SPFA 타임 커팅을 짜고 그 동안 민규랑 혜아가 빠른 알고리즘을 고민하는 것으로 전략을 잡았다. (정해가 벨만 포드에서 크게 다르지 않을 거 같아서, 느린 풀이를 짜도 금방 고칠 수 있을 것 같기도 했다)
하지만 혜아와 민규가 빠르게 gg를 쳤다 (...) J에 대해서 고민할까 하는 말도 나왔지만, 정말 안 좋은 전략인 것 같아서 이 때 J 문제지를 찢고(!) 다 같이 B 코드를 봐 주기로 합의를 했다. 내가 짠 SPFA 커팅은, 초기 거리를 모두 0으로 주고 relax가 일어나는 지점을 큐에 넣은 후, 총 relax 횟수가 일정 상수 C를 넘어가면 그냥 음수 사이클이 존재한다고 판단, 아니면 없다고 판단하는 식이다. 이진 탐색은 while(clock() < 1.9 * CLOCKS_PER_SEC) 까지 돌렸다 (...)
코딩은 빠르게 됐지만 예제가 오랫동안 잘 안 나왔는데, 알고보니 비주얼 스튜디오 디버그 모드라 그랬던 것이었다... 릴리즈로 바꾸니 잘 나왔다. C를 500000 ~ 5000000 사이로 다르게 잡은 6개의 코드를 동시에 제출했다. 모두 2초를 풀로 먹는 코드인거를 생각해 보면 조금 사악한 짓이긴 했다(?) 6개 중 C = 500000만 WA가 떴으며 나머지는 다 AC를 받았다. 남은 대회 시간은 2분이었는데, 스코어보드의 재미를 위해서 J에 아무 코드나 제출하고, 2등을 자축했다 (?)
