演習課題「素数判定をおこなう」
paiza ビルにあるエスカレーターは全長 K メートルあり、 1 秒で 1 メートル進みます。また paiza ビルに勤める社員が N 人おり、 i 番目の社員は時刻 A_i にエスカレーターに乗ります。各社員がエスカレーターに乗った直後に、エスカレーター上にいる人数をそれぞれ答えてください。ただしある時刻にエスカレーターに乗る社員と降りる社員がいた場合、これは同時におこなわれます。
この問題は少し難しいですが、キューを用いて実装してみましょう。なお、サンプル 1 のケースでは以下のように社員がエスカレーターに乗ります。
【入力される値】
N K
A_1 ... A_N
【条件】
すべてのテストケースにおいて、以下の条件をみたします。
・ N, A_i は 1 以上 50,000 未満
・ 1 ≦ A_1 < ... < A_N < 50,000
・ K は 1 以上 100 未満
【期待する出力】
社員 i がエスカレーターに乗った直後に、エスカレーター上にいる人数 E_i を改行区切りで出力してください。末尾には改行を入れ、余計な文字、空行を含んではいけません。
E_1
...
E_N
期待する出力値
1
2
2
2
＃06:キューの活用例
このチャプターでは、キューの活用例について学習します。
paiza のレベルアップ問題集にもキューを使って解く問題がいくつかあります。
スタック・キュー問題集で練習すると良いでしょう。
https://paiza.jp/works/mondai/stack_queue
キューは幅優先探索を行う際によく登場します。
深さ優先・幅優先探索問題集という問題集があるので、ぜひ覗いてみてください。
https://paiza.jp/works/mondai/bfs_dfs_problems
length = 5
queue = []
person_on_escalator = 0
for time in range(1, 10):
if time == 1:
queue.append(2)
person_on_escalator += 2
elif time == 3:
queue.append(5)
person_on_escalator += 5
elif time == 7:
queue.append(2)
person_on_escalator += 2
else:
queue.append(0)
if len(queue) > length:
person_on_escalator -= queue.pop(0)
print(person_on_escalator)