DISCO 2020 (HEAT) E - Majority of Balls

atcoder.jp

目的

解法を文字に起こす練習
一度やってみたかった

概要

合計2N個のボールが一列に並んでいる
赤いボールと青いボールがそれぞれN個ずつある（Nは奇数）
何番目のボールがどの色かわからないが、ヒントを聞ける
ぴったりN個のボールを番号で指定して、赤いほうが多いか青いほうが多いかを尋ねると答えが返ってくる
何度か質問して2N個の並び順を確定するのが目的

ひねりポイント*1

これはインタラクティブな問題です。（普通に生活をしていると触れない問題なのでむずい、デバッグがつらい）
直接何番目のボールが何色かを知れない
ボールの数の差が分からない（10対1でも6対5でも同じ答えが返ってくる）
質問回数の上限が絶妙（適当に聞いてたら足りなそうじゃない？）

思考

一つずつずらしていって、違う回答が返ってくるところに着目すればよさそう？*2

なぜか…一つ落として一つ追加する　という操作で、例えばそれまでRedだったのがBlueになった場合、
1. 落としたものは赤
2. 追加したものは青
3. 残りのN-1個は赤と青が半々（制約よりNは必ず奇数）
ということがわかるため

f:id:yosutecon:20191124032755p:plain — 怪画１

上図の赤丸をL番目とすると、青丸はL+N番目になる

1～L-1番目、L+N+1～2N番目（上図でいう赤丸と青丸の外側）に関しては、L+1～L+N-1番目と同時に一つずつ聞いていけば一意に定まる（N-1個が半々ということがわかっているので、はみ出した1個のみで判定される）

1～L番目、L+N～2N番目が決まったが、この中に赤玉と青玉はどちらも必ず(N-1)/2個以上含まれているので、適当にこの中から赤玉を(N-1)/2個、青玉を(N-1)/2個選んでおけば、同じような方法でL+1～L+N-1番目（上図でいう内側）も一意に定まる
特定作業には2N回弱かかるので、ヒントを聞ける回数は残り10回くらいしかない

つまり最初に10回くらいで違う回答が返ってくる場所を特定しないといけない（本番はここで詰んだ）

怪画２
頭から見ていく方法だと、例えばこういう順だと詰む
あたりまえポイントとして、1回目に任意のN個を選んでヒントを聞いて、次に前回選ばなかったN個を選んでヒントを聞いたとき２つの結果は必ず異なっている

怪画3

なので、最初に1～NとN+1～2Nの結果を持っておいて（両者は必ず異なる）、そこから二分法で境界を探せばよい（中央のヒントを聞いて、それと同じ方の端を中央に近付けることを繰り返す）

N<100なので細かい計算してないけどだいだい10回くらいで終わるだろうし
現場猫