BOJ 26974 - Range Reconstruction

May 16, 2023

$a_0=0,a_1=r_{0,1}$ 로 결정하고 $a_2 \sim a_{n-1}$ 을 결정해보자.

정답은 항상 존재하므로 $a_i$ 는 항상 두 가지만 가능하다.

$a_{i-1}+r_{i-1,1}$ 이거나 $a_{i-1}-r_{i-1,1}$ 이다.

한 가지를 검사해보고 그것이 가능하다면 그것으로 결정하고 아니면 나머지로 결정한다.

결정하는 방법은 $O(n^2)$ 으로 naive하게 할 수 있다.

$a_i$ 가 수열에 추가됨으로써 달라지는 모든 변화들을 현재까지 만들어진 $a$ 를 이용해 직접 검사하는 것이다.

정해에선 이것이 항상 타당함을 귀납적으로 증명할 수 있다고 한다.

You may also enjoy