Editorial

---

D

summary:

모든 $a_i$가 노드이고, $a_l \to a_r$로 가는 엣지의 비용은 $min(a_l,a_{l+1},\dots,a_r)$이라고 할 때,

$\underset{1 \leq u \lt v \leq n}{max} d(u,v) (d(u,v)= u에서 v로 가는 최단경로)$ 의 최댓값을 구하는 문제이다.

solution:

i번째 수에서 i+1번째 수로 가려면 바로 가는 거 $min(a_i,a_{i+1})$,

다른 데를 거쳐서 가는 것 $2*\underset{1 \leq i \leq n}{min}a_i$

이 두 가지가 있다.

즉, $d(i,i+1)= min(min(a_i,a_{i+1}),2*\underset{1 \leq i \leq n}{min}a_i)$이고,

2칸이 넘게 떨어진 $l$과 $r$ 노드에 대해서는 $a_l,a_r$ 외에 중간에 끼는 수가 늘어난다.

범위 안에는 1배이고, 외부는 2배를 곱한 값을 엣지의 비용으로 가지게 되므로 범위 안에 수가 늘어나면 $d(l,r)$이 더 커질 수는 없다.

따라서 $\underset{1\leq i \lt n}{max} d(i,i+1)$이 답이 된다.

1에서 $10^9$를 구간으로 설정하고 이분 탐색을 하면 된다.

이분 탐색을 하는 방법은 외부의 수는 2배를 하게 되고 내부의 수는 1배이므로 일단 $a_i*2$가 ans보다 작은 수는 존재해서는 안 되므로 ans/2보다 작은 수들은 전부 $10^9$로 바꾸고(못바꾸면 false), 배열의 최솟값을 구한 뒤 배열을 돌면서 $d(i,i+1)$이 $ans$를 넘을 수 있는지 확인해주면 된다.

opinion:

저 수식 자체는 생각을 했고 풀기도 제대로 푼 것 같은데, 구현 과정에서 무언가 문제가 있었던 것 같다.