図解解説シリーズ
競技プログラミングを始めたばかりでAtCoderの解説やJOIの解説ではいまいちピンと来ない…という人向けに、図解を用いて解説を行います。
問題文
情報オリンピック日本委員会に掲載されている問題
AtCoderに掲載されている問題
入出力など実際に確認して自分の作成したプログラムを採点することができます。
図解解説
今年度の一次予選のD問題は、以下の５つのスキルを確認する問題になっています。
１．入力・出力を正しく利用できる
２．算術演算子を正しく利用できる
３．条件分岐（if）を正しく利用できる
４．繰り返し処理を正しく利用できる
５．配列（リスト）を正しく利用できる
問題文を整理するために、具体的な数字を用いて、図示して考えてみます。
箱とボールのどちらを基準にして操作を行うか、入力例１を使ってシミュレーションしてみます。
箱を基準に考えてみると、箱の中にボールが１個も入っていない状況や、箱の中にボールがたくさん入っている状況が発生します。特定のボールがどの箱の中に入っていて、次にどの箱に動かせばいいのか…と考えるのも大変です。
一方、ボールを基準に考えてみると、今、ボールがどの箱の中に入っているのか管理するだけで済みます。変更の発生するところだけ変更すれば済みます。
従って、今回は、ボールを基準にして管理する方法でプログラムを行うことにします。
そこで、Ballという配列を用意して、その配列の要素の中に箱の番号を入れて状態を管理します。
配列は、要素番号0から始まります。もし、配列の要素数をボールの数と一致させると、箱とボールの番号も0に読み替えて管理する必要があります。0から管理しなくてもすむように、配列の要素数を「ボールの数+1」にして、箱とボールの番号をそのまま使用すると便利です。
解答例
d.py
N,M = map(int,input().split())
#ボールがどの箱に入っているか管理するための配列Ballを宣言し、初期値(ボールの番号=箱の番号)を代入
Ball = []
for i in range(N+1):
Ball.append(i)
#ボールXが箱Yに移動する操作をM回実行
for i in range(M):
X,Y = map(int,input().split())
Ball[X]=Y
#最終的にどの箱に入っているかボール1からボールNまで順番に出力
for i in range(1,N+1):
print(Ball[i])
イラスト
スライド内で使用しているイラストはすべて「いらすとや」の素材を利用しています。