お久しぶりの記事です。暇なので競プロの問題の解説をしてみることにしました。のんびり解説記事を書きたいので自分が解けた中で難しい問題や自分の解法が他の解説と違ったものに絞り解説しようと思います。
初めての解説記事はJOI春合宿より「数当て」(難易度 9) です。
問題ページ
https://atcoder.jp/contests/joisc2011/tasks/joisc2011_guess
問題概要
インタラクティブ問題です。$1$ から $N$ を並び替えた順列を予想して、合致する箇所の個数が知らされるのでその順列を当てようという問題です。予想できるのは合計$L$回までです。
制約(満点)
- $1\le N\le100$
- $L=700$
考察
以下、特に断りのない限り $0$-indexed とします。
満点制約ではだいたい $N$ 回の操作を $7$ ステップ行うことが出来ると考えると、この $7$ というのは $\log_2(100)\approx 6.64$ より、$\log(N)$ から来ているものだと推察できます。
このような形の問題だと二分探索出来ると嬉しいですね。この問題で二分探索をどこに適用するかを考えると、ある数字がどの場所にあるかを特定するため二分探索で区間を狭めるといいのではないかと考えられます。
しかし、二分探索で区間を絞り込むことを考えると、調べる区間以外を知りたい数字以外のもので埋める必要がある (例えば $N=7$ として、$1$ が区間 $[0,\ 4)$ にあるか調べたいとします。このとき予想する数列を $(1,\ 1,\ 1,\ 1,\ 2,\ 2,\ 2)$ とすると、$2$ が区間 $[4,7)$ に存在したら変な値が帰ってきます) ため面倒です。どうにかしてこれを解決したいので、どこにあるか分からない数字を 1 個でもいいので確定出来ないか試みましょう。
解法
ある区間に入っていることが分かっている数字 ($k$ 個存在するとする) のうち $1$ 個のみを固定し、残りの $k-1$ 個と固定した数字で区間の半分ずつを調べる方針を取ります。
例として、答えが $(2,\ 3,\ 1,\ 4)$ と仮定して、${1,\ 2,\ 3,\ 4}$ のそれぞれの数字が前半の $2$ 箇所か後半の $2$ 箇所かどちらかにあるかを調べたいとします。このとき、後半の区間を $1$ で埋めて残りは $2,\ 3,\ 4$ の $3$ つで埋めると、
- $(2,\ 2,\ 1,\ 1)$ → $2$
- $(3,\ 3,\ 1,\ 1)$ → $2$
- $(4,\ 4,\ 1,\ 1)$ → $1$
という結果が帰ってくるはずです。これで、$2$ が帰ってきた $2,\ 3$ は前半に、そうでない $4$ は後半にあると断定できますね。残った $1$ は後半にあります。
別の例として、答えが $(2,\ 1,\ 3,\ 4)$ だとすると、
- $(2,\ 2,\ 1,\ 1)$ → $1$
- $(3,\ 3,\ 1,\ 1)$ → $0$
- $(4,\ 4,\ 1,\ 1)$ → $0$
という結果となります。今度は、$1$ が帰ってきた $2$ は前半、$0$ が帰ってきた $3,\ 4$ は後半にあるとわかります。残った$1$は前半です。
固定した $1$ が前半か後半かによって以上のどちらかの結果になるので、$3$ 回で各数字の位置が前半か後半かが特定できました。
$k$ 個ある区間の各数字を前後半どちらであるか振り分けるためには $k-1$ 回必要なので、各ステップにつき $N$ 回を超えない回数で数字の存在する区間を半分に絞り込めることが分かります。よって、これで $N=100$ のデータであっても $700$ 回以内に順列を特定することが出来ると分かりました。
実装
ある区間に入りうる数の配列をセグ木のような形で持つことにしました。$N$ が2べきでない場合はちょうど半分とはせず、$N$ 以下で最大の2べきの個数ある区間と残りの区間で分けるようにしました (例: $11$ 個の区間は $8,\ 3$ 個の区間に分割)。図のような形です。
以下、C#による実装。非本質的な部分は省いています。
実装を展開する
public static void Solve(Scanner cin)
{
int n = cin.ReadInt();
int seg = MaxNum(n);
var list = new List<List<int>>();
list.Add(Enumerable.Range(1, n).ToList());
while (seg > 0)
{
var next = new List<List<int>>();
for (int i = 0; i < (n + seg - 1) / seg; i++)
{
next.Add(new List<int>());
}
for (int i = 0; i < list.Count; i++)
{
int size = list[i].Count;
int lsize = MaxNum(size);
int rsize = size - lsize;
int border = i * seg * 2 + lsize;
int p = list[i][0];
if (size == 1 || size <= seg)
{
foreach (var e in list[i])
{
next[2 * i].Add(e);
}
continue;
}
// box[i]: 帰ってきた値がiである数字
var box = new List<List<int>>();
for (int j = 0; j < 3; j++)
{
box.Add(new List<int>());
}
for (int j = 1; j < size; j++)
{
for (int k = 0; k < n; k++)
{
if (k < border) Console.WriteLine(list[i][j]);
else Console.WriteLine(p);
}
Console.Out.Flush();
int ret = cin.ReadInt();
box[ret].Add(list[i][j]);
}
// 固定した値は1が帰ってきたときと同じと考えていい
box[1].Add(p);
// 帰ってきた値が1, 2のどちらかであったとき
if (box[0].Count == 0)
{
foreach (var e in box[2])
{
next[2 * i].Add(e);
}
foreach (var e in box[1])
{
next[2 * i + 1].Add(e);
}
}
// 帰ってきた値が0, 1のどちらかであったとき
else
{
foreach (var e in box[1])
{
next[2 * i].Add(e);
}
foreach (var e in box[0])
{
next[2 * i + 1].Add(e);
}
}
}
list = next;
seg /= 2;
}
for (int i = 0; i < n; i++)
{
Console.WriteLine(list[i][0]);
}
Console.Out.Flush();
cin.ReadInt();
}
// 自身以下の2べきの数を求める
public static int MaxNum(int n)
{
int ret = 1;
while (ret < n)
{
ret *= 2;
}
ret /= 2;
return ret;
}
ACコード: https://atcoder.jp/contests/joisc2011/submissions/17678327
感想
こういう感じの頭を捻るインタラクティブは面白くてとても好きです。実装が少し面倒だったけれど……。
ちなみに公式解説や他の方の解説では $1$ の位置を最初に $100$ 回くらいかけて決めて、$1$ を区間を二分探索する際の相棒にするという解法がほとんどでした。ちなみに私の解法では $N=100$ の時でも $599$ 回目の質問で答えに辿り着ける (はず) ので、他の解法よりも割と効率がいいはず。
おまけ
インタラクティブってデバッグ面倒ですよね。ジャッジが簡単な場合は自分で実装するのも手です。ACコードにその名残が残っているので参考にしてみてください。