BOJ 26974 - Range Reconstruction

BOJ 26974 - Range Reconstruction

$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$를 이용해 직접 검사하는 것이다.

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