구사과

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$ 에서 출발해서 모든 정점을 다 돌..