Codeforces Global Round 13

　Dまで四完でした。

　Cでセグ木を使ったけど、imos法を使えば使わなくて良かったらしい。確かに。

　Fは惜しかった気がしたけど、コンテスト後にACするまでかなり苦労したことを考えると現実的には厳しかった。

コンテストへのリンク

コンテスト後のツイート

F. Magnets

　一応、自力AC。

　多分、公式解説と同じ方法なのですが、私が苦戦したところ（クエリ回数を減らす部分）に触れられていないので、何か勘違いしているのかもしれない。

　ここでは、ツイートしたものをまとめておきます。

　そもそものアイディアは、

・一個 vs 他全て

　をn回試すというもの。

　ただ、これだと、

・--N--NNNSSS

　のようなとき、Nのところに対しては0が返ってくるので困る。

　なので、そこをちょっと工夫して、「他全て」ではなく、「今まで試して0になったものを除く全て」を試すという方針にする。

　これは、まず、

・1 vs 他全部を投げて、

で0が返ってきたら、

・2 vs 他全部 - {1}を投げる。

これも0なら

・3 vs 他全部 - {1, 2}

……とやっていく。

　これなら、さっきの

・--N--NNNSSS

　という例で、最初のNでは0が返ってくるけれど、それ以降のN（やS）に対しては-1が返ってくるため上手くいく。

　それにより、n回のクエリで、「NかSだと確定しているもの」と「高々一個NかSがあり、他は"-"のもの」とに分けられる。後者を二分法で調べれば良い。

・NかSと確定している一個 vs 後者の半分

　というクエリを投げて、1が返ってくればその中にNやSがある。0なら、残り半分に高々一個NやSがある。

　ただ、この方針だと、n+lognの繰り上げ回数クエリが必要。さらに二回クエリを減らす必要がある。

　そのうち一回は割合簡単に減らせる。最初にn回クエリを投げたが、返り値の正負や偶奇を見ることで、最後の一回が"-"なのかNやSなのか、というのは分かる。

（具体的に書いていないのは、試行錯誤しながらコードを書いていたので、正確に理解できていないためです。逆に言えば、試行錯誤すればできるはず）

　もう一回は、先程書いた、

「後者を二分法で調べれば良い。

・NかSと確定している一個 vs 後者の半分

　というクエリを投げて、1が返ってくればその中にNやSがある。0なら、残り半分に高々一個NやSがある。」

　にヒントがあった。

　1が返ってきたときの方が情報が多い！

　なら、適当に半分を取るのではなく、

・NかSと確定している一個 vs 後者の半分のうち多い方

　というクエリを投げた方が得られる情報が多い。

　実際、そうすると、

・1が返ってくる→その中にNかSが含まれる（と情報が増えるので、最後1個残ったときそれがNかSと分かる。ので一回減る）

・0が返ってくる→「残りの方に高々一個NかSがある」（最後までこれを繰り返すと、残り一個が"-"かどうか分からないので、それも聞く必要がある。が、小さい方を取っていったので、logで収まる！）

　となる。