はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

問題

今回は次のような問題でした。

詳細は次のCodeIQマガジンの記事をご覧ください。 codeiq.jp

以下が提出版のRuby(111)です。…eval"N,M="+getsにした方が短いですね。今更ですが。

n,m=eval"[#{gets}]"
h={}
f=->s,u,r{r*u<1?0:h[(s*n+u)*m+r]||=(s>u ?f[s-u,u-=1,r-1]:s-u=s-1)+f[s,u,r]}
p f[n,n,m]

さて、方針としては、漸化式を見つけ出し、それを元にメモ化再帰で実装する、というものです。

ページ数合計s、残りr日、次に読めるページ数上限u ( 要は前日読んだページ数-1 ) で何通りの読み方があるかを表す$f(s,u,r)$を考えると、次の漸化式が成立することが分かります。

$$ f(s,u,r)=\left\{ \begin{array}{ll} f(s-u,u-1,r-1)+f(s,u-1,r) & ( s\gt u ) \\ 1+f(s,s-1,r) & ( s\leq u ) \\ \end{array}\right. $$

なお、上のケースに現れる2項は、取り敢えず上限一杯読んで次の日に移るか、保留するかに。下のケースの2項は、当日読み切ってしまうか、読み切らない程度に読むかに対応しています。

そして終端としては、

$$ f(s,u,r)=0\,\,\,\,\,( r=0\,\,or\,\,u=0 ) $$

なので、これらを実装します。答えは、初日読める上限は総ページ数 n に等しいので f(n,n,m)によって計算できます。

なお、メモする時のハッシュのキーは、s,r,uの範囲を考え、n,mを交え衝突しない値を適当に計算して使っています。

メモ化再帰、便利なんですが、もっと数学的に追及する余地があるのではないか…と思ってしまいますね。どうなんでしょうか。