ABC429 C – Odd One Subsequence

C - Odd One Subsequence

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

整数列Aの中から2つは等しく、残りの1つは異なる組を満たす個数を答える問題

どの数がいくつあるかを持っておけば良いなと思ったところまでは良かったですが、そのあとが思いつきませんでした。

まず、辞書型の配列で以下のように出現頻度をもつことにしました（入力例1を考えます）

{ 2: 3, 3: 1, 5: 1 } # 2が3つ、3が1つ、5が1つCode language: PHP (php)

次に数字を一つ選び、できる組の個数を考えていきます。

2と何かの組み合わせ（3と5）で条件に合う組を作ります

また、2は3つありますが、3つのうち2つを選ぶ組み合わせは3つです・・・X

この組み合わせの数Xと残りの1つを選ぶ個数をかけます

3は1つなので3*1=3個の組が作れます、5も同じく1つなので3*1=3個の組が作れます。

これらを足すと答え6が求められます。

3と5を1つづつみていくと時間がかかるので、まとめます。

2の個数から2個選ぶ組み合わせX * (3の個数 + 5の個数) = 6
3 * (1 + 1） = 6

3の個数+5の個数の部分を求めるには

全体Nから今考えている2の個数を引くとわかります。

5-3=2（全体N – 2の個数）

これを全ての出現する数で計算して足し合わせます。

以下でACできました。

from math import comb


def i_map(): return map(int, input().split())
def i_list(): return list(map(int, input().split()))

n = int(input())
a = i_list()

d = dict()

for i in range(n):
  idx = a[i]
  if idx in d:
    d[idx] += 1
  else:
    d[idx] = 1

ans = 0
for key in d:
  t = n - d[key]
  ans += comb(d[key], 2)*t

print(ans)Code language: Python (python)

補足

組み合わせの数を求める方法はPythonではmath.comb()が使える