Eau de Cologne
문제: https://www.acmicpc.net/problem/8249 풀이: 더보기 정점을 무한히 일직선으로 폅시다. 이 때, $v$라는 정점은 지구를 동쪽으로 $r$바퀴 돌았는지의 여부와 함께 $(v, r)$이라는 정점으로 바뀝니다. 좀 더 엄밀히 말해서 경도 $0$인 기준선을 서->동 방향으로 몇 번 지났는지라고 생각합시다. $w_b - w_a$의 부호가 $k$와 같으면 경도 $0$ 기준선을 지나지 않습니다. 즉 $(a, r) \leftrightarrow (b, r)$ 간선이 됩니다. 만약 다르면 기준선을 지납니다. 즉, $a \leftrightarrow b$ 간선은 $(a, r) \leftrightarrow (b, r+k)$ 간선이 됩니다. 이제 $(1, 0)$ 에서 $(1, r)$ $(r \n..
문제: https://www.acmicpc.net/problem/23603 풀이: 더보기 Zeckendorf's Theorem을 살펴봅시다. Zeckendorf's Theorem: 모든 양의 정수는 인접하지 않은 서로 다른 피보나치 수의 합으로 유일하게 표현할 수 있다. (Zeckendorf Representation) 예를 들면, $64 = 55 + 8 + 1$ 처럼 인접하지 않은 피보나치 수의 합으로 유일하게 표현할 수 있습니다. 가령, $64 = 55 + 5 + 3 + 1$ 같은 표기법은 $5$와 $3$이 인접하게 됩니다. 이제 이 방식이 최소 개수의 항을 쓴 피보나치 합이라는것을 증명합시다. Claim: 양의 정수를 최소 개수의 피보나치 수의 합으로 표현하는 방법은, Zeckendorf Repre..
문제: https://www.acmicpc.net/problem/26305 풀이: 더보기 길이가 $4$ 이상인 palindrome이 있으면, 앞 뒤에 두 문자를 떼어낸 문자열도 palindrome입니다. 그러므로, 우리는 길이 $2$ 혹은 $3$의 palindrome이 생기지 않도록 유지해주기만 하면 됩니다. DP의 상태를 현재 위치 $(r, c)$와, 현재 위치에 오기 전에 방문했던 문자 $p$ 로 저장합니다. $(r, c, p) \rightarrow (nr, nc, np)$ 로의 transition은 $\lvert r-nr \rvert + \lvert c-nc \rvert = 1$ 이고, $A[r, c] = np$ 이며, $A[nr, nc]$ 가 $p$와 $A[r, c]$ 모두와 다를 때 이루어지게 ..
문제: https://www.acmicpc.net/problem/14399 풀이: 더보기 X연산을 시행한 이후에는 X>Y, Y연산을 시행한 이후에는 Y>X를 만족합니다. 즉, 최종적으로 만들 두 수가 정해져 있는 경우 가장 마지막 연산부터 X>Y인지, Y>X인지 정해가면서 계산해오면 사용한 연산의 나열을 알 수 있고, 이는 수가 정해져있을 경우 유일합니다. (유클리드 알고리즘을 떠올려도 좋습니다) 이제, 모든 1 이상 N이하의 i에 대해서 (N, i)를 만드는 연산 횟수를 세고 (이는 mod연산을 이용해서 개수만 빠르게 세어줍니다), 이 중 연산 횟수가 최소인것을 모두 골라 사전순 최소인 것을 고르면 됩니다. 가능한 길이로는 $O(\log N)$ 상한이 있기 때문에, 위 방법으로 문제를 풀면 $O(N \..
문제: https://www.acmicpc.net/problem/5477 풀이: 전반 더보기 우선, 무조건 제거되어야 하는 간선들을 찾아줍니다. 간선 $(u, v, w)$에 대해 트리에서 $u \rightarrow v$ 경로의 길이가 홀수이면, $(u, v, w)$와 트리 경로만 이용해서 짝수 사이클을 만들 수 있습니다. 그렇기 때문에 무조건 삭제되어야 합니다. 이제, 짝수 사이클이 만들어지는 조건을 찾아봅시다. $(u_1, v_1, w_1)$ 간선이 트리를 통해 만드는 사이클과, $(u_2, v_2, w_2)$ 간선이 트리를 통해 만드는 사이클은 모두 홀수 사이클입니다. 이제 두 사이클을 XOR하면 (즉, 간선 중 둘 중 한 쪽에만 포함된 간선을 찾아서 새로운 그래프를 만들면), 새로운 그래프는 사이클..
HTML 삽입 미리보기할 수 없는 소스