Eau de Cologne

문제 https://www.acmicpc.net/problem/21853 풀이 (Subtask 4) 더보기 $k$를 고정하고, Tree-DP를 사용합니다. 정점 $v$에서, 서브트리가 조건을 만족하고, $v$는 자식 정점과 연결되는 간선을 $k-1$개 이하가 되도록 할 때 가중치 합의 최솟값을 $A_v$라고 합시다. $v$에 대한 추가 조건이 없는 경우의 가중치 합의 최솟값을 $B_v$라고 합시다. 정점 $v$를 고정하고, $v$의 자식 정점의 집합을 $S$라고 합시다. 또한 $w(a, b)$를 $a$와 $b$를 잇는 간선의 가중치라고 합시다. $v$와 연결할 자식 정점의 집합을 $T$라고 합시다. 해당 자식 정점은, 부모와 이미 간선 $1$개가 이어져있기 때문에, $k-1$개의 간선만 이을 수 있습니다..

문제: https://atcoder.jp/contests/abc309/tasks/abc309_h 풀이: 더보기 $O(NM)$ 에 문제를 해결하는 것은 쉽습니다. $D_{r, c}$ 를 $A_1, \cdots, A_K$에서 출발해서 $(r, c)$로 도달하는 경우라고 합시다. 답은 $D_{N, B_1} + \cdots + D_{N, B_L}$입니다. $D_{1, c}$ 는 $A_i$에서 $c$가 등장하는 횟수입니다. $(1 \le c \le M)$ $D_{r, c} = D_{r-1, c-1} + D_{r-1, c} + D_{r-1, c+1}$입니다. $(1 \le c \le M)$ 단, $D_{r, 0}$ 와 $D_{r, M+1}$ 은 항상 $0$으로 가정합니다. 이제 이를 다항식 형태로 바꿔봅시다. $D..

문제: 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 \..