はじめに

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

問題

問題については、CodeIQ Magazineの、以下の記事に載っています。

解答

以下が提出版のgolf解、Ruby(39)です。計算量的にもΟ(n)で速いです。

a=s=1
11.times{|i|s+=(2*i+3)*a=s-a}
p a

解説

コードの構成

ちょっとコードを見易くしてみます。と言ってもあまり変わりませんが。

a=s=1
11.times{|i|
  a=s-a
  s+=(2*i+3)*a
}
puts a

これは実は、2つの数列の漸化式を11回分回すという次の計算をそのままコード化したものなのですね。

$a_0=S_0=1$
$a_{n+1}=S_n-a_n$
$S_{n+1}=S_n+(2n+3)a_{n+1}$

という事で、実はとても素直な解なのです。

詳細

提出したコードのコメントを使い回し、もとい再掲します。

色の数 $n$ に対する塗り分け方を $a_n$ とします。そして、 $2n$ 箇所のマスの左端の色をAとし、もう1箇所のAのマスに着目します。

もし、もう1箇所の両隣が異なる色の場合 ( 端で隣がない場合含む ) 、2箇所のAを取り除いた $2(n-1)$ マスも「隣り合うマスが同じ色にならない」という条件を満たします。そのため、Aの箇所毎に塗り方は $a_{n-1}$ 通りです。また、Aを配置できるのは $2n-1$ 箇所ですので、計 $(2n-1)a_{n-1}$ 通りです。

次に、Aの両隣が同じ色、その更に両隣が異なる色の場合 ( 同じく隣がない場合含む )、 2箇所のA、Aの両隣の2マスを取り除いた $2(n-2)$ マスも同じく条件を満たします。このケースは、計 $(2n-3)a_{n-2}$ 通りです。

…このように次々、Aを挟んで同じ色を配置するマスを増やしていくと、 $(2n-5)a_{n-3}, (2n-7)a_{n-4}, ..., 3a_1, 1$ という組み合わせの数が浮かび上がります。便宜的に $a_0=1$ とすると、これは $(2i+1)a_i\ \ \left(0\leq i\leq n-1\right)$ と一般化でき、ここまでの合計は $\sum_{i=0}^{n-1}(2i+1)a_i$ となります。