「今週のお題：予約で満席の指定席」問題解答 ( CodeIQ )

CodeIQ

はじめに

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

codeiq.jp

問題

問題は1人～6人組を列車の座席に割り当てる場合の数を求めるものですが、少々ややこしい条件でした。詳しくは次の記事をご参照ください。

codeiq.jp

ちなみに、座席の列数をnとした場合、n=12のケースの答え、2754844344633 を出力するプログラムを実装します。

解答

提出コード

以下のRubyのコードを提出しました。一応131文字で、1tweetに収まる文字数になっています。

x=[1,1]
y=[1,2]
z=[1,4]
f=->n{x[n+1]||=(0..n).inject(0){|s,i|s+(y[i]||=y[i-1]*2+y[i-2])*(z[i]||=z[i-1]*4+z[i-2])*f[n-1-i]}}
p f[12]

解説

方針

帰納的に状況を整理し、漸化式を割り出すことを考えました。

漸化式

まず、席の割り当て方は次のようになっています。

  • 1人 … 任意の空いた座席に割り当て可能
  • 2人組 … 2人掛け1列占拠、もしくは3人掛けの1列の内つながった2座席
  • 3人組 … 3人掛け1列占拠
  • 4人組 … 2人掛けの連続する2列占拠
  • 5人組 … 同じ列の2人掛け・3人掛け占拠
  • 6人組 … 3人掛けの連続する2列占拠

ここで2人掛け・3人掛け両方に影響を及ぼすのは5人組のみであり、5人組が無ければ、2人掛け・3人掛けを独立させて座席割り当てすることができます。
そのため、n列の座席に対する全体の場合の数f(n)と、5人組無しの場合の数f_{S}(n)は、「何列目に初めて5人組が割り当てられるか」で区別して考えることにより、

  • f(n)=f(n-1)+f_{S}(1)\times f(n-2)+f_{S}(2)\times f(n-3)+\cdots+f_{S}(n-2)\times f(1)+f_{S}(n-1)+f_{S}(n)

という関係があることが分かります。一部の項の対応する状況を図解すると、次のようになっています。( なお、最後の項f_{S}(n)は5人組が全くないケースの分ですね )

f:id:ange1:20151209203905p:plain

更に、仮想的にf(-1)=f(0)=f_{S}(0)=1と定めれば、

  • f(n)=\sum_{i=0}^{n}f_{S}(i)f(n-1-i)

と一つの式にまとまります。

次に、f_{S}(n) ですが、これは2人掛け・3人掛けを独立させて考えることができますので、それぞれに対応する座席割り当て f_{2}(n), f_{3}(n) により、次のように表すことができます。

  • f_{S}(n)=f_{2}(n)\times f_{3}(n)

さて、2人掛け・3人掛けについては、2列をまとめて独占する4人組・6人組を除けば各列は独立で、

  • 2人掛けならば、2人組、1人×2 の2通り
  • 3人掛けならば、3人組、2人組+1人(2通り)、1人×3の4通り

であるため、次の漸化式が成立します。

  • f_{2}(n)=2\times f_{2}(n-1)+f_{2}(n-2)
  • f_{3}(n)=4\times f_{3}(n-1)+f_{3}(n-2)

なぜかというと、次の図 ( 3人掛けの状況、2人掛けでもほぼ同様 ) のように、状況を2つに分けて考えられるからですね。

f:id:ange1:20151209201255p:plain

加えて、f_{S}(n)との整合性も考えると、初期値 ( 仮想的な0項目含む ) は次の通りです。

  • f_{2}(0)=1, f_{2}(1)=2
  • f_{3}(0)=1, f_{3}(1)=4

以上により条件が出揃いました。

実装

漸化式が出揃っているので、それぞれの数列に対してメモ化再帰で関数を実装する方法が考えられます。 が、ここで、単純な積である f_{S}(n) はともかく、f_{2}(n),f_{3}(n) に関しても0から順に飛びなく評価するのであれば、インライン化できることに気付きます。

どういうことかというと、例えばf_{2}(n)の実装は単独であれば、次のようなものが考えられるのですが…。

y=[1,2]
f2=->n{y[n]||=f2[n-1]*2+f2[n-2]}

ここで 0 から飛びなく評価するのであれば、f2[n] を呼び出した時には既に f2[n-1],f2[n-2] の値はメモされていて、y へのアクセスで代替できるからです。

そのため、f(n),f_{2}(n),f_{3}(n) の計算済み結果を保存するメモ用配列 x,y,z に初期値を与えれば、関数本体は1つで済ますことができます。 なお、f(n) の引数が最小で -1 となることに対応するため、x は添え字を1つずらして扱います。

おまけ

私は131文字で止まってしまいましたが、@g_m_k さんによるともっと短くすることができるようです。

どんな方法か、興味深いですね。

終わりに

今回は自動採点ではないということで、フィードバックが戻ってくるまでちょっとドキドキしていました。
頂いたコメントで「コメントがないと ( コードを ) 読むのがつらいですが」とあって、少し喜んでしまったのは天邪鬼でしょうか。