「今週のお題：上から順に処理する書類」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 入力 m,n ( $ 0 \lt n \lt m \lt 14 ) に対し、以下の場合の数を出力する
- 1～m番の書類を小さい番号順に机に積む事務員と、積まれた書類を上から処理する ( 同時に取り去る ) 上司がいる
- 上司が処理した書類が丁度 n番だった時に、それまで処理した書類の番号の順番が何通りあるか
解説
一つ例を挙げて考えてみます。例えば$m=7,\,n=4$としましょう。
そうすると、処理する書類の番号は$n=4$が丁度壁になっていることが分かります。すなわち、4番より大きい書類に手をつけたあと、4番より小さい書類に手をつけることができません。
つまり、処理としては、(1～3番を処理)→(5～7番を処理)→(4番を処理)となる訳です。
※ただし、積み残しやまだ積まれてない書類がある、つまり全てを処理していない可能性があることには注意
では、まず1～3番の処理です。ここで、「積む」を右向きの移動、「処理する」を上向きの移動として格子上の移動と捉えると、次の図のように対角線を超えない4×4の移動に置き換えることができます。
4を積んだ後は、もはや積み残した書類 ( 図の右側の例では2番 ) は処理できなくなりますが、ダミーの移動を入れると、結局は左下から右上までの移動と1対1に対応します。
この場合の数は、というと、皆さん大好きカタラン数の4番目$C_4$に他なりません。これにより一般の場合、n未満の書類の処理はカタラン数$C_n$で計算できることが分かります。
※カタラン数については、Wikipediaのカタラン数のページ等をご覧ください。
続いて、5～7番と、それと最後の4番の処理です。
やはりこれも格子上の移動と見ることができる訳ですが、先ほどとは状況が変わります。
それは、最初の「積む」と最後の「処理」が必ず4番であることと、必ずしも右上まで到達しなくても良い、ということです。
この図の右の例にある通り、6番,5番を処理してから4番と、7番に手を出さない場合も考えられるのです。もちろん、5番以降を積まずに、いきなり4番で終了しても構いません。
結局、灰色の● ( の直上のピンクの● ) がどれもゴールになるため、場合の数としてはカタラン数の合計、上の例では$C_0+C_1+C_2+C_3$となるのです。
一般のn,mの場合であれば、$C_0+\cdots+C_{m-n}$です。
ということで、まとめると、n未満の番号の処理に対応した$C_n$、nより大きい番号の処理に対応した$C_0+\cdots+C_{m-n}$これらの積が解となります。
以下、提出版のRuby実装です。
カタラン数の和を計算するため、カタラン数自身ではなく和の漸化式
$$
S_n = \frac{(5n-1)S_{n-1} - (4n-2)S_{n-2}}{n+1}
$$
を元に和をメモ化再帰し、カタラン数自体は和の隣接項の差として計算しています。
fs,fc,sm=
->n{ sm[n]||=((n*5-1)*fs[n-1]-(n*4-2)*fs[n-2])/(n+1) },
->n{ n<1?fs[0]:fs[n]-fs[n-1] },
[1,2]
p ->m,n{ fc[n]*fs[m-n] }[*gets.split.map(&:to_i)]
終わりに
最初、上側にまでカタラン数が現れることに気付かずWAを喰らってしまいました。気付けばカタラン数尽くしの問題だったと言えるでしょう。
