\(O(N^3)\) 解法

単純な 3 重ループでも 2 秒に間に合うことで、話題になっていました。

• (C++) https://atcoder.jp/contests/abc143/submissions/19848987
• (Python) https://atcoder.jp/contests/abc143/submissions/13185963

\(N^3\) は約 \(10^{10}\) と大きいですが、

• 加算、比較しか必要としない（除算どころか乗算もない）
• ループ回数は \(\binom{N}{3}\) で、 これは約 \(N^3/6\) である（\(O(N^3)\) とはいえ「定数倍」に \(1/6\) がつく）

ことなどがあって、「\(N=2000\) の \(O(N^3)\) 解法」の中では処理が軽い部類であるためです。

\(O(N + L_{\text{max}}\log L_{\text{max}})\) 解法

高速畳み込み計算を利用した、時間計算量 \(O(N + L_{\text{max}}\log L_{\text{max}})\) のアルゴリズムも存在します。FFT というアルゴリズムを利用しており、ABC-D を超えるレベルです。

• \(A_i + A_j \leq A_k\) となる添字集合 \(\{i,j,k\}\) の個数を数えて、全体から引くことにします。
• まず順序対 \((i,j,k)\) を数えます。これには、各 \(L\) に対して \(A_i+A_j=L\) を満たす \((i,j)\) の計算ができればよくて、\(A_i\) の度数分布を畳み込むことで計算できます。
• 順序対 \((i,j,k)\) の個数から、\(i = j\) であるようなものを引いて \(2\) で割ることで、集合 \(\{i,j,k\}\) の数え上げが行えます。