公式

D - Distinct Trio 解説 by kyopro_friends


与えられた条件は「\(A_i < A_j < A_k\) を満たす \((i,j,k)\) の組の個数を求めよ」と読み替えることができます。

元の条件を満たす $(i,j,k)$ に対して $i,j,k$ の並び替えであって、$A_i \lt A_j \lt A_k$ を満たすものがただ1つ存在します。逆に、$A_i\lt A_j\lt A_k$ を満たす $(i,j,k)$ に対して $i,j,k$ の並び替えであって、$i\lt j\lt k$を満たすものがただ1つ存在します。

\(j\) を全探索します。このとき、\(i,k\) は独立に選ぶことができます。\(i\) の選択肢の個数は \(A\) に含まれる \(A_j\) より小さな要素の個数、\(k\) の選択肢の個数は \(A\) に含まれる \(A_j\) より大きな要素の個数となります。したがって、「\(A\)\(x\) 未満の要素が何個あるか?」を表す配列を予め用意しておくことで、この問題を \(O(N+\max A)\) で解くことができます。

実装例(Python)

投稿日時:
最終更新: