【図解解説】JOI2021-2022 一次予選 第2回 問題4 希少な数

図解解説シリーズ

競技プログラミングを始めたばかりでAtCoderの解説やJOIの解説ではいまいちピンと来ない…という人向けに、図解を用いて解説を行います。

問題文

情報オリンピック日本委員会に掲載されている問題

AtCoderに掲載されている問題

入出力など実際に確認して自分の作成したプログラムを採点することができます。

図解解説

今年度の一次予選のD問題は、以下の５つのスキルを確認する問題になっています。
１．入力・出力を正しく利用できる
２．算術演算子を正しく利用できる
３．条件分岐（if）を正しく利用できる
４．繰り返し処理を正しく利用できる
５．配列（リスト）を正しく利用できる

問題文を整理するために、具体的な数字を用いて、図示して考えてみます。

出現回数が入っているリストAを先頭から一つずつ確認し、数え上げていきます。出現回数をまとめると、2,5,8が1回、4が2回出現します。出現回数が最小の数字の中で最小の整数が答えとなるので、入力例２では2が正解となります。

ここで、どのように数え上げていけばいいか考えます。問題文から、1<=Ai<=2000となっているため、最大2000種類の整数が出現します。また、リストAの要素数は1<=N<=100となっていることから、出現回数は最大100回となります。

そこで、2通りの方法を考えてみます。リストAの先頭から確認していく作業はどちらも同じです。

1つ目の方法は、出現回数を保存するリストBを作成します。1～2000までの整数を数え上げることができればよいので、要素数を2001にしたリストを用意します（0は使用しませんが、そのほうが操作が楽になります）。リストAの先頭から1つずつ数字を確認し、該当する数字の要素番号の値を1増やします。そうすることで、リストBにそれぞれの数字の出現回数を保存することができます。最後に、リストBの先頭から出現回数が1以上の値を確認し、最小の出現回数が出てきたらその値を変数に保存します。以上で最小の整数を求めることができます。

2つ目の方法は、Python固有のcountメソッドを使用して数字が何個あるか確認を行います。同じ数字を何度も調べてしまい効率が悪いと感じるかもしれませんが、この方法で考えてみます。現在の出現回数の最小値と数字を保存する変数が必要になりますが、解答例のように丁寧に整理してプログラムを記述してください。リストAの数字は小さい順に並んでいませんので、出現回数が同じ場合は必ず数字の大小関係を比較するように注意してください。

解答例

N = int(input())
A = list(map(int,input().split()))
#出現回数を保存するリストを作成し、初期値をすべて0にする
B = []
for i in range(2001):
  B.append(0)
#要素番号=数値として、先頭からリストAをチェックし出現したら+1する
for i in range(N):
  B[A[i]] = B[A[i]] + 1
#答えを探すために数字と出現回数を記録するための変数を用意
#最初に大きな値を設定しておいて、これよりも小さい値が出てきたら書き換える
suji = 3000
kaisu = 1000
#先頭から順番に確認を行い出現回数が1以上のものが見つかったら、
#保存している出現回数と大小関係を比較する
#もし、保存している値よりも出現回数が小さかったら数字と出現回数を書き換える
for i in range(2001):
  if B[i]>=1:
    if kaisu>B[i]:
      kaisu=B[i]
      suji=i
#最後に数字を表示
print(suji)

採点サイトに提出したプログラム

N = int(input())
A = list(map(int,input().split()))
#答えを探すために数字と出現回数を記録するための変数を用意
#最初に大きな値を設定しておいて、これよりも小さい値が出てきたら書き換える
suji = 3000
kaisu = 1000
#先頭から順番に確認を行いcountメソッドを使って出現回数を数え保存している出現回数と大小関係を比較する
#もし、保存している値よりも出現回数が小さかったら数字と出現回数を書き換える
#保存している値と出現回数が同じだったら、保存している数字と大小関係を比較し、数字が小さかったら数字を書き換える
for i in range(N):
  if A.count(A[i])<kaisu:
    kaisu = A.count(A[i])
    suji = A[i]
  elif A.count(A[i])==kaisu:
    if A[i]<suji:
      suji = A[i]
#最後に数字を表示
print(suji)

採点サイトに提出したプログラム

イラスト

スライド内で使用しているイラストはすべて「いらすとや」の素材を利用しています。