「今週のお題：綺麗に並んだセミナーの座席」問題解答 ( CodeIQ )

CodeIQ コードゴルフ

はじめに

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

codeiq.jp

問題

ちょっと条件がたくさんあってややこしいです。まとめてみると、

  • 全部で n 席 ( 個々の席は区別しない ) を並べる方法が何通りかを出力する。n は標準入力として与えられる。
  • 席は、単数/複数のブロックを、縦に通じる路を挟んで配置する。横の通路は設けない。
  • 各ブロックは、横2～5席、縦2～(任意)席の長方形の配置とする。縦の席数は全ブロック共通。
  • 全体が横方向に関して対称の配置にする。

という、組み合わせ問題です。

※2015/11/5追記：記事が公開されましたので追記。あと細かいところ修正。

解答

golf解として、以下のRuby(115)を提出しました。1tweetに収めることはできますが、あまり短くはなりませんでした。

n=eval *$<
h=[a=0,1,0,1,1,2]
2.upto(n.times{h<<h[-1]+h[-2]-h[-6]}/2){|w|n%w<1&&a+=(~w&1)*h[1+w/=2]+h[w]+h[w-1]}
p a

解説

以下、提出時のコメントに追記してまとめたものです。( 1度書いておくとラクできますね )

方針

入力 n に対し、n=w\times d ( w,d\geq 2 ) と積 ( wが幅、dが奥行 ) に分解した時の配置の数は、 dに関わらず wによって一意に決まります。これを f(w) とし、f(w) を求めることを考えます。
※最終的な答えは、各分解に対する f(w) の合計で求まります。

f(w)について

f(w) については、w の偶奇によって分かれます。が、いずれにしても中央の席のブロックに対し、 対称たる左右にどのような幅で席の配置を行うか、が焦点です。

  • w が偶数の場合は、中央が幅 0,2,4 のブロックに対し、左右の幅が \frac{w}{2},\frac{w}{2}-1,\frac{w}{2}-2 席ずつ
  • w が奇数の場合は、中央が幅 3,5 のブロックに対し、左右の幅が \frac{w-1}{2}-1,\frac{w-1}{2}-2 席ずつ

というケースがあります。
※w が偶数の場合、対称軸を通路とする配置も考える必要があるのですが、それを「幅0のブロック」とみなすことで、他と同じように扱える訳です。
そのため、この左右の幅 ( kとする ) に対応する席の配置 g(k) を考えます。 左右どちらかの配置が決まればもう片方も自動的に決まるので、

f(w)=\cases{ g(w/2)+g(w/2-1)+g(w/2-2) \,\,\, ( wが偶数 ) \cr　　　　　g(w/2-1)+g(w/2-2) \,\,\, ( wが奇数 ) }

という関係が成り立ちます。ここで、/ は整数除算、すなわち小数点以下は切り捨てです。こうすることで、偶数・奇数での式の見た目がかなり似てきます。 なお、便宜上、0個の席の配置は1通り、負数の席の配置は0通りとして扱います。
※負数については、 w\geq 2 なので、-1 のみ考えれば十分です。

g(k)について

さて、ブロックは幅2～5となっているので、
g(k)=g(k-2)+g(k-3)+g(k-4)+g(k-5)
という隣接6項間漸化式が成り立ちます。 実際には項数を減らすため、
g(k)=g(k-1)+g(k-2)-g(k-6)
という隣接7項間漸化式にして使います。( 文字数節約以上の意味はありませんが )

なお、g の初期値は次のようになります。
g(-1)=0, g(0)=1, g(1)=0, g(2)=1, g(3)=1, g(4)=2

コード化

これで材料は全て出揃いました。 なお、g の添え字が -1 からなのはコード上扱いにくいので、 h(k)=g(k+1) なる h を設け、最初に十分な ( 過剰ながら ) 数の項を配列として蓄えておきます。
※hの満たす漸化式は、もちろんgと同じになります。
wの偶奇の違いは、 g(w/2)=h(w/2+1) に対する係数で調節します ( もちろん if文で分岐させても良いんですけど )。
最終的に、
f(w)=(係数)\times h(w/2+1)+h(w/2)+h(w/2-1)\,\,( 係数は w が偶数なら 1、奇数なら 0 )
となります。

という訳で、素直に組んだコードの例は以下の通りになります。冒頭のコードはこれを色々縮めたものです。
※2015/11/5追記:コードに誤植 ( ?不足 ) があったので修正。

n=gets.to_i
a=0
h=[0,1,0,1,1,2]
n.times{
  h<<h[-1]+h[-2]-h[-6]
}
2.upto(n/2){|w|
  if n%w==0
    coef=w.even? ? 1 : 0
    a+=coef*h[w/2+1]+h[w/2]+h[w/2-1]
  end
}
puts a

終わりに

最終的に漸化式の形に書いてしまえば、そこからコードに落とすのはラクなので、如何に整理して漸化式を割り出すか。そこが楽しい所ですね。
あ。速度については、いずれにせよΟ(n) なので ( というか、n が大きくなると解が発散しちゃうので )、特に頑張ってはいません。