ガジェット通信

見たことのないものを見に行こう

結城浩の「マヨイドーロ問題」解説

DATE:
  • ガジェット通信を≫

はじめに

結城が今回出題した「マヨイドーロ問題」には、二週間のあいだに何と713人ものみなさんに挑戦していただきました。ありがとうございます。

結城浩の「マヨイドーロ問題」
挑戦期間:2015年12月3日〜12月17日
挑戦済み:713人

結城浩の「マヨイドーロ問題」

以下では、この問題のかんたんな解説をお届けします。

出題編PDF(問題はこちらから)

今回の「マヨイドーロ問題」では、問題に挑戦しようとした方には、以下の「出題編PDF」が提示されました。

出題編PDF

これから自力で挑戦したいという方は、上の「出題編PDF」をまずお読みください。

解説編PDF(解答と解説はこちらから)

今回の「マヨイドーロ問題」で正解した方(すべてのテストケースにPASSした方)には、以下の「解説編PDF」が提示されました。

解説編PDF

上のPDFには、解答と詳細な解説がありますので、詳しく読みたい方はこちらをご覧ください。

以下ではこの「解説編PDF」に書き切れなかった情報と、みなさんの解答に関する情報をお送りします。

出題の方針

今回の「マヨイドーロ問題」では「多段階に楽しめる問題」を目指しました。

シミュレートする楽しみ

まず、問題文を読んで内容を理解したなら、マヨイドーロの中を動き回るようすをシミュレートすることができます。プログラミングの楽しみですね。

マヨイで直進するか、反転するかを選択する。
与えられた反転数の上限Nに至るまで進む。
そして出口Yから出る場合をカウントする。

これによって、小さなNについては容易にカウントすることができるでしょう。しかし、このままでは大きなNに対処することができません。

数学的構造を調べる楽しみ

また、数学的構造を調査する楽しみがあります。「Nに対応したPを求める」というのは、N=1,2,3,… に対応する「数列を作り出す問題」と見なすことができますから、漸化式を考えて、それを解くということになります。

漸化式を導くことができてから、今回の中心主題である「フィボナッチ数列」を思い出せるかどうかは、解答者の知識ということになります。

実装上の楽しみ(多倍長計算)

実装上にも壁があります。非常に大きなPが登場してしまうので、多倍長の計算が必要になってしまうからです。

Rubyのように最初から多倍長の計算ができるようになっていたり、JavaのようにライブラリとしてBigIntegerが用意されていれば簡単ですが、そうでない言語ではその部分を実装する必要が生じます。

といっても、多倍長計算すべてを実装する必要はなくて、加算と印字機能さえ用意できれば何とかなるでしょう。実際、文字列を使って多倍長計算を実装した方は何名かいらっしゃいました。

実装上の楽しみ(高速化)

実装上のもう一つの壁は、実行時間です。マヨイドーロの中の動きを素朴にシミュレートしていたのでは、膨大な時間が掛かってしまい、カウントすることができません。先ほど述べた「数学的構造」にたどり着かないと厳しいでしょう(不可能ではありません)。

「フィボナッチ数列」にたどり着いた場合でも、素朴に再帰呼び出しで実装すると、スタックオーバーフローを起こすことになります。また、計算時間も無駄になります。基本的な技術ですが「メモ化」が高速化に役立ちます。

解答言語の分布

みなさんの解答言語の分布を紹介します(正解数をカウント)。

言語名正解数
Ruby204
Python80
Java879
Java750
Python 348
Haskell33
C31
Perl28
C++21
C++1118
PHP17
C#16
Scala13
Go8
Node.js7
Scheme (guile)4
VB.NET4
F#3
C99 strict3
Clojure3
R2
Bash2
D (dmd)2
Erlang1
PARI/GP1
Brainf**k1
Common Lisp (clisp)1
Nemerle1
Tcl1
Objective-C1

みなさんの解答

また、みなさんの解答や「私はこう解いた」というお話は、ぜひブログなどで公開して「結城浩 @hyuki」までリプをお送りください。
以下からリンクいたします。

結城浩の「マヨイドーロ問題」解答リンク集

最後に

今回は、多数の挑戦、ありがとうございました。

これからもCodeIQでの結城浩の問題を応援してくださいね。

それではまた!

CodeIQの問題に挑戦しよう!(結城浩のWebサイト)

なお、結城はメールマガジンも発行しています。よろしければご購読くださいね。

結城メルマガ(結城浩のWebサイト)

CodeIQ運営事務局より

結城さん、ありがとうございました!
結城さんの次の問題にご期待ください!

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP