Codeforces Round #670 (Div. 2) E. Deleting Numbers
問題概要
インタラクティブ問題である。
まず正整数 が与えられる。ジャッジは 以上 以下の整数 を持っている。また集合 があり、初期状態では である。
以下のクエリを合計 回まで投げることができる。 の値を特定し、Cクエリで解答せよ。
A
: に含まれる の倍数の個数が返答される。B
: に含まれる の倍数の個数が返答される。その後、 に含まれる の倍数のうち でないものが から消去される。 でなければならない。C
: の値は であると解答する。このクエリは 回しか発行できない。
制約
解法
数 を絞り込んでいく基本方針としては、まずBクエリを投げて集合を変化させます。このとき「もし今までBクエリで投げた値の倍数が全部消えていれば、集合にはこの値が残っているはず」という状態を自分で管理しておきます。そしてAクエリ(Bクエリでも可)を投げて、返ってくる値が自分で管理している値と合わないならば、「これまで投げたBクエリの中に の約数が存在し、今投げたAクエリの値も の約数である」ということが分かります。このように情報を得るには「消去を試みる→残っているかチェック」という2段階が必要です。
クエリ数 は潤沢に見えますが、実際はほとんどの個数を「素数へのBクエリ」に使わないといけません。なぜなら が素数である場合、それを識別するためにはその素数そのものについてBクエリを投げる必要があるからです。10万以下の素数は 個なので、残り 回程度しか使えません。
また素数についてのBクエリを投げた後、その結果を確認するAクエリも必要です。再び素数全部についてAクエリを投げ直す余裕はないので、これは必然的に A 1
というクエリでまとめて確認することになります。
そのため素数をいくつかのグループに分けて、「1グループの素数全てについてBクエリを投げる→A 1
でチェック」という処理を繰り返すことにします。冒頭に書いた方法でAクエリの結果を照合し、自分で管理している値と合わないのであれば、このグループの中に の素因数が存在します。そのためグループ内の素数 全てについて改めて A
というクエリを投げて の素因数かどうかを判定します。
そして の素因数が1つ見つかれば、以降のグループの素数については、既に がBクエリに当たっているのでいきなりAクエリを投げて素因数かどうかの判定をすることができます。これで の素因数が全て分かります。
素因数が全て分かれば、あとは各素因数について をAクエリで投げることでその重複度が分かります。
この解法のクエリ数は
- (素数全てについて投げるBまたはAクエリ)
- 1グループの素因数の個数(ヒットした後の投げ直しパート)
- グループ数(
A 1
を投げる回数) - (重複度の合計の最大値)
- (Cクエリ)
を合計したものと見積もることができます。1グループの素因数の個数を に近い 程度にしておくことで、合計クエリ数が 程度になります。
時間計算量はBクエリに応じて集合を管理するところが一番重く、それぞれの数を高々1回しか投げないとすると調和級数で です。私の実装だと複数回 A 1
を投げるたびに 要素を見ているので正確にはこれに収まっていないのですが、収まるように実装することは可能です。