第8話 鏡餅

はじめに

　こちらでは，競技プログラミングコンテストサイトAtCoderの常設コンテスト「AtCoder Beginners Selection」に筆者が挑戦します．記事には，筆者が作成したコード(使用言語はPython)と簡単な解説を載せますので，プログラミング初心者の方の参考になれば幸いです．なお，この記事では，Pythonの詳細な文法については解説致しませんので，そちらに関しては関連記事および文献等を参照して頂きたく存じます．

問題(ABC085B - Kagami Mochi)

　X 段重ねの鏡餅 (X≥1)とは，X枚の円形の餅を縦に積み重ねたものであって，どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです．例えば，直径 10，8，6 センチメートルの餅をこの順に下から積み重ねると 3段重ねの鏡餅になり，餅を一枚だけ置くと 1段重ねの鏡餅になります．
ダックスフンドのルンルンは N枚の円形の餅を持っていて，そのうち i 枚目の餅の直径は d_iセンチメートルです．これらの餅のうち一部または全部を使って鏡餅を作るとき，最大で何段重ねの鏡餅を作ることができるでしょうか．

コード(解答例)

N = int(input())
d =[]
for i in range(N): 
    d.append(int(input()))

d = sorted(d, reverse=True)

if N > 0:
    count_layer = 1
else:
    count_layer = 0

for i in range(N-1):
    if d[i] > d[i+1]:
        count_layer += 1

print(count_layer)

解説

　ポイントとしては，餅の直径に基づきソートする点です．ソート後は，隣り合う要素の大小関係を見ながら，層の数を更新します．ただし，同じ直径の餅を重ねることができない点に注意する必要があります．