구사과

잠자고 있던 퀄리티 낮은 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 성적보다 약간 낮았고, 결국 금메달 / 은..