DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 E - Majority of Balls
解法
キーとなるのは以下の2つの気付きです。
- に対する質問の答えと に対する質問の答えは必ず異なる。片方が
Red
であればもう片方はBlue
である。 - もし「赤青が半々ずつ」ということが分かっている 個のボールの集合が得られたとすると、ここにもう1つのボールを入れて質問することでそのボールの色を特定できる。
1.の事実を利用して、2.の「赤青が半々ずつ」である 個のボールの集合を求めようとしてみましょう。
まず に対する答えを質問します。これが Red
だと仮定します。この集合から「 を抜いて を入れる」という操作を1つずつしていくと、最終的には になって答えは Blue
になります。ということは、1個のボールの入れ替えで Red
から Blue
に変わる箇所が少なくとも1箇所あるはずです。
このような箇所は二分探索で求めることができます。上図のように Red
と Blue
には単調性がありませんが、このような場合でも二分探索では「Red
と Blue
が隣り合う箇所をどこでもいいから1つだけ見つける」ことができます。
※逆の視点で書くと、元々二分探索のアルゴリズムができることは「ある判定の結果が左端=A、右端=Bだと分かっているときに、A, Bが隣り合っている箇所をどこでもいいから1つだけ見つける」ことです。さらにもし単調性がある場合にはこの箇所がただ1つであり、そこを境界にしてAとBが真っ二つに分かれるので、最大値・最小値を求めるために使える、というわけです。
この二分探索に必要な質問回数は、 であることから7回以下です。最初の1回と合わせて、残り202回。
1個のボールの入れ替えで Red
から Blue
に変わる箇所が分かったとすると、以下の図のように 個のボールは「色が確定した2個のボール」と「赤青が半々ずつである 個のボールの集合×2」に分かれます。これが欲しかったものです。
あとは未確定のボールたちを、自分が含まれていないほうの「赤青が半々ずつである 個のボールの集合」に含めてクエリを投げれば色を確定できます。ボールの個数以上の質問回数が残っているので、質問回数も足りてこれで解けます。
ACコード
Submission #8584303 - DISCO Presents Discovery Channel Code Contest 2020 Qual
インタラクティブはAtCoderでは出題が少なく、実装にも慣れが要ると思います。Codeforcesでは比較的よく出るので慣れたい場合はそっちもオススメです。