BETA

AtCoder Beginner Contest 111

投稿日:2019-07-05
最終更新:2019-07-05

問題

数列 a1,a2,...,an が以下の条件を満たすとき、 //// と呼ぶことにします。
各i=1,2,...,n2 について、ai=ai+2
数列に現れる数はちょうど 2 種類偶数長の数列 v1,v2,...,vn が与えられます。 要素をいくつか書き換えることでこの数列を //// にしたいです。 書き換える要素の数は最小でいくつになるか求めてください。

考えたこと

  • setに変換し順列組み合わせを試し、愚直に試す。

不正解だったコード

import itertools  
N=int(input())  
L=list(map(int,input().split()))  
data=list(set(L))  
S=list(itertools.permutations(data, 2))  
ans=[]  
for s in S:  
  p=0  
  for i in range(N):  
    if i%2==0:  
      if s[0]==L[i]:  
        p=p  
      else:  
        p=p+1  
    else:  
      if s[1]==L[i]:  
        p=p  
      else:  
        p=p+1  
  ans.append(p)  
print(min(ans))  

正解したコード

import collections  
N=int(input())  
L=list(map(int,input().split()))  
E=[i for i in L[::2]]  
O=[i for i in L[1::2]]  
e = collections.Counter(E).most_common()  
o = collections.Counter(O).most_common()  
if e[0][0] != o[0][0]:  
    print(N - e[0][1] - o[0][1])  
else:  
    if len(e) == 1 or len(o) == 1:  
        print(N // 2)  
    else:  
        a = N - e[1][1] - o[0][1]  
        b = N - e[0][1] - o[1][1]  
        print(min(a, b))  
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

aocoryの技術ブログ

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
or 外部アカウントではじめる
10秒で技術ブログが作れます!