AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典:
AtCoder Regular Contest 020 B – 縞模様
実は以前投稿した問題にほとんど同じものがある(参考:AtCoder Beginner Contest 111 C – /\/\/\/ をPython3で解く)。こちらのほうが昔の問題なので、diffが高めに出ているのだろう。こちらは新たに解き直したつもりだが、驚くほど同じ解法になっていてちょっと笑ってしまった。
from collections import Counter
def main():
n, c = map(int, input().split())
colors = [int(input()) for _ in range(n)]
odds = colors[::2]
evens = colors[1::2]
odd_cnt = list(Counter(odds).items()) + [(0, 0)]
odd_cnt.sort(key=lambda x:x[1], reverse=True)
even_cnt = list(Counter(evens).items()) + [(0, 0)]
even_cnt.sort(key=lambda x:x[1], reverse=True)
odd_num = (n+1)//2
even_num = n // 2
if odd_cnt[0][0] != even_cnt[0][0]:
p_odd = odd_num - odd_cnt[0][1]
p_even = even_num - even_cnt[0][1]
result = (p_odd + p_even) * c
else:
p1_odd = odd_num - odd_cnt[0][1]
p2_odd = odd_num - odd_cnt[1][1]
p1_even = even_num - even_cnt[0][1]
p2_even = even_num - even_cnt[1][1]
result = min(p1_odd + p2_even, p2_odd + p1_even) * c
print(result)
main()
関連