BlindCoder writeup (Ja)

問題概要

$ 0以上$ 2^{32}=4294967296未満の整数$ 50個の集合$ Sがサーバー上にある。

論理演算や四則演算を用いた式$ fを送ると、その式の値$ f(x)が$ xの下一桁と等しいような$ x\in Sの個数が返ってくる。

$ 1000回まで自由に$ fを送ってよい。$ Sを特定せよ。

例:

$ S=\{0,1,\ldots,49\}のとき、$ f(x)=0を送ると$ 5\ (x=0,10,20,30,40)が返ってくる

考察

$ xの下一桁は$ x\,\%\,10であり、$ -1は下一桁になりえない。よって、論理関数$ P(x)について$ fを

$ f(x)=P(x)\,?\,(x\,\%\,10)\,:\,-1

とすると、「$ Sのうち$ P(x)を満たすものの個数」を得ることができる。

ステップ 1

「$ [0,2^{32})に$ 50個含まれる」の情報を、50個の重ならない「$ [a,b)に$ 1個含まれる」の情報にする。

これは、$ Sの要素が複数個含まれる区間$ [a,b)を選んで$ \left[a,\dfrac{a+b}{2}\right)に含まれる個数を聞くことを繰り返すなどすればよい。

この方針では平均$ 71回ほどで重ならない50個の区間を得られる。

ステップ 2

ステップ 1 で得られた区間を1点へ狭めていく。

簡単のため、ステップ 1 で得られた区間の長さを$ \dfrac{2^{32}}{64}=2^{26}とする。

戦略A

区間$ [a,b)について、「$ \left[a,\dfrac{a+b}{2}\right)に含まれる個数」を聞くことで区間の長さを半分にできる。

これを全ての区間の長さが1になるまで繰り返すことで解くことができる…ように思えるが、必要なクエリは$ 26\times50=1300回となり、間に合わない。

戦略B

2つの区間へ同時にクエリを送ることを考える。

区間$ [a,b),[c,d)について、「$ \left[a,\dfrac{a+b}{2}\right)か$ \left[c,\dfrac{c+d}{2}\right)に含まれる個数」を聞くと、0か1か2が返ってくる。

0,2のとき、どちらの区間も半分にできる。つまり、戦略Aのクエリ2回分の効果がある。

1のとき、$ \left[a,\dfrac{a+b}{2}\right)に含まれるか$ \left[c,\dfrac{c+d}{2}\right)に含まれるかのどちらかであり、片方を半分にできればもう片方を半分にできる。

つまり、戦略Aのクエリ1回分の効果がある。

以上から、1回のクエリで戦略Aのクエリ1.5回分の効果が期待できる(実際は、区間が残り1つになる場合などで少し減る)。

よって、必要なクエリは$ 1300/1.5=866.66\ldots回となり、ステップ 1 の$ 71回と合わせても間に合う。