구사과

BOJ 33365. Password최댓값은 $n$ 입니다. 최솟값은, 비밀번호의 중앙에 비알파벳 문자를 배정한 후, 중앙에서 왼쪽 / 오른쪽으로 세 문자마다 비알파벳 문자를 배정하면 됩니다.BOJ 33324. The Romanian Sieve$\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor$ 을 $O(\sqrt n)$ 시간에 계산할 수 있으면 전체 문제를 이분 탐색으로 $O(\sqrt n \log n)$ 시간에 해결할 수 있습니다. 그 방법을 소개합니다.$\sum_{i = 1}^{n}\lfloor \frac{n}{i} \rfloor$ 를 계산할 때는, 항상 $\lfloor \frac{n}{i} \rfloor \leq \sqrt n$ 혹은 $i \leq \sqrt n$ 중 하..

어떤 decision problem에 대해서, kernel은 그 decision problem의 답을 보존하는 작은 인스턴스다. 그러니까 f : Instance -> Instance인데$|f(x)| \leq g(k)$$Decision(x) = Decision(f(x))$같은 함수가 있으면, decision problem은 $g(k)$ 크기의 kernel이 있다고 함자명한 theorem은, 모든 FPT 문제는 다항시간에 찾을 수 있는 kernel이 존재한다는 것이다.구체적으로 decision problem을 $g(k) n^c$ 에 풀 수 있으면 poly time에 kernel을 찾을 수 있음. 방법은:$n \geq g(k)$ 면, 그냥 $n^{c+1}$에 풀고 trivial yes / no instance..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

ARC 123 A. Arithmetic Sequence$A_1 + A_3 = 2 \times A_2$ 가 되도록 각 수를 최소한으로 증가시키는 문제입니다. 위 부등식의 두 방향에 따라서 케이스를 나눠 처리하면 됩니다.$A_1 + A_3 \le 2 A_2$ 면 $2A_2 - A_3 - A_1$ 만큼 $A_1$ (혹은 $A_3$) 을 증가시키면 됩니다.$A_1 + A_3 > 2A_2$ 면 일단 $A_1 + A_3$ 이 짝수여야 합니다. 홀수일 경우 둘 중 아무거나 $1$ 만큼 증가시킵시다. 그리고 $A_2$ 를 $(A_1 + A_3) / 2$ 로 증가시키면 됩니다.ARC 123 B. Increasing Triples문제가 연산 을 도입하여 조금 난해하게 쓰여있습니다. 수열 $A$, $B$, $C$ 에서 $A..

2019년 APIO 2019 B번 문제 Bridges의 Almost linear time 풀이가 존재하는지에 대해서 질문을 남긴 적이 있다. 당시의 나는 그러한 풀이가 존재할 것이라고 믿었다. Dynamic MST를 Poly-log time에 해결할 수 있기 때문이다. 하지만 이제는 다시 한 번 생각해 봐야 할 것 같다. 문제를 요약하면 다음과 같다. (원래 문제에서는 트리가 아니라 그래프가 주어지지만, 여기서는 트리라고 가정하고 Hardness를 증명한다. 즉, 문제 상황보다 더 강한 증명이다.)크기 $n$ 의 가중치 있는 트리가 주어졌을 때, 다음 두 연산을 처리하여라:$Update(e, w)$: 간선 $e$ 의 가중치를 $w$ 로 갱신한다.$Query(v, x)$: 정점 $v$ 에서 가중치 $x$ ..

잠자고 있던 퀄리티 낮은 scribe 몇개를 기록용으로 올린다.Hamiltonian Path in $O(2^nn^c)$ time, $O(n^c)$ spaceKarp의 1982년 논문이라고 들었다.존재 여부 대신 경우의 수 mod p를 세자. random p를 잡아서 decision problem으로 바꿀 수 있다.길이 n의 (simple) path를 세는 대신 길이 n의 walk를 세는 건 쉬움. 그냥 sumA^{n-1}(i, j). 그런데 길이 n의 walk가 모든 정점을 방문하면 그게 hamilton path이다. 그래서 모든 정점 부분 집합에 대해서 포배하면 끝.TSP in $O(4^n n^c)$ time, $O(n^c)$ space모든 $i, j$ 에 대해 $i$ 에서 출발해서 모든 정점을 다 돌..

이 글 을 보고 작성하였다.BOJ 1763 트리 색칠 이나 AGC 023 F. 01 on Tree 문제는 다음과 같은 최적화 문제로 표현할 수 있다:트리의 모든 topological order $p$ 중에서, \sum_{p(i) 예를 들어 트리 색칠은 $a_i = 1, b_j = C[j]$ 고 01 on Tree는 $a_i = V_i, b_j = 1 - V_j$ 라고 할 수 있다.이 문제를 푸는 알고리즘은 다음과 같다. 만약에 어떤 루트가 아닌 노드의 $b_v / a_v$ 가 트리 전체에서 최대면, 최적해에서 $p$ 와 $v$ 가 인접하게 등장함을 증명할 수 있다. 구체적인 증명은, $[p \ldots w v]$ 의 꼴일 때 $v, w$ 를 바꿔서 손해를 볼 수가 없음. 그래서 저런 최대를 찾은 후 $(..

(9/15 06:58 - Hieroglyphs 만점 풀이를 추가했다.)(9/13 09:44 - 초판 작성)이집트 알렉산드리아에서 IOI 2024 Day 2 대회가 진행되었다. 한국 학생들의 최종 성적은 다음과 같다.김은성, 100 / 58.64 / 59 / 3 / 78 / 64.0, 362.64점, 29등 (금메달)우민규, 100 / 31.40 / 59 / 3 / 100 / 64.0, 357.40점, 33등 (은메달)정희우, 100 / 53.89 / 59 / 3 / 100 / 31.0, 346.89점, 41등 (은메달)정민찬, 100 / 79.64 / 17 / 3 / 78 / 64.0, 341.64점, 48등 (은메달)올해는 학생들의 Day 2 성적이 Day 1 성적보다 약간 낮았고, 결국 금메달 / 은..

이집트 알렉산드리아에서 IOI 2024 Day 1 대회가 진행되었다. Day 1 기준 한국 학생들의 성적은 다음과 같다.김은성, 100 / 58.64 / 59, 217.64점, 22등정희우, 100 / 53.89 / 59, 212.89점, 26등정민찬, 100 / 79.64 / 17, 196.64점, 43등우민규, 100 / 31.40 / 59, 190.40점, 52등올해도 작년과 같이 모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않다. 또한 그 경계선의 점수 차가 크지 않은 편이다. Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 좋은 결과를 내기를 소망한다.Day 1의 만점자는 중국의 Kangyang Zhou로 대회 시..