[17318] Highway Cycling

조건은 다음과 같이 됩니다. $w_i$를 $i$번째 도로에서 달리는 속도라고 하면,

$$\begin{gather*} E_i := k_i(w_i - v_i)^2s_i \\ E_u = \sum E_i \\ T = \sum \frac{s_i}{w_i} \end{gather*}$$

여기서 $E := \sum E_i$를 $\mathbf{w}$ 벡터의 공간에서 $\mathbb{R}$ 공간으로 보내는 다변수함수로 볼 수 있습니다. 마찬가지로 $T$도 그렇게 둘 수 있겠네요. $E - E_u = 0$이므로 라그랑주 승수법을 먹여 전체 조건을 다음과 같이 변형할 수 있습니다.

$$\begin{gather*}E = E_u\\\nabla (E - E_u) = \lambda \nabla T\end{gather*}$$

풀어 정리하면 다음처럼 됩니다.

$$\begin{gather*}E = E_u\\ \lambda = -2k_iw_i^2(w_i - v_i)\text{ for every }i\end{gather*}$$

 

 $\lambda$를 나타내는 식에서 $w_i$를 제외한 나머지는 모두 주어지는 값이기 때문에, 만약 어떤 $\lambda$값을 잡는다면 그에 따른 $\mathbf{w}$ 벡터를 (삼차방정식을 풀어) 찾을 수 있습니다. $\lambda$값은 큰 범위에서 $E = E_u$ 조건을 사용해 이분 탐색을 때리면 됩니다. 적절한 $\mathbf{w}$를 찾았다면 $T$를 계산할 수 있고, 그러면 그게 답이 됩니다.

 

17318번: Highway Cycling