スナネコです。
AtCoderのpractice contestのB問題を解いたので解説を書きます。
問題ページにあるコード例を読むとわかりますが、この問題は「Q回以下の比較で、長さNの数列をソートせよ」と読み替えられます。
(N,Q)=(26,1000)のとき
コード例に書いてあるとおり、バブルソートなど、のソートアルゴリズムを実装すると通ります。
(26,100)のアルゴリズムでも当然解けるので、(26,100)が解けるなら、(26,1000)のためのコードを書く必要はありません。
(N,Q)=(5,7)のとき
本題です。
7回の質問で得られる情報7bit128パターンから、ありえる数列の並び5!=120通りを特定する必要があります。
この厳しすぎる条件から、毎回の質問は返答がほぼ半々に分かれるようにするしかないことがわかるので、何を質問すればいいか選択肢が絞れます。
1回目
(A,B)を質問し、A<Bと返ってきたとしてよいです。残りの可能性は60通りです。
2回目
質問として(A,C) か (C,D)のどちらかが考えられます。
（例えば(B,C)は数列全体を反転すれば(A,C)と同じですし、(C,E)はDとEを入れ替えれば(C,D)と同じです）
(A,C)を聞いてA<Cと返ってきた場合、ありえる数列が40通り残るので、残りの5回で判別できません。
なので(C,D)を聞きます。C<Dとしてよいです。残りの可能性は30通りです。
3回目
質問として(A,C)、(A,D)、(A,E)の3通りが考えられます。
(A,D)を聞いてA<Dと返ってきた場合、ありえる数列が25通り残るので、残り4回で判別できません。
(A,E)を聞いてA<Eと返ってきた場合、ありえる数列が20通り残るので、残り4回で判別できません。
なので(A,C)を聞きます。A<Cとしてよいです。残りの可能性は15通りです。
4回目
現時点でA<C<D、A<Bがわかっています。ABCDの並び順はABCD,ACBD,ACDBのどれかで、さらにEがどこに入るかで3×5の15通りの可能性があります。
意味のある質問と、最悪ケースを考えると
A>E 12通り
B>C 10通り
B<D 10通り
B>E 9通り
C<E 8通り
D>E 11通り
となるので、(C,E)と質問するしかないことがわかります。
4回目でC<Eになったとき
A<C<(D,E) かつ A<Bがわかっています。DEの順序を確定するのに1回、Bの位置4通りを確定するのに2回の計3回で特定できます。
4回目でC>Eになったとき
意味のある質問と、最悪ケースを考えると
A<E 4通り
B>C 4通り
B>D 5通り
となるので、(A,E) か (B,C)を質問すればよいです。どちらでもあと2回の質問で特定できますが、(B,C)の方があとが簡単です
5回目でB<Cになったとき
A<B<C<D、E<Cがわかっているので、Eがどこに入るか3通りを2回で確定できます
5回目でB>Cになったとき
(A,E)<C<(B,D) となるので、AE,BDの順序をそれぞれ2回で特定すれば良いです。
以上でこの問題が解けました。
最後の何回かの質問の部分の場合分けがちょっと大変ですが、他に選択肢はないので、頑張って場合分けを実装するしかなさそうです。
