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

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

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

https://www.acmicpc.net/problem/10129 10129번: 작은 새 문제 경기과학고의 뒤뜰에는 일렬로 된 n개의 나무로 이루어진 숲이 있다. 그 중 첫 번째 나무 위에는 마지막 나무의 위로 올라가고 싶어하는 작은 새가 한 마리 있다. 그 새는 몸집이 매우 작기 때문에 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 만약 새가 i번째 나무 위에 있다면, 이 새는 한 번의 비행으로 i+1, i+2, …, i+k번째 나무 중 하나로 갈 수 있으며 그보다 멀리 떨어진 나무로는 가지 못한다. 또한, 작은 새에게 지금 있는 www.acmicpc.net 더보기 가장 먼저 드는 생각은 dp[i]dp[i]dp[i]를 "iii번 나무에 도달하기 위해 느끼는 피로감의 횟수"로 정의하는 것이다. 점화식..

이 문제에서는 SEERC '19 Game on a Tree와 CERC '11 Racing Car Trail의 풀이를 다룬다. 풀이의 첫 단어부터 강력한 스포일러가 될 수 있으니 충분한 고민을 해보고 오는 것을 권한다. 풀이 설명 또한 두 문제의 context에 의존하는 경향이 강하니 지문을 숙지하고 오자. https://www.acmicpc.net/problem/17962 17962번: Game on a Tree In a single line, print “Alice” (without quotes), if Alice wins. Otherwise, print “Bob”. www.acmicpc.net https://www.acmicpc.net/problem/3419 3419번: Racing Car Trail..

https://www.acmicpc.net/problem/13318 13318번: 위험한 해싱 string matching 알고리즘에는 여러 가지가 있다. KMP 알고리즘이나 Boyer­Moore 알고리즘이 그 예시이다. 하지만 지구이는 KMP를 이해할 수 없었고, Boyer­Moore는 시간복잡도가 너무 컸다. 결국 지구이는 틀릴 확률이 있지만, 간단한 방법인 해싱을 즐겨 사용하게 되었다. 해싱은 문자열을 숫자 하나로 바꾸는 해시 함수를 하나 정의한 후, 이 값이 같은지 다른지를 통해 문자열이 같은지 판별하는 방법이다. 지구이는 해시 함수를 다음 www.acmicpc.net 풀이 두 해시값을 뺀 다항식을 생각하면, 그 다항식은 아래와 같은 조건을 만족해야 한다. deg⁡f<300000\deg f < 300000degf<300000 \(..