CodeIQ MAGAZINECodeIQ MAGAZINE

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

2015.12.18 Category:CodeIQ問題解説・リーダーボード Tag: , ,

  • 73
  • このエントリーをはてなブックマークに追加
結城さんアイコン_300_300

こんにちは、結城浩です。

一年ぶりにCodeIQでアルゴリズムの問題を出題しました。

たくさんの挑戦者に楽しんでいただいた、結城浩の「マヨイドーロ問題」の解説をお送りします。
by 結城浩

はじめに

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

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

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

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

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

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

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

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

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

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

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

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

出題の方針

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

シミュレートする楽しみ

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

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

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

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

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

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

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

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

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

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

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

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

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

解答言語の分布

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

言語名 正解数
Ruby 204
Python 80
Java8 79
Java7 50
Python 3 48
Haskell 33
C 31
Perl 28
C++ 21
C++11 18
PHP 17
C# 16
Scala 13
Go 8
Node.js 7
Scheme (guile) 4
VB.NET 4
F# 3
C99 strict 3
Clojure 3
R 2
Bash 2
D (dmd) 2
Erlang 1
PARI/GP 1
Brainf**k 1
Common Lisp (clisp) 1
Nemerle 1
Tcl 1
Objective-C 1

みなさんの解答

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

最後に

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

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

それではまた!

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

CodeIQ運営事務局より

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

  • 73
  • このエントリーをはてなブックマークに追加

■この記事を書いた人

avatar

結城浩

書籍執筆者。著書は『数学ガール』『暗号技術入門 第3版 秘密の国のアリス』『プログラマの数学』『Java言語プログラミングレッスン』『Java言語で学ぶデザインパターン入門』など多数。2014年度日本数学会出版賞受賞。

■関連記事

【謎解きプログラム】乱数で発生する数値は?【組み合わせ】解答と解説... 【謎解きプログラム】乱数で発生する数値は?【組み合わせ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...
第134回「今週のアルゴリズム:幅優先の二分木を深さ優先探索」正解者発表... 「今週のアルゴリズム」とは 「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。 第134回は「今週のアルゴリズム:幅優先の二分木を深さ優先探索」の...
「放物線とマス目の関係」問題の解答と解説... table.nabe{ margin-left:30px; } .nabefloat{ float:right; } table.nabe td, table.nabe th{ padding:3px; } table.nabe th{ ...
【謎解きプログラム】データをバイナリで見てみよう【バイナリ】解答と解説... 【謎解きプログラム】データをバイナリで見てみよう【バイナリ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「...
第133回「今週のアルゴリズム:ホワイトデーのお返しの個数」正解者発表... 「今週のアルゴリズム」とは 「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。 第133回は「今週のアルゴリズム:ホワイトデーのお返しの個数」の問...
【謎解きプログラム】データベースを扱ってみよう【SQLite】解答と解説... 【謎解きプログラム】データベースを扱ってみよう【SQLite】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ