ABC 111 C - /\/\/\/
問題概要
C - /\/\/\/
数列Aに対して、偶数列を任意の値a, 奇数列を任意の値bの2種類のみに置き換える時
最小で何か所置き換えれば条件を満たせるか答えよ。
※ただし、値a, 値bは異なる値とする
解法
偶数列、奇数列から、それぞれ1番目に多い値(a1,b1)と2番目に多い値(a2,b2)を求め
a1とb1が異なるときは、nからa1とb1を引く。
a1とb1が同一である場合、a1とb1で多い方を採用し、
採用されなかった方はa2、またはb2を用いる。
a1とb1が同一かつ、同じ数である場合、
a2とb2を比較し、多い方を採用しnから引けばよい。
提出コード
n = int(input()) a = list(map(int, input().split())) even = defaultdict(int) odd = defaultdict(int) for i in range(n): if i % 2 == 0: even[a[i]] += 1 else: odd[a[i]] += 1 x = sorted(even.items(), reverse=True, key=lambda t:t[1]) y = sorted(odd.items(), reverse=True, key=lambda t:t[1]) even_index = 0 odd_index = 0 if x[0][0] == y[0][0]: if x[0][1] > y[0][1]: even_index = 0 odd_index = 1 elif x[0][1] < y[0][1]: odd_index = 0 even_index = 1 else: if len(x) > 1: print(n - x[0][1] - max(x[1][1], y[1][1])) else: print(n // 2) exit() else: even_index = 0 odd_index = 0 print(n - x[even_index][1] - y[odd_index][1])