Official
H - サンドイッチな組/Sandwich triplet Editorial
by
H - サンドイッチな組/Sandwich triplet Editorial
by
sounansya
以下の条件を全て満たす \((i,j,k)\) の個数を \(X\) とします。
- \(1\le i < j < k \le N\)
- \(A_i= A_k\)
また、以下の条件を全て満たす \((i,j,k)\) の個数を \(Y\) とします。
- \(1\le i < j < k \le N\)
- \(A_i =A_j= A_k\)
すると、求める答えは \(X-Y\) として表すことができます。したがって、 \(X,Y\) の値がそれぞれ求まれば良いです。
\(c\) に対し \(A_i=c\) を満たす \(i\) を昇順に並べた整数列を \(B^c=(B^c_1,B^c_2,\ldots,B^c_{L_c})\) とします。
[1] \(X\) を求める方法
\(i,k\) を固定することで、 \(\displaystyle X=\sum_c \sum_{1\le i < k \le L_c} (B^c_k - B^c_i - 1)\) となります。
\(\displaystyle \sum_{1\le i < k \le L_c} (B^c_k - B^c_i - 1)=\sum_{i=1}^{L_c} (2i-L-1)B_i^c-\frac{L(L-1)}2\) となるので、各 \(B^c\) に対してこの式を計算することで全体として計算量 \(O(N)\) で求めることができます。
[2] \(Y\) を求める方法
\(Y\) は同じ要素の \(3\) つ組の個数なので、 \(\displaystyle Y=\sum_c \binom{L_c}3\) となります。
以上を適切に実装することでこの問題に正答することができます。計算量は \(B^c\) を求める部分がボトルネックとなり \(O(N \log N)\) です。
実装例(Python3)
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
s = defaultdict(lambda: [])
for i in range(n):
s[a[i]].append(i)
x, y = 0, 0
for b in s.values():
l = len(b)
for i in range(l):
x += (2 * i - l + 1) * b[i]
x -= l * (l - 1) // 2
y += l * (l - 1) * (l - 2) // 6
print(x - y)
