CodeIQ 挑戦の記録 : 第79回「今週のアルゴリズム：本の読み方は何通り？」

CodeIQというサイトで問題に挑戦した記録です。

第79回「今週のアルゴリズム：本の読み方は何通り？」

問題文は「正解者発表」ページを参照下さい。
問題文を要約すると、

• 標準入力より本のページ数nと日数mが与えられる。
• この本をm日以内で全て読む時、必ず前日よりも少ないページ数で読むものとすると、 何日目に何ページ読むパターンが何通りできるか、パターンの総数を解答する。

考え方

メモ化再帰を用い、残りページ数、前日のページ数、残り日数を引数として、可能な全てのパターンを試し、総数を数える。
なお、今回はJavaで解答を提出したが、3次元配列を用いたメモ化ではメモ化の効果が少なく、Rubyでは制限時間に間に合わなかった。

参考に同じアルゴリズムで書いた下記の言語で実行時間を計測した結果が下記の通り。
（Java,C++は3次元配列だが、Rubyは3重のハッシュで実装。小さい入力では正答がでる）

言語	version	実行環境	実行時間
Java	sun-jdk-8u25	実行くん	約0.4秒
C++	gcc-4.7.2	実行くん	約0.3秒
Ruby	ruby 2.0.0p645	ローカル	1分以上経過しても出力せず中止

提出したコードは下記