ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #670 (Div. 2) E. Deleting Numbers

Problem - E - Codeforces

問題概要

インタラクティブ問題である。

まず正整数  n が与えられる。ジャッジは  1 以上  n 以下の整数  x を持っている。また集合  s があり、初期状態では  s=\lbrace 1, 2, ..., n\rbrace である。

以下のクエリを合計  10000 回まで投げることができる。 x の値を特定し、Cクエリで解答せよ。

  • A  a s に含まれる  a の倍数の個数が返答される。
  • B  a s に含まれる  a の倍数の個数が返答される。その後、 s に含まれる  a の倍数のうち  x でないものが  s から消去される。 a \gt 1 でなければならない。
  • C  a x の値は  a であると解答する。このクエリは  1 回しか発行できない。

制約

  •  1 \le n \le 10^{5}

解法

 x を絞り込んでいく基本方針としては、まずBクエリを投げて集合を変化させます。このとき「もし今までBクエリで投げた値の倍数が全部消えていれば、集合にはこの値が残っているはず」という状態を自分で管理しておきます。そしてAクエリ(Bクエリでも可)を投げて、返ってくる値が自分で管理している値と合わないならば、「これまで投げたBクエリの中に  x の約数が存在し、今投げたAクエリの値も  x の約数である」ということが分かります。このように情報を得るには「消去を試みる→残っているかチェック」という2段階が必要です。

クエリ数  10000 は潤沢に見えますが、実際はほとんどの個数を「素数へのBクエリ」に使わないといけません。なぜなら  x素数である場合、それを識別するためにはその素数そのものについてBクエリを投げる必要があるからです。10万以下の素数 9592 個なので、残り  400 回程度しか使えません。

また素数についてのBクエリを投げた後、その結果を確認するAクエリも必要です。再び素数全部についてAクエリを投げ直す余裕はないので、これは必然的に A 1 というクエリでまとめて確認することになります。

そのため素数をいくつかのグループに分けて、「1グループの素数全てについてBクエリを投げる→A 1 でチェック」という処理を繰り返すことにします。冒頭に書いた方法でAクエリの結果を照合し、自分で管理している値と合わないのであれば、このグループの中に  x の素因数が存在します。そのためグループ内の素数  p 全てについて改めて A  p というクエリを投げて  x の素因数かどうかを判定します。

そして  x の素因数が1つ見つかれば、以降のグループの素数については、既に  x がBクエリに当たっているのでいきなりAクエリを投げて素因数かどうかの判定をすることができます。これで  x の素因数が全て分かります。

素因数が全て分かれば、あとは各素因数について  p^{2}, p^{3}, ..., をAクエリで投げることでその重複度が分かります。

この解法のクエリ数は

  •  9592素数全てについて投げるBまたはAクエリ)
  • 1グループの素因数の個数(ヒットした後の投げ直しパート)
  • グループ数(A 1 を投げる回数)
  •  16 (重複度の合計の最大値)
  •  1 (Cクエリ)

を合計したものと見積もることができます。1グループの素因数の個数を  \sqrt{9592} に近い  100 程度にしておくことで、合計クエリ数が  9800 程度になります。

時間計算量はBクエリに応じて集合を管理するところが一番重く、それぞれの数を高々1回しか投げないとすると調和級数 O(n \log n) です。私の実装だと複数回 A 1 を投げるたびに  n 要素を見ているので正確にはこれに収まっていないのですが、収まるように実装することは可能です。

ACコード

Submission #92678910 - Codeforces