脳log[20240922]

2024年09月22日 (日) [AtCoder] 精進。今日あった ARC184-A Appraiser (水 diff)。600 点問題だけど、たぶんインタラクティブ加算が +100 か +200 あるから、実質的な難易度に基づく配点は 400 か 500 あたり。N-1 回クエリできるならすべてのコインを裏表どちらかに分類することができて、もちろん 10 枚だけの方が偽物グループということになる。ところがコイン枚数 N=1000 に対してクエリ上限 Q=950 なので、999 回クエリすることはできない。ところで、１から N までのシャッフルされた順列をソートされた状態にするのに、スワップ回数は必ずしも N-1 回いらないんですよ。N 項が G 個のグループに分かれて、グループ内で玉突きによって位置を交換しているとき、グループのサイズ引く１回の交換でグループ内の要素を目的の位置に置くことができる。全体では N-G 回の交換でソート済みの状態にできる。この問題ではどうか。仮にグループ内の比較のみによって真贋が定まるのであれば、グループをまたいだ比較を節約することができる。グループとは？ たとえば 10 回の比較で 11 枚が同種だと判定されたら、その 11 枚は本物に決まる。たとえば 20 回の比較で 21 枚が 10 対 11 に分かれたなら、双方の真贋が決まる。このボーダーは未確認のコインの中に本物と偽物が何枚あるかによって動くし(少ない方＋１になる)、選んだコインに偽物が何枚含まれるかという偶然によってもグループのサイズが変動する。最も幸運なケースでは最小 20 回のクエリで 10 枚の偽物を見つけられる。最も不運なケースでは、900 回の比較によって 990 枚の本物を見つけて、消去法で残りの 10 枚が偽物に決まる。最も不運とは書いたけど、終盤は少なくなってきた本物を的確に選んでいるので実は不運ではない。クエリ回数も最大ではないかもしれない。でもクエリ１回につき１個以上の偽物を見つけるとしても見つけられないとしても、900 に +50 回もあれば足りそう。■提出 #58038450 (AC / 1343 Byte / 112 ms)。一番頭を使ったのが 38 行目のボーダーラインを定める式(b = [m,[k-m,10].min].min)。多数派が b より多くなると多数派の真贋が決まるので、即座にグループを閉じて次の要素からまた新しいグループを始める。グループが多いほどグループをまたいだ比較をせずに済んでクエリが節約できる。まだあった。グループを処理する F 関数を実装しているときに、残りの要素の真贋が同数のケースに対処する必要があると思った。未判定コインの中に本物と偽物が同数ある場合。多数派がないからお前が偽物だ(本物だ)と決められない。これはすでに真贋が明らかになっている要素との比較で対処することにした。F 関数の引数 hint がそれ。この対処が実際に必要だったかどうかはわからない。たとえば 890 回のクエリで 979 個の本物を見つけたときに(※10 回のクエリで 11 個の本物が見つけられるのでした)、残りのコインは 10 対 11 であって、問題なく判別できる。残りのコインが９対９になるとか、８対８になるとかのクエリの成り行きが、N=1000,M=10 というパラメータに対して存在しているかどうかはわからない。