この問題を３つのアプローチで解き、また、類似する問題の考察を考えます。
- 解法1: 組み合わせだけで考える(包除原理)
- 解法2: 小さい方から見て作れる組み合わせ数を数える(累積和)
- 解法3: DP
定義: 以下、$cnt_x$を配列$a$内に$x$の個数とします。
解法1: 組み合わせだけで考える(包除原理)
まず、異なるi, j, kを選ぶ組み合わせ全体を考えます。この組み合わせは、
- パターン１：同じ値が含まれないもの
- パターン２：同じ値が2個ちょうどであるもの
- パターン３：同じ値が3個であるもの
全てが包含されたものとなります。(同じ値が1つであるもの、というのは存在しません)
今回は選択する数が3つであるため、これらは排他的です。（同時に複数のパターンを含むものはありません）
$ b > a$の時、$aCb = 0$です。
- パターン２：各$x$に対して、$cnt_{x} C2 \times (n - cnt_{x}) $です。ある数$x$に注目した時、$x$から2つ選ぶ組み合わせは$cnt_{x}C2 $で、その中で$x$以外の数を選ぶのは、$n - cnt_{x}$です。
- パターン３：各$x$に対して、$cnt_{x}$個の中から3つを選びたいので、$cnt_{x}C3$です
求めたい数(パターン1) = 全ての組み合わせ - パターン2 - パターン3を答えればよいです。
実装(Python)
from collections import defaultdict
nC3 = lambda n: (n * (n-1) * (n-2)) // (3*2*1)
nC2 = lambda n: (n * (n-1)) // (2*1)
n = int(input())
dat = list(map(int, input().split()))
cnt = defaultdict(int)
for x in dat: cnt[x] += 1
ans = nC3(n)
for key in cnt: ans -= nC2(cnt[key]) * (n - cnt[key])
for key in cnt: ans -= nC3(cnt[key])
print(ans)
解法2: 小さい方から見て作れる組み合わせ数を数える(累積和)
求めたい数の定義を考えると、相違なる$i$, $j$, $k$ を選んだ際の値$a[i]$, $a[i]$, $a[k]$の集合に含まれる異なる３つの値$x$,$y$,$z$は$x<y<z$となる値であることは自明です。(つまり、$a[i] = x$とは限らないです)
ここで、真ん中の数$y$を固定したとします。 このとき、$x$は$y$よりも小さい数全て、$z$は$y$よりも大きい数全てが候補になるので、その積の組み合わせを作ることができます。すなわち、ある$y$を定めた時には、配列aに含まれるyよりも小さい数の個数 * 配列aに含まれるyよりも大きい数の個数 というような$x$,$y$,$z$の組が、$配列aに含まれるyの個数$存在することになります。
実装を考えます。配列$a$がソートされているとし、値$x$の個数を$cnt[x]$としておきます。ある地点から右にある要素の数を$cntR$, 左にある要素の数を$cntL$とします。最初、$cntR = n$とします。次のように処理します。
- xの小さい方から次の処理をします
- 今、$x$をyとしてその左右の候補数を考えたいので、$cntR$から$cnt[x]$を引きます。
- 答えに、$cntL \times cntR \times cnt[x]$を足します。
- この処理が終わった後は、$x$は次の数字の左側になるので、$cntL$に$cnt[x]$を足します
- これを繰り返します
$cntR$, $cntL$は実質、(それぞれ右、左からの)累積和です。
実装(Python)
from collections import defaultdict
n = int(input())
dat = list(map(int, input().split()))
cnt = defaultdict(int)
for x in dat: cnt[x] += 1
cntL = 0 # いまのところより左にある数の総数
cntR = n # いまのところより右にある数の総数
sortedNum = list(sorted(cnt.keys())) # 配列aの(distinctな)昇順の要素
ans = 0
for x in sortedNum:
cntR -= cnt[x]
ans += cntL * cntR * cnt[x]
cntL += cnt[x]
print(ans)
解法3: DP
この時、$dp[i][j]$を昇順の$i$個めの要素まで$j$個を選んだとします。この時、dpの最後の要素の$[3]$が答えです。
配列$a$の小さい方から$i$個めの要素$x$についてdp[i][j] = dp[i-1][j] + dp[i-1][j-1] * cnt[x](ただし、j > 0で、j=0なら$dp[i][0] = 1$)です。(常に、0個しか選んでいない状態は1つです)
加算のそれぞれの項について考えます。
-
dp[i-1][j]: $i$個めの要素を選ばなかった場合、dp[i-1][j]について、直前の数まで$j$個を選んだ状態は引き継ぎます。 -
dp[i-1][j-1] * cnt[x]: $i$個めの要素を選んだ場合はdp[i-1][j-1]の状態に$x$を追加して、$j$個選んだ状態とします。このような$x$の選び方は$cnt[x]$個あります。
実装(Python)
from collections import defaultdict
n = int(input())
dat = list(map(int, input().split()))
cnt = defaultdict(int)
for x in dat: cnt[x] += 1
sortedNum = list(sorted(cnt.keys())) # 配列aの(distinctな)昇順の要素
sortedNumCount = len(sortedNum)
# dp[i][j]: 昇順のi個めの要素までj個を選んだとする
dp = [[0] * 4 for _ in range(sortedNumCount + 1)]
dp[0][0] = 1
for ind in range(1, sortedNumCount + 1):
x = sortedNum[ind-1]
dp[ind][0] = 1
dp[ind][1] = dp[ind - 1][1] + dp[ind - 1][0] * cnt[x]
dp[ind][2] = dp[ind - 1][2] + dp[ind - 1][1] * cnt[x]
dp[ind][3] = dp[ind - 1][3] + dp[ind - 1][2] * cnt[x]
print(dp[sortedNumCount ][3])