AtCoder Beginner Contest 228 D 問題 Linear Probing
問題
提出解答
https://atcoder.jp/contests/abc228/submissions/27409638
問題の概要
とする. 長さ
の列
があり, 最初は全ての項が
である.
以下の 個のクエリを順に処理せよ.
のとき
以下の処理を順に行う.-
とする.
-
である限り,
に
を加算する.
-
-
のとき
を出力する.
制約
または
なる
が存在する.
- 入力は全て整数である.
解法
であるから, 長さ
の列
を具体的に用意できる. このとき,
のクエリは単純に
を参照し, 出力するだけで完了する.
よって, の場合の処理を考える. 愚直な処理では, 2. において,
クエリの合計計算量が
となり, 間に合わない. 1.,3. は単純な代入であるから, 2. の処理の高速化を目指すことになる.
の処理を観察してみると, 一度更新された要素は二度と更新されないことがわかる. このことを利用して, 以下のように処理を行うことで, 高速に更新すべきインデックスを求めることができる.
- 最初,
とする. この
は
となる
全体の集合とする.
のクエリが来たとき, 以下のように処理する.
とする.
の要素で,
以上である要素が存在するとき,
を
にある
以上の最小の要素とする.
の要素で,
以上である要素が存在しないとき,
とする.
とする.
から
を除く.
この処理を高速に行うためのデータ構造の条件は,
にある
以上の最小の要素を高速に求めることができる.
から要素を削除する処理ができる.
である.
これを可能にするデータ構造は, 例えば, 順序付き集合や, Binary Tire などがある. Binary Tire を用いた場合の計算量は, である.
また, 別解として, Union-Find を用いる方法がある (計算量