구사과

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로 대회 시..

IOI 2018 Day 2 풀이를 작성할 당시 Meetings 문제를 해결하지 못해서, "36점 초과의 풀이는 작성 중입니다" 라고 하고 풀이를 비워두었다. IOI 2024 참관을 위해 알렉산드리아로 가는 비행기에서 드디어 100점 풀이 작성을 완성했다. 원래 글을 끌어올리기에는 시간순 정렬을 너무 깨는 것 같아서 개별 글에 작성한다.Problem길이 $N$의 양의 정수 배열 $A_0, A_1, \cdots A_{N-1}$ 이 있다. $0 \leq L \leq v \leq R $Cost(L, R, v) = \sum_{i = L}^{v-1}{(Max_{j=i}^{v}(A_j))} + \sum_{i = v}^{R}{(Max_{j=v}^{i}(A_j))}$$Q$ 개의 질의가 주어진다. 질의로 $L, R$이 주..

2, 4, 5번 문제의 아이디어를 구상했다.시간 여행각 $i$ 에 대해 $j \le i, A_i - K \le A_j \le A_i$ 를 만족하는 최소 $j$ 를 찾아 그 합을 출력하는 문제이다. $j \le i$ 조건은 함정이다. 어차피 $i$ 가 조건을 만족하기 때문에 무조건 저 조건은 성립한다. 그러면 $A_j$ 값이 특정 구간에 있는 최소 $j$ 를 찾는 문제가 되고, 이는 sliding window minimum 문제이다. $O(N + maxA)$ 나 $O(N \log N)$ 에 해결할 수 있다.공장단순하게는 끝점 작은 순으로 구간을 처리하면서 기존에 넣은 구간과 겹치지 않는 구간을 추가해 주면 된다. 쿼리가 들어올 때, 쿼리로 추가된 구간을 끝점 작은 순으로 정렬하자. Merge sort를 하..

출처는 http://www.cs.tau.ac.il/~zwick/grad-algo-09/short-path.pdf흔히 알려진 알고리즘은 벨만 포드를 사용한 $O(nm)$ 시간 알고리즘이다. 이 글에서는 $O((n + m)\sqrt n \log W)$ 알고리즘을 소개한다.그래프에 음수 사이클이 없다면 퍼텐셜 함수가 존재해서 $p(u) - p(v) + w(u, v) \geq 0$ 이 되게 만들어 줄 수 있음이 잘 알려져 있다. 그래서 결정 문제를음수 사이클을 찾거나퍼텐셜 함수를 찾거나로 정의할 수 있다. 퍼텐셜 함수를 찾을 수 있으면 거기서부터는 $O(m + n \log n)$ 에 최단 경로를 찾는 것이 쉽기 때문이다.만약 모든 간선의 가중치가 -1 이상 (즉 음수 간선은 무조건 가중치 -1) 일 때 문제를 ..

ABC 127 B. Algae주어진 점화식을 계산하면 됩니다. (답은 int32 범위도 넘어가지 않습니다.)PA 2024. Zelki$D[i]$ 를 (조건을 만족하는) 선물 상자 하나를 골랐고, 그 안의 사탕의 무게 합을 $m$ 으로 나눈 나머지가 $i$ 일 때, 가능한 가격 합 최소라고 정의합시다. 원래 문제와의 차이는, 원래 문제에서는 선물 상자를 여럿 고를 수 있다는 점입니다.$D[i]$ 는 동적 계획법을 사용하여 구할 수 있습니다. $DP[x][i]$ 를, 사탕의 색상이 $x$ 이하인 사탕들만 고려하여 무게 합 나머지가 $i$ 가 되게 하는 방법이라고 합시다. $DP[x-1][_]$ 테이블이 채워져 있으면, 색상이 $x$ 인 사탕의 모든 경우를 다 시도하면서 $DP[x][_]$ 테이블을 채울 수 ..

Splay tree 등의 BBST 구현을 여러번 시도해 보았지만 내가 대회에서 직접 짜면 버그가 너무 많아서 보통 피해왔었다. 얼마 전 QOJ를 읽다가 Weight-Balanced Tree라는 Persistent BBST의 굉장히 간단한 구현체를 찾아 이 블로그에 소개한다. 이 구현의 장점은:Rotate 연산을 사용하지 않는다.Rotate 연산은 유도하기 대단히 귀찮아서 보통 암기해야 하고 실수하기 쉽다.사실 이 구현도 Merge에서 암기해야 할 부분이 있는데 Rotate보단 쉬운 거 같다. 그리고 그 부분은 실수를 조금 해도 괜찮다.리프 노드만이 실제 원소에 대응된다. 리프 노드가 아니면 대응되는 원소는 없으며, 왼쪽 자식 / 오른쪽 자식을 모두 가진다. 일반적으로 우리가 사용하는 세그먼트 트리등과 동..