AtCoder Beginner Contest 294 D問題 解説(Pythonコード付)

はじめに　

　本記事はPythonでAtcoderにチャレンジしているけど、Pythonはコード例がないため解説がわかりにくい！と感じている方を対象としています。
　私自身大してレートも高くないので、不備等あるかもしれませんがご了承くださいm(_ _)m
　質問や指摘などもコメント等に書いてくださったら対応していきたいと考えていますのでどしどしコメントしてください。(内容がわかりにくいぞ！みたいな文句でもオールオッケーです笑)

AtCoder Beginner Contest 294 D問題

　問題のURLはこちらです。AtCoder Beginner Contest 294 D問題

使う手法　

今回は優先度付きキューを使っていきます。
優先度付きキューはデータ構造の一つで、一般的なキューは配列に入れた順番通りにタスクを処理しますが、これに優先度をつけてることで処理する順番を変えていきます。　
　詳しくはこちらを見てみてください。

考え方

　今回の問題は、優先度付きキューである「called」と、集合型である「go」の二つのデータ構造を使って状態を管理していきます。「called」はすでに呼び出された人間を格納し、「go」は受付に向かった人を格納します。　
　クエリに沿って見ていくと、クエリ1が発生した際には一番小さい値の人をcalledに格納し、クエリ2が発生した際には呼び出された人の値をgoに格納し、クエリ3が発生した際にはcalledから値を取り出し、goに格納されていなければその値を出力する、といった形で処理を行なっていきます。　
　Pythonではheapqと呼ばれるライブラリがあり、こちらで作成した優先度付きキューは値が最も小さいものをpopできるので、今回はこちらを用いてコーディングを行なっていきます。

実装例　

import heapq
#標準入力 
n,q = map(int,input().split())
#状態を管理するcalledとgoの作成
called = list()
go = set()

#calledを優先度付きキューに変換
heapq.heapify(called)

#呼ばれていない人の中で、最小の値を管理する。初期値は1であり、クエリ1が実行されるたびに+1していく。
min_num = 1
 
for _ in range(q):
　#クエリの受け取り
  eve = list(map(int,input().split()))
  if eve[0] == 1 :
　　#min_numをcalledに追加する。
    heapq.heappush(called,min_num)
    min_num += 1
  elif eve[0] == 2 :
    #受付に行った人の値をgoに追加する。
    go_num = eve[1]
    go.add(go_num)
  else :
    booler = True
    while booler :
　　　 #calledから値が最も小さなものを取り出す。
      k = heapq.heappop(called)
　　　 #取り出した値がgoに格納されているか調べる。
      if k not in go :
        print(k)
        booler = False
　　　　　#取り出した値は消えてしまっているため、ここで一度追加する。
        heapq.heappush(called,k)
        break

最後に　

　上に挙げたコードをPythonで実行すると、2問ほどTLEになってしまいます。なので、上記のコードを実行する際には言語をPyPyにして実行してください。
　久々の投稿で、文章がわかりにくいところもあると思うので、その時は遠慮なくコメントしてくださいm(_ _)m