https://www.acmicpc.net/problem/31286
31286번: 철도 2
$N = 6$, $U = [0, 1, 2, 3, 4]$, $V = [1, 2, 3, 4, 5]$, $W = [3, 1, 4, 1, 5]$인 경우를 생각해 보자. 그레이더는 다음 함수를 호출한다. travel([0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [3, 1, 4, 1, 5]) 모든 가능한 $(x, y)$ 순서쌍에 대
www.acmicpc.net
이번 선발고사 4번 문제이다.
O(N^2logN^2)까지 짜서 당시 37점을 먹었는데 그 코드에서 꽤 직관적인 관찰 하나로 필요한 mst 간선만 남기면 바로 100점이 나오는 문제였다.
풀이를 듣자마자 이걸 왜 못맞췄지 소리가 절로 나왔다. 그리고 그 날 바로 정답 코드를 짜놓고 게임하러 갔다.
그리고 어제 문제가 올라왔다. 바로 제출을 했는데..
?
분명 맞을텐데 27점이 긁힌다. 그리고 27점은 트리가 특별한 케이스는 모두 맞았다는 소리고, N<=50도 틀렸단 소리다.
분명 claim은 맞을텐데 라고 생각하면서도 반례를 찾기 위해서 2시간 동안 온갖 트리를 다 그리고 온갖 증명을 했다. 근데 아무리 봐도 틀린게 없다. 그렇게 몇번 더 제출했지만 실패하고 그냥 내일 랜덤 테케 돌리자고 생각하고 잤다.
다음 날에 랜덤 트리 제너레이터 짜는 법을 대충 본 다음에 적당히 O(N^2logN^2) 코드랑 검사해봤는데 반례가 안 나왔다. 한 10분 정도 돌려놨는데 보일 기미가 없었다. 그래서 혹시? 하고 weight 제한을 기존 제한인 10^9로 하니까 반례가 바로 나왔다. 분명 어제 봤을 때는 오버플로 문제는 없었던 것 같았는데..?
아
아
괜히 int 쓰지 맙시다
