Problem statement정점 $n$개인 무방향 그래프 $G$가 주어진다. 정점이 $k$개인 path $P_k$와의 cartesian product $G \square P_{k}$의 cartesian product의 스패닝 트리의 개수를 구하여라. $n \le 500$, $k \le 10^{18}$.Matrix-tree theorem그래프 $G$의 Laplacian 을 $L_{G} := D_{G} - A_{G}$로 쓰자. $L_{G}$는 real symmetric matrix이고, positive semidefinite이므로 양의 실수 고윳값을 갖는다. Connected graph $G$에 대해 $L_{G}$는 rank $n-1$이 되는데, non-zero eigenvalue를 $\lambda_{1..

https://www.acmicpc.net/problem/21268솔루션에서 Tellegen's Principle을 인용하고 있어서 지난 포스트와 연관해 작성해본다. 머리 좋은 사람들은 아마 생각하지 않고도 풀 수 있을 것 같다.Without Tellegen's principle$E_{k} = \sum_{i = 1}^{n} C_{i} \prod_{j = 1}^{k} (A_{i} + B_{j})$를 답이라고 하자.$i$와 관련한 항들을 사부작거리다보면, $P_{j} = \sum_{i = 1}^{n} C_{i}A_{i}^{j}$를 미리 계산해두면 편할 것 같다.$\sum_{j} F_{k, j}x^{j} = (x+B_1)(x+B_2)\cdots (x+B_{k})$라고 두면, $E_{k} = \sum_{j} P..

BOI 2016 Swap순열 $x_1, \cdots, x_n$ 이 주어질 때, $i = 2, \cdots, n$ 에 대해 (순서대로) $x _ {[i/2]}$와 $x _ i$ 를 스왑할 수 있는 기회가 한 번씩 주어진다. 이를 적절히 사용하여 만들 수 있는 사전 순 최소 순열을 구하여라.풀이$x_i$의 후보는 $x_i, x_{2i}, x_{2i+1}$ 셋 뿐이고, 사전 순 최소를 생각하면 이 중 최소인 값이 $i$번 자리에 들어가는 것이 당연하다.(자명한 경우) $i$번 자리에 $x_i$ 또는 $x_{2i}$가 들어가는 경우, $(2i, 2i+1)$번 자리가 각각 $(x_{2i}, x_{2i+1}), (x_{i}, x_{2i+1})$로 강제된다.(비자명한 경우) 하지만 $x_{2i+1}$이 들어가는 경우..

어제 끝난 제 3회 IDTCup의 후기이다. 무려 21명이 운영진이었고, 참가자는 20명에 불과한 대회였지만 그래도 준비 과정을 적어본다. 부족한 운영 능력에도 불구하고 열심히 검수/참가해주신 분들에게 감사를 표한다. Special thanks to jhhope1. 넋두리 대회에 대한 구상이 구체적으로 나온 건 12월 전후인 것 같다. 이때는 그래도 ICPC를 다시 나가고 싶다는 생각이 있었고. 올해 휴학을 할지 말지 정해진 부분이 없었기 때문에 PS에 대한 관심이 별로 식지 않았던 때였다. 그 사이에 이렇게 급격하게 PS에 무관심해질 줄은 몰랐다. 그래서인지 막판에는 즐겁다기보단 일로 느껴져서 부담되는 부분도 있었다. 출제자들 모두 PS에 대한 관심이 떨어진 상태라, 좋은 대회를 만들자기보다는 그냥 내..

글 쓰는 법을 까먹을 것 같으니, 몇 개 되지 않는 문제들을 줏어담아보자. BOJ 20556. 둥둥섬 다리 재정비하기 20556번: 둥둥섬 다리 재정비하기 첫 줄에 섬의 수 $N$과 쿼리의 수 $Q$가 주어진다. $(1 \leq N,Q \leq 300\,000)$ 이후 $N-1$개의 줄에 걸쳐 다리들이 연결하는 두 섬 $u$와 $v$가 공백으로 구분되어 주어진다. $(1 \leq u,v \leq N)$ 이후 $Q$개의 줄 www.acmicpc.net 루트가 \(r\)로 고정되어 있다고 할 때, \(a\)개의 다리를 재정비해서 얻을 수 있는 최적의 결과는 가장 큰 \(a\)개 서브트리의 크기 합이라는 사실을 간단하게 알 수 있다. 따라서 "가장 큰 \(k\)개의 합"이 지원되는 자료구조에 서브트리들의 크기..

ICPC를 마무리하면서 2020의 PS 일정은 사실상 마무리되었다. 11/12 solve 3등으로 전체 대회를 마무리했다. 굉장히 좋은 성적을 거뒀지만, 제 역할을 못한 것 같아서 많이 아쉽다. 기대한 것도 있었고... 대회 준비 팀 구성은 작년과 같이 imeimi / jhhope1 / TAMREF로 구성된 3인팀이었다. 사실 예선 때까지만 해도 거의 기대를 하지 않았다. 학기 일정을 소화하기에도 많이 벅찼고 PS를 거의 손도 대지 않았다. 그런데 솔직히 팀원이 imeimi인데ㅋㅋㅋㅋ 월파 욕심이 안 나기 어렵다. 폼이 많이 떨어진 상태에서 예선을 봤는데 생각보다 가능성이 보여서(??) jhhope1이 실력을 좀 키우자는 이야기를 했다. 결국 내가 아는 문제들을 즈홒한테 던져주고, 즈홒은 풀이를 짜고, ..