구사과

보호되어 있는 글입니다.

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$ ..