【図解解説】JOI2021-2022 一次予選 第1回 問題4 箱と鍵

図解解説シリーズ

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

問題文

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

AtCoderに掲載されている問題

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

図解解説

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

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

入力例１を使って考えます。N=４個の宝箱と、M=４個の鍵があります。宝箱と鍵にはそれぞれ番号が振られていて、宝箱と鍵が同じ番号ならその鍵で宝箱を開けることができます。番号が同じ宝箱なら、１つの鍵で複数の宝箱を開けることもできます。このとき、宝箱をいくつ開けることができるか考えるのがこの問題です。

そこで、宝箱を１つずつ鍵に合わせて開けられる鍵があるかどうか確認する方法で処理を行ってみます。変数cntを作成し、宝箱が開いたらcntの値を1増やすことで、開いた宝箱の数を管理することにします。この方針に従って作成したプログラムが以下のものとなります。

d1.py

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
#開けることができた宝箱の数を管理する変数cntを初期値0で作成する
cnt = 0
#宝箱を基準に繰り返し処理をN回実行する
for i in range(N):
  #M個の鍵に対して一つずつ確認を行い、一致するものがあったらcntの値を1増やす
  for j in range(M):
    if A[i]==B[j]:
      cnt = cnt + 1
#変数cntの値を出力して終了
print(cnt)

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

採点結果を見てみると、不正解WAが発生しています。なぜこのような状況になったのでしょうか？

入力例１を使って丁寧に状況を見てみると、最後の宝箱を開けるときに、同じ鍵が２つあるため余計に数えていることがわかります。宝箱を開けることができたら、鍵を探す作業を中断できれば、正しく数を数えることができそうです。

Pythonには、breakという命令があります。この命令を使用すると、現在実行中の繰り返し処理を中断することができます。２重ループのように繰り返し処理が重なっている場合は、１つの繰り返し処理だけ中断することになります。

なお、Pythonには配列の中に調べたい値があるかどうかチェックするためのin演算子があります。今回のように重複する値があったとしても、意識することなく「値があるかどうか」を確認することができます。記述方法は、解答例「in演算子を使用したプログラム」を確認してください。

解答例

中断処理を記述したプログラム

d2.py

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
#開けることができた宝箱の数を管理する変数cntを初期値0で作成する
cnt = 0
#宝箱を基準に繰り返し処理をN回実行する
for i in range(N):
  #M個の鍵に対して一つずつ確認を行い、一致するものがあったらcntの値を1増やす
  #同じ番号の鍵があると正しい答えを出すことができないので、鍵を探す作業を中断するためにbreakを実行する
  for j in range(M):
    if A[i]==B[j]:
      cnt = cnt + 1
      break
#変数cntの値を出力して終了
print(cnt)

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

in演算子を使用したプログラム

in演算子を使用すると、スッキリとしたプログラムになります。言語固有の機能を有効活用することで、複雑な処理を簡単に記述することができます。

d3.py

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
#開けることができた宝箱の数を管理する変数cntを初期値0で作成する
cnt = 0
#宝箱を基準に繰り返し処理をN回実行する
for i in range(N):
  #i番目の宝箱に対応する鍵があるかどうかin演算子を使ってチェックする
  #一致する鍵があったら、変数cntの値を1増やす
  if A[i] in B:
    cnt = cnt + 1
#変数cntの値を出力して終了
print(cnt)

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

イラスト

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