読者です 読者をやめる 読者になる 読者になる

C Sharpens you up

http://qiita.com/yuba に移しつつあります

ちょまど問題の算数的解法を改善=14手

算数

昨日の http://cs.hatenablog.jp/entry/2014/06/18/174157 には出題者の名前からちょまど問題という名前が付いたようです。

16手というのは算数的解法で、数学的にはまだまだ先があるのですが、ともかく算数的には16手が最短かと思っていましたが、まだまだ改善の余地がありましたね。14手になります。

解法のアイディア

  1. まず3回の試行で正解の分布を知る。正解を多く含む順に上位の選択肢2つ(A,Bと名付ける)と下位の選択肢2つが決まる。
  2. 9回の試行で、問9までについて正解がAかBか下位かがわかる。下位が正解の問題は最大4問。
  3. 2択問題が最大で4問なら、それらは2回の試行で正解がわかる。
  4. 問10の答は正解の分布から差し引きでわかる。

3 + 9 + 2 = 14手。