AtCoder Beginner Contest 294 D問題 Bank
問題
提出解答
問題の概要
人の人がいる. これらの人は人
, 人
,
, 人
と名付けられている.
以下の 個のイベントを順に処理せよ.
受付に呼ばれていない人のうち, 最も小さい番号の人が受付に呼ばれる.
人
が受付に行く. (この時点で人
はすでに
回以上受付に呼ばれている.)
すでに受付に呼ばれているが受付に行っていない人のうち, 最も小さい番号の人が再度呼ばれる.
のイベントにおいて, 呼ばれた人の番号を求めよ.
制約
- 各イベントに対する制約
: 受付に呼ばれていない人が存在する.
: 人
は
回以上は受付に呼ばれていて, このイベントの直前までは人
は受付に行っていない.
: 受付に呼ばれているが, 受付に行ってない人はいない.
: この種類のイベントは
回以上起こる.
解法
で呼ばれる人は順番に
である.
よって, 次に で呼ばれる人を表わす変数
と受付に呼ばれたが受付に行っていない人の集合
を利用して, 次のようにして処理する.
.
- イベントの順に以下を行う.
:
に
を加え,
に
を加算する.
:
から
を削除する.
:
の最小値を取得する.
として順序つき集合を利用することにより, 計算量
時間で全て処理できる.