図解解説シリーズ

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

問題文

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

AtCoderに掲載されている問題

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

図解解説

今年度の二次予選のA問題は、以下のスキルを確認する問題になっています。
１．スタック・キューなどの特殊なデータ型を正しく利用できる

問題文を整理するために、入力例１を用いて、図示して考えてみます。

この動きは、スタックと呼ばれるデータ構造にあてはまります。スタックの概念については、以下のサイトが参考になります。アニメーションがついているため動作のイメージをつかむことができます。合わせてキューというデータ構造もありますので、一緒に覚えておいてください。

Pythonではキューとスタックの両方を兼ね備えた両端キューを使用します。

今回の問題ではスタックの動きを実装するので、appendとpopの命令を使用します。
※2021/12/18 12:20　スライドを差し替えました

解答例

a.py

#両端キュー(deque)を使用するためにライブラリを読み込む
from collections import deque
N = int(input())
#書籍を格納するための両端キューを作成する
q = deque()
#先頭から順番に読み込み、
#　READなら両端キューの末尾にある書籍を取り出して表示する
#　READでなければ、両端キューの末尾に書籍を追加する
for i in range(N):
  s = str(input())
  if s=='READ':
    print(q.pop())
  else:
    q.append(s)

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

イラスト

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