突撃！となりの偏差値 解答

日比谷亜依斗あいとくんは、入学式早々、隣の友達に偏差値を聞いた。すると、
「当てずっぽうで言ってみてよ。正解、もっと上、もっと下、だけで答えてあげる」
と言われました。亜依斗君はどうすれば最小回数で答えに辿り着けるか考えました。
最も運が悪い場合でも確実に当てるためには、亜依斗くんは何回質問する必要があるでしょうか？

クリックして表示

ためしに、小さい方から0.1ポイント刻みに大きくしていくとしましょう。
58.6、58.7、58.8、…80.0
1ずつ増やしていくと、偏差値80だった場合215回もかかってしまいます。
日比谷生の場合逆の方が速そうですが、理論上は変わりません。非効率的ですね。
この方法を「線形探索」といいます。

続いて、58から1ポイントずつ上げていって、「より下」と言われたら0.1ポイントずつ下がっていくとしましょう。
さっきより効率がよさそうですね。
この探索方法でやると、79.1ポイントのときの32回が最多になります。
58から80まで上がるのに23回、79.9から79.1に下がるのに9回です。
線形探索を少しいじっただけなのに、かなり効率が良くなりました。

結果的に、今回最も効率が良くなるのは、ずばり「どんどん2分割していく」方法です。
この方法を「二分探索」といいます。2 minutesではなくBinaryです。ご注意を。
この方法で行くと…

• 1回目…58.6と80.0の中間である69.3を聞く。不正解の場合、範囲が58.6～69.2または69.4～80.0に絞られる。
• 2回目…1回目で絞った範囲の中間地点を聞く。前者の場合は63.9、後者では74.7となる。聞いた後の範囲は5.3に絞られる。
• 3回目…2回目で絞った範囲のさらに中間地点を聞く。範囲は2.6まで絞られる。
• 6回目…聞いた後、範囲は0.3まで絞られる。
• 7回目…聞いた後、範囲は0.1(!)にまで絞られる。
• 8回目…もし7回目で外してしまった場合、該当するのは1つしかない！つまり、それが正解。

例えば、もし友達が偏差値58.6だった場合、順に69.3、63.9、61.25、59.9、59.2、58.85、58.7、58.6の8回の質問で答えに辿り着くことができます。
これは直感で分かった方も多かったかもしれませんね！
ちなみにプログラム(Python)で書こうとするとこうなります。Pythonの説明を表示

ss = 58.6 # ここには友達の偏差値を入れる
mn = 58.6
mx = 80.0
ask = 0
i = 0

while True:
  i += 1
  ask = (mn + mx) // 2
  if ask == ss:
    break
  elif ask < ss:
    mn = ask + 0.1
  else:
    mx = ask - 0.1
print(i) # 結果が表示される
    

このコードを実行すると、最終的に何回かかったかが表示されます。
コンソール

線形探索、二分探索といった探索の実行時間は「O記法」というもので表されます。
一般に、O(n)という形があったとき、nの値が小さいほど実行速度は速くなります。
線形探索の実行時間はO(n)、二分探索の実行時間はO(log n)となります。
このあたりは3年の佐藤先輩が詳しいよ！
また、全体の平均試行回数が最小になるようにする問題の場合、全体の偏差値の分布によって二分探索を応用していくことになります。