競技プログラミング

【超初心者向け】AtCoderで最初に解くべき過去問集を分かりやすく解説します【7問目】

プログラミング

こんにちは!サトシです!

 

この記事では、「AtCoderに登録して最初に解くべき10問(AtCoder Beginners Selection)」の7問目「Kagami Mochi」をめちゃくちゃ分かりやすく解説していきます。

AtCoder で問題を解くためには、新規登録しないといけません。

新規登録はこちらから → AtCoder に新規登録する

 

それでは、「Kagami Mochi」の解説をしていきます!

プログラミング
【競プロ】最初に解くべき過去問10問をPythonで分かりやすく解説します!【AtCoder】こんにちは!サトシ(@satoshi365_blog)です! この記事では、「競技プログラミング(AtCoder)に登録し...

7問目「Kagami Mochi」で身につくスキル

この問題では、こんなスキルが身につきます。

身につくスキル
  • len() の使い方
  • set() の使い方

先に、これがどのようなスキルなのかを説明します。

 

len() の使い方

len() を使うと、リストの要素の数が分かります。

例えば、下のように書きます。

a = [1, 4, 2, 3]
print(len(a))   # 4 と出力

b = [0, 0, 4, 2, 4, 5]
print(len(b))   # 6 と出力

 

※今回は、set型の要素の数を求めるために使います。len() は set型の要素の数も求めることができます。set型については下の「set() の使い方」をお読みください。

set() の使い方

set() を使うと、リストの中にある重複している数を取り除くことができます。

例えば、下のように書くと、リスト [3, 4, 4, 2, 3, 1] を {1, 2, 3, 4} とすることができます。

a = set([3, 4, 4, 2, 3, 1])
print(a)   # {1, 2, 3, 4} と出力

 

上の例で出力した、{1, 2, 3, 4} はset型と呼ばれます。

a = set([3, 4, 4, 2, 3, 1])
print(type(a))   # <class 'set'> と出力

7問目「Kagami Mochi」の解説

下の順番で解説していきます。

  • 問題文
  • 入力例と出力例
  • 解答例
  • 解説

それでは見ていきましょう。

 

問題文

 

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

制約
・1 ≤ N ≤ 10
・1 ≤ di ≤ 100
・入力値はすべて整数である。

入力
入力は以下の形式で標準入力から与えられる。

N
d1
.
.
dN

出力
作ることのできる鏡餅の最大の段数を出力せよ。

ABC085B – Kagami Mochiより引用

 

入力例と出力例

入力例

5
10
40
20
40
40

出力例

3

上の例だと、「10, 40, 20, 40, 40」センチメートルのお餅を持っています。

下から順番に「40, 20, 10」とすると、1番多くお餅を重ねることができます。(問題文を見ると、同じサイズのお餅を重ねるのはダメらしい)

 

今回の例では、3段の鏡餅を作れるので、「3」を出力します。

 

解答例

d = [int(input()) for _ in range(int(input()))]
print(len(set(d)))

解説

今回の問題は、下の手順で解いていきます。

  1. 入力を受け取る
  2. set() で入力の重複をなくす
  3. len() で要素の数を求める

 

今回の問題で気をつけるポイントは、「同じサイズのお餅は重ねることができない」ということです。

なので、同じサイズのお餅を無視するだけで、この問題は解けます。

つまり、今回することは、set() と len() を使って「何種類のサイズのお餅があるか」を数えるだけです。

 

では、コードを詳しく解説していきます。

 

まずは、入力を受け取ります。

※int(input()) より先に range(int(input()) が先に動くので、range(int(input()) の input() に N が入力されることに注意してください!

d = [int(input()) for _ in range(int(input()))]

 

何種類のサイズのお餅があるかを求めて、出力します。

print(len(set(d)))

 

 

まとめとして、もう一度プログラムを確認してみましょう。

d = [int(input()) for _ in range(int(input()))]
print(len(set(d)))

これで「作ることのできる鏡餅の最大の段数」を求めることができました。

まとめ

もし分からない点などありましたら、気軽にTwitterなどでご質問ください^^

少しでも参考になれば嬉しいです!

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です