「今週のお題：スタートメニューのタイル」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
これ暫くの間方針がたたず、結構あせりました。
codeiq.jp
問題
指定のサイズの長方形のエリアに、タイル ( 横×縦が、1×1, 2×2, 4×2, 4×4 の4種類 ) を敷き詰める方法が何通りか数えるものです。
エリアの横・縦はカンマ区切り1行で入力より与えられます。
なお、エリアの最大サイズは10×10と分かっています。
解説
方針
たとえ10×10とたった100マスのエリアであっても、1通りずつ列挙すると膨大な手間がかかります。なので、何かしら帰納的に ( 漸化式として ) 処理する方法を考えなければ、制限時間以内に解くことはできません。また、漸化式をたてるにしても、重複して数えあげることがないように整理しなければなりません。ここらへん、良い方法が暫く思いつきませんでした。
で、締め切り間近でようやっと気づいたのが、
- タイルを上からラインで外していく方法は一意
- 空きエリアの縁の上部の形で場合分けすれば、縦のサイズを元に漸化式がたつ
ということです。
まず 1 について。
例えば、下の図のようにタイルを配置した場合、一番上のラインからはがしていくと、全部で6段分に分けられることが分かります。逆に、この分かれた段を上から順に ( 左右の順も合わせて ) 敷き詰める方法も1通りに定まります。なお、6段というのはエリアの縦のサイズ6とたまたま一致していますが、縦のサイズが大きいタイルを敷き詰めた場合は必ずしも一致するとは限りません。
続いて 2 について。 このように、ライン毎にはがしていくとすると、残ったエリアの上部の凸凹は最大でも3マス差に収まります。
すなわち、横10マスのエリアを考える場合であっても、ざっくり310乗通りで形状の違いが収まることになり、形状毎の場合の数 ( 凸凹を除いた縦のサイズに応じたタイルの配置の仕方の数 ) 同士で漸化式を組むことができることが分かります。
実装
以上を元にRubyで実装しました。詳細はソース中のコメントを参考にどうぞ。
横10マスのエリアの場合、上部の凸凹の形状は最大310通りなのですが、全部の形状が現れる訳ではありませんし、左右の対称性を活かして処理を減らしたいという考えもあります。そこで、各形状毎に最上部にどのようなタイルの配置がありえるかを調べ、はがすと次にどのような形状になるか、次の形状毎に何通りの配置があるのか、凸凹でない部分の縦のマスがどれだけ目減りするかを必要分だけ調べて漸化式の係数を保持しておきます。
なお、漸化式はざっくりと次のようになります。
- $f_{i}(n)=\sum_{(c,j,d)\in C_{i}}^{}c\times f_{j}(n-d)\ \ ( 添え字i,jは形状に対応した識別子、C_{i}は漸化式情報集合、nは凸凹を除いた縦のサイズ )$
