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..

오늘 다룰 Max Cut 문제는 non-negative weighted undirected graph $G = (V, E, w)$에 대해서 $S \subseteq V$를 골라서 $vE(S, V - S)$의 weight 합을 최대화하는 문제이다. 다항 시간 알고리즘이 알려진 min cut에 비해 이 문제는 NP-hard임이 알려져 있다.NP-hard problem의 경우 여러 근사 알고리즘들이 존재하는데, 가장 naive한 알고리즘부터 생각해보자. 임의의 $S \subseteq V$에 대해 $E(S, V-S)$의 weight 합, 즉 $\sum_{e \in E(S, V-S)} w(e)$를 $w(\partial S)$라고 표기하자. $w(\partial S)$의 가능한 최댓값, 즉 MAX CUT을 $\mat..

Bostan-Mori algorithm흔히 "선형 점화식의 $N$번째 항"을 구하는 알고리즘으로 알려진 방법이다. 사실은 보다 일반적으로, $P(x)/Q(x)$ 꼴의 rational power series의 $N$차항 계수를 구하는 데 사용할 수 있다.Theorem. $\deg P 어떤 다항식 / power-series의 $N$차항 계수를 $[x^N]f(x)$로 쓴다.$\mathcal{M}(d)$는 $\mathbb{F}[x]$의 두 $d$차 다항식을 곱하는 데 걸리는 시간이다. Computer algebra에서는 sublogarithmic factor를 따지지만, PS 범위에서는 $\mathcal{M}(d) = O(d\log d)$로 생각해도 무방하다.$\mathbb{F}$는 덧셈, 뺄셈, 곱셈, 나눗셈..

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에 대한 관심이 떨어진 상태라, 좋은 대회를 만들자기보다는 그냥 내..