2009-03-04 23:17:10
Treasure Casket
二分探索
数字を入力した時に、アタリか上か下かを教えてくれます。
それのみで探索するとなると、
- A) 候補x,y,zがあり x<y<z の時に、yを入力した時の返答でx,y,zが特定できます。 これだけで特定できるのは候補が3つの時のみで、そのとき特定後アタリを得るために、最悪2回の入力を必要とします。
- B) 候補a,b,c,y,i,j,kがあり、a<b<c<y<i<j<kの時に、yを入力することで、 a/b/cかi/j/kかアタリが得られ(A)のケースに帰着します。つまり候補が7つの時に最悪3回の入力を必要とします。
以下再帰的に定義を行うと、f(n)を最悪n回の入力でアタリが判明する要素数とすると、追加する1回の検査でf(n)*2 + 1の要素で新たに判明し。
- f(n+1) = 2*f(n) + 1
- f(n+1) + 1 = 2*(f(n) + 1)
- f(n) + 1 = 2^(n - 1) * (f(1) + 1)
- A,Bからf(1) = 1, f(2) = 3, f(3) = 7なので、
- f(n) = 2^(n - 1)*2 - 1 = 2^n - 1
逆関数は、
- f(n) + 1 = 2^n
- n = log2(f(n) + 1)
となります。
さて、10から99までが答えの範囲のようなので、それを全部カバーする90個の要素ならlog2(91)=6.xxで、7回の入力が必要になります。
ヒントから得られる候補
- A) カギの数字の1桁目(2桁目)は奇数(偶数)のようだ……。
- 1桁目が偶数・奇数→候補 45個。[1-9][13579] or [1-9][02468], 9*5
- 2桁目が偶数→候補 40個。[2468][0-9], 4*10
- 2桁目が奇数→候補 50個。[13579][0-9], 5*10
- B) カギの数字の1桁目(2桁目)はx、y、zのどれかのようだ……。
- 候補 54個。([xyz][0-9]|[1-9][xyz]), 3*10+9*3-3
- (-3はxx,yy,zzの多重カウント分)
- C) カギの2桁の数字のどちらかはxのようだ……。
- 候補 18個。(x[0-9]|[1-9]x), 10+9-1
- D) カギの数字はxより大きく、yより小さいようだ……。
- 候補 (y-x+1)個。表記上と違いx,yを含むようだ。
- 候補18個の場合でもlog2(19)=4.xxつまり5回の入力を要します。ヒント複数がうまく値を制限しあい候補を減らせない限り正答に確実に行くことはできませんね。
私ならどうするか
長時間悩んだ末に最後は運になって出ない、よりは確実に出せるかどうか初期の段階で見極めたいです。
方法1
いきなり絞込み。
早期撤退型。
トライ可能回数がn
- いきなり9+2^(n-1)を入力。これより小さければわかってる範囲の中央値を入れていけばかならず正解にたどり着ける。
- 例：25を入力して小なら10～24に正解があるので(24+10)/2=17が中央値、これより小なら10～16、大なら18～24で同様に続けていく。
- n=4なら17, n=5なら25, n=6なら41で始める。
でも正解確率は低いよ。
方法2
1回ヒントを貰う。
C,Dならラッキー。違ってれば1に移行、勝算は低いけれど。
6回入力可能でいきなりヒントC,Dで31個以内に絞り込めたら、もしくは5回入力可能でDで15個以内に絞り込めたら確実に正答できます。 5回/Cだとしても最悪でも2個、たいてい1個には絞れます。
まとめ
箱からでるアイテムいらないからどーでもいい。
