ABC475 E - Quiz Competition: Qualifiers

考え方

予選通過者の判定アルゴリズムをよく見ると、これは辞書順評価などとほぼ同じことをしている。
よって、正解を '0'、不正解を '1' と割り当てて、辞書順に並べれば通過順がわかる。

ただし、いくつか注意点がある。

$1$ つめに、最後まで全く同じ解答をした人の扱い。
仮に $M=10$ だとして、辞書順ソート $10$ 番目と $11$ 番目が同じなら、両者予選落ちである。
つまり、自分が $M$ 位以内かではなく、$M+1$ 位の人よりもいい解答だったかで調べる必要がある。
実際に $M+1$ 位を取得する方針と、自分と同等以上が $M$ 人以下か調べる方針がある。
ただし、前者は $M=N$ の場合に範囲外アクセスになるという問題が発生する。

$2$ つめに、全問不正解者の扱い。
$M=N$ の場合、全問不正解でも $M$ 位以内になるが、この場合は予選敗退になる。
これは、全問不正解の人を $1$ 人番兵で入れておくとよい。
すると、全問不正解者はその人と同順位扱いになり、$M$ 位以内に入れなかったと判定される。
ついでに、$M=N$ の場合に範囲外アクセスする問題も同時に解消されて一石二鳥。

ということで、これを実装すればよい。
そのためには、配列に類似していながら、以下が全て $O(K\log N)$ 以下でできるデータ構造が必要となる。

• 文字列の追加ができる
• 文字列の削除ができる
• 以下のいずれか
  • 辞書順で小さい方から $M+1$ 番目の文字列をいつでも取得できる
  • 辞書順が指定文字列以下であるデータの個数をいつでも取得できる

実はPythonなら、sortedlistというデータ構造が使用可能ライブラリにあるらしい。
多重集合として常時ソートされていて、かつランダムアクセス可能。
つまり、Python使いならこの時点でほぼ解き終わっている。ずるい。

C++ 使いは自力で頑張るしかなく、主に以下の $3$ つの方針が考えられる。

• priority_queue を $4$ 本使って、中央値管理と同じアルゴリズムで $M+1$ 番目の文字列を取得する
• クエリを全て先読みし、座標圧縮してからFenwick木で指定文字列以下であるデータの個数を取得する
• 重み付きTrie木に累積和機能を搭載し、$M+1$ 番目の文字列を取得する

方針 $1$

priority_queue を $4$ 本使って、中央値管理と同じアルゴリズムで $M+1$ 番目の文字列を取得する。

以下の $2$ 本の priority_queue を用意する。

• 「左側」用の、大きい方を取り出す priority_queue
• 「右側」用の、小さい方を取り出す priority_queue

ここに値を追加していき、常に「左側」のトップが「右側」のトップ以下であるように保つ。
左側の個数が $M$ 個になっていれば、「右側」のトップが $M+1$ 位になっている。

問題は、データの削除が大変なこと。
priority_queue は、トップに来ていない中身の削除はできない。
そこで、遅延処理用に左右それぞれ「削除されたと見なす文字列」を入れる priority_queue を追加する。
先頭が変化する処理ごとに、本体と削除用のトップが一致していたらそれらを削除するようにすればよい。

計算量は $O(K(N+Q)\log(N+Q))$ となる。
実装例は「解答例」のコード参照。

方針 $2$

クエリを全て先読みし、座標圧縮してからFenwick木で指定文字列以下であるデータの個数を取得する。

クエリを先読みし、登場する可能性がある文字列を先に全て列挙してしまう。
それを座標圧縮し、Fenwick木の各要素に割り当てる。
文字列が追加されたらそこに $+1$、削除されたらそこに $-1$ をする。
Fenwick木で先頭から指定文字列までの和をとれば、その文字列以下の個数になる。

計算量は $O(K(N+Q)\log(N+Q))$ となる。
「解答例2」のコード参照。

方針 $3$

重み付きTrie木に累積和機能を搭載し、指定文字列以下であるデータの個数を取得する。
もしくは、$M+1$ 番目の文字列を取得する方針でもよい。

AtCoder LibraryにはTrie木がないので、自前ライブラリの実装を頑張る。

計算量は $O(K(N+Q))$ となる。
「解答例3」のコード参照。

入力例1での動作

入力を受け取る。

n: 5
m: 3
k: 3
t: "oxo"
s: {"oxo", "oxx", "xxo", "xox", "xoo"}
q: 3
queries:
(5, 1)
(1, 3)
(4, 1)

方針 $1$

正解を 0、不正解を 1 として各参加者の解答を文字列に変換すると、次のようになる。

さらに、全問不正解を表す番兵 111 を $1$ つ追加する。

方針 $1$ では、辞書順で小さい方から $M=3$ 個を「左側」、残りを「右側」として管理する。
「右側」の先頭が $M+1=4$ 番目の文字列である。
変更された参加者の評価文字列がこれより小さければ Yes となる。

初期状態では、左側が 000, 001, 100、右側が 110, 111, 111 である。

各クエリ後の状態は次のようになる。

したがって、各クエリへの答えは順に Yes, Yes, No となる。

方針 $2$

まず、クエリを全て先読みして、登場する可能性がある評価文字列を列挙する。
入力例1では、番兵も含めると 000, 001, 010, 011, 100, 110, 111 の $7$ 種類が登場する。

これをこの順に座標圧縮し、Fenwick木で各評価文字列の人数を管理する。
Fenwick木の内部配列そのものではなく、管理している配列として見ると、初期状態は次のようになる。

評価文字列が変更されたら、変更前の位置に $-1$、変更後の位置に $+1$ をする。
各クエリ後の配列は次のように変化する。

各クエリで、変更された参加者の評価文字列までの累積和をFenwick木で求める。
その人数が $M=3$ 以下なら Yes、$4$ 人以上なら No である。

したがって、各クエリへの答えは順に Yes, Yes, No となる。

方針 $3$

Trie木の各ノードに、その部分木に存在する評価文字列の個数を持たせる。
評価文字列が変更されたら、変更前の文字列を $-1$、変更後の文字列を $+1$ して更新する。

指定文字列以下の個数を求めるときは、先頭から順にTrie木をたどる。
現在見ている文字が 1 なら、0 側の部分木にある文字列は全て指定文字列より小さい。
そこで、その個数を答えに加えてから 1 側へ進む。
最後までたどったら、指定文字列と全く同じ文字列の個数も加える。

入力例1では、各クエリについて次のようになる。

したがって、各クエリへの答えは順に Yes, Yes, No となる。

注意点

特になし。

別解

方針 $2$、方針 $3$ を参照。