rkm0959, jhhope1이랑 진행한 문제풀이의 간략한 풀이. 스포일러에 주의하자. BOJ 15313. 정과프 해적단 $[l, r]$ 값이 없는 문제는 좌표압축 + 세그먼트 트리를 이용한 dp로 $O(n\log n)$에 해결할 수 있다. 이 때 $l$이 증가할수록 조건을 만족하기 위해 필요한 최소의 $r$도 증가하므로 inchworm을 얹어주면 $O(n^{2}\log n)$이 된다. BOJ 15504. 프로그래밍 대결 제일 실력이 높은 선수를 제외하고, 각 선수마다 ‘자신을 이기는 선수’를 정해주면 스패닝 트리가 유일하게 결정된다. 해당 작업을 mcmf로 모델링하면 $O(n^{4})$. 늘 그렇듯 플로우 문제에서 시간복잡도는 아무 의미 없다....
교육용으로 사용한 10문제의 풀이입니다. 용어가 원본 문제와 다를 수 있습니다. BAPC 2021 F. “Fair Play” $n$이 홀수인 경우는 당연히 불가능하고, 짝수인 경우 $(b, p)$를 std::pair 와 같은 방식으로 정렬한 것을 $(b_{1}, p_{1}), \cdots, (b_{n}, p_{n})$이라고 둡시다. 이 때 유일하게 가능한 매칭 방법은 $(b_{1}, p_{1})$을 $(b_{n}, p_{n})$과, $(b_{2}, p_{2})$를 $(b_{n-1}, p_{n-1})$과 … 매칭해주는 것입니다. 이렇게 해서 벡터합이 모두 균일하다면 possible, 그렇지 않다면 impossible 입니다. BAPC 2021 I “Implementation Irregularities” $s_{i}$가 증가하는 순서대로 원소들을 배열하고, $s_{i} = -1$인 원소들을 제외합시다....
Riemann Mapping은 $\mathbb{C}$의 모든 simply connected proper subset $\Omega$에 대해, Conformal map $f : \mathbb{D} \to \Omega$가 존재한다는 매우 강력한 정리이다. 여기서는 짧고 아름다운 nonconstructive한 증명을 다룬다. Ref: Stein & Shakarchi, Complex Analysis Ch.8 Montel’s theorem 어떤 함수열 $\ev{f_n}$이 수렴하는 부분수열 $\ev{f_{n(k)}}$를 갖는다는 사실은 매우 유용하다. 물론 여기서 수렴은 모든 cpt subset에 대한 uniform convergence를 의미한다. Arzela-Ascoli Theorem의 경우, 정의역이 cpt set인 연속함수들의 함수족 $\mc{F}$가 uniformly bdd, equicontinuous면 위 성질을 만족한다는 것을 보장하고 있다....
$\mathbb{C}$의 open unit disk $\mathbb{D}$에 대해, holomorphic function $f : \mathbb{D} \to \mathbb{D}$를 생각하자. Schwarz Lemma는 이러한 $f$의 성질에 대한 Lemma이고, 이는 $\mathbb{D}$의 Automorphism group을 characterize하는 데 큰 도움을 준다. Lemma (Schwarz) $f : \mb{D} \to \mb{D}$가 holomorphic이고, $f(0) = 0$을 만족한다고 하자. 다음 세 성질이 성립한다. $\abs{f(z)} \le \abs{z}$. 만약 $z_0 \neq 0$에 대해 $\abs{f(z_0)} = \abs{z_0}$가 성립한다면, $f$는 rotation. $\abs{f’(0)} \le 1$. 등호가 성립한다면 $f$는 rotation. 증명은 기초 복소해석을 공부했다면 크게 어렵지는 않다....
SEEMOUS 2019를 풀어보았다. 몇몇 문제는 풀이를 검증하기 위한 배경 지식이 부족해서 나중에 자세히 다루기로 한다. P1 $[0,1]$의 값을 갖는 무한 실수열 $\set{x_{n}}$이 다음 조건을 만족하면 $\set{x_{n}}$을 Devin sequence라고 한다. $ \lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^{n}f(x_{i}) = \int_{0}^{1} f(x)dx $ 이 때, $\set{x_{n}}$이 Devin sequence가 될 필요충분조건은 $ \forall k \ge 0 \quad \lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^{n}x_{i}^{k} = \frac{1}{k+1} $ 인 것임을 보여라. Solution sketch $\implies$는 자명. $\impliedby$는 Weierstrass. P2 $A_{1}, A_{2}, \cdots, A_{m} \in \mathfrak{M}_{n,n}(\mathbb{R})$에 대하여 다음을 만족하는 $\set{\varepsilon_{i}} \in \set{-1,1}^{m}$이 존재함을 보여라....