[AtCoder] ABC 140 C – Maximal Value

問題

方針

条件を具体的に書き出すと、

\[\begin{eqnarray}
\max(A_1, A_2) &\leq& B_1\\
\max(A_2, A_3) &\leq& B_2\\
&\vdots&\\
\max(A_{N-2}, A_{N-1}) &\leq& B_{N-2}\\
\max(A_{N-1}, A_N) &\leq& B_{N-1}\\
\end{eqnarray}
\]

となり、\( A_1 \) と \( A_N \) は不等式の制約が一つであることが分かります。よって、\( A_1 = B_1 \), \( A_N = B_{N-1}\) のとき総和を最大化します。その他のものについて考えると、\( A_2 \) については、

\[
A_2 \leq B_1 \wedge \max(A_2, A_3) \leq B_2
\]

なので、\( A_2 = \min(B_1, B_2) \) となります。同様に考えて、\( A_i = \min(B_{i-1}, B_{i}) \ (2 \leq i \leq N – 1)\) となります。

コード