読者です 読者をやめる 読者になる 読者になる

「今週のお題:上から順に処理する書類」問題解答 ( CodeIQ )

CodeIQ

はじめに

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

codeiq.jp

問題

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

  • 入力 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の移動に置き換えることができます。

f:id:ange1:20170207224333p:plain

4を積んだ後は、もはや積み残した書類 ( 図の右側の例では2番 ) は処理できなくなりますが、ダミーの移動を入れると、結局は左下から右上までの移動と1対1に対応します。

この場合の数は、というと、皆さん大好きカタラン数の4番目$C_4$に他なりません。これにより一般の場合、n未満の書類の処理はカタラン数$C_n$で計算できることが分かります。
※カタラン数については、Wikipediaのカタラン数のページ等をご覧ください。

続いて、5~7番と、それと最後の4番の処理です。
やはりこれも格子上の移動と見ることができる訳ですが、先ほどとは状況が変わります。

それは、最初の「積む」と最後の「処理」が必ず4番であることと、必ずしも右上まで到達しなくても良い、ということです。

f:id:ange1:20170207230026p:plain

この図の右の例にある通り、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を喰らってしまいました。気付けばカタラン数尽くしの問題だったと言えるでしょう。