水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

No.349 干支の置き物

No.349 干支の置き物 - yukicoder

絶対に隣りあわないパターンかどうかを判断する問題。


もしこの中で一番多い種類を考えると、ABABABABAのように1つ置きにAが現れるパターンが最大で、これを超えてしまうと絶対どこかで隣り合ってしまう。
よって一番多い種類が(n+1)//2個以下であればYES、そうでなければNOを出力する。


ちなみにこの類のカウントする問題は、Pythonを使っている場合、Counterを使うことで少し楽に処理が可能である。


以下、Python3での解答コード。

#81004 No.349 干支の置き物 - yukicoder

from collections import Counter
n = int(input())
c = Counter([input() for _ in range(n)])
print("YES" if (n+1)//2>=max(c.values()) else "NO")