Guess Them All(数当て) - joi2011-day2 解説

筆者: qnighy

1からNの順列に対して「ブローのないヒット＆ブロー」を行った結果によってそれを推測する数当てである。

部分点解法

省略。next_permutationで10点取れる。

基本的な戦略は、二分探索である。

仮に、現在ある1つの数Aのある位置が分かっているとする。

すると、どの位置についても、「絶対にその位置にない数」を1つ作ることができる。

そこで、別の数Xについて、その位置がPより前か後かを調べたい。そこで

を置くことにより、結果が0か1かでその前後が判定できる。これを繰り返せば全ての数についてceil(log(n))回で答えを得ることができる。

上記の解法では、最初に1つの数が判明していることを前提としている。ではこのことについて考えてみよう。

最初に、前半を1、後半を2にした予測を実行してみることにする。すると0,1,2のいずれかが返ることがわかる。

0が返るとき、1は後半に、2は前半にあることがわかるので、「前半を1、後半を2にした列」は「絶対にその位置にない数」の条件を満たす。
2が返るとき、1は前半に、2は後半にあることがわかるので、「前半を2、後半を1にした列」は「絶対にその位置にない数」の条件を満たす。
1が返るとき、1,2のいずれも前半にあるか、いずれも後半にあるかのどちらかである。このときは、2,3について同様に繰り返す。2,3についてもやはり1が返った場合は、3,4について実行する。前半または後半には高々n/2個程度しか入らないので、この方法はいつか終了する。

この手順が終了したとき、通常の二部探索を実行するための準備が整う。また、この手順によって調べられた数はそれぞれ範囲を半分に絞ることができているので、二部探索に必要なクエリの回数も各ceil(log(n))回以下に抑えられる。

最後の数(n)については調べなくてもわかるので、ceil(log(n))回のクエリのあとに正解がわかるので、最後に出力して終了すれば、ceil(log(n))(n-1)+1回以下のクエリで終了する。よってこれによって満点を得ることができる。

この手法ではn=1のときがコーナーケースとなるので注意すること。

また、n回かけて最初の1つを判定して、判明した分を二部探索の対象から除外することで答えを得るなどの方法もある。