\(O(N^{2})\) で解くことができます。

\(P_{1} > P_{i}\) でなければならない \(i\) は、以下の条件を満たすものです。

• \(L_{1} < L_{i} < R_{i} < R_{1}\)

\(2, 3, \dots , N\) のうち、上記の条件を満たす整数 \(i\) の集合を \(A\) とし、そうでない整数の集合を \(B\) としたとき、以下を満たすように \(P\) を決めるのが最適です。

• \(\forall a \in A : P_{1} > P_{a}\)
• \(\forall b \in B : P_{1} < P_{b}\)
  

なぜなら、\(P_{1}\) を最小化したいためです。 また、\(L_{a} < L_{b} < R_{b} < R_{a}\) を満たす \(a\in A, b\in B\) は存在しないからです。

よって、\(A, B\) それぞれについて、この問題を再帰的に解けば最適解がもとまります。

実装例 C++ 2 ms