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

「今週のお題:隣り合うと消えちゃうんです」問題解答 ( CodeIQ )

CodeIQ コードゴルフ 数学

はじめに

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

codeiq.jp

問題

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

codeiq.jp

解答

以下が提出版の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 となります。

しかしながら、これだとAが隣り合うa_{n-1}通りを含んでしまいます。よって、それを除いた
a_n=\sum_{i=0}^{n-1}(2i+1)a_i - a_{n-1} n に対する塗り分け方の適切な組み合わせの数であり、漸化式を表すものです。

コード化する際には、計算の簡略化のため、S_n=\sum_{i=0}^n(2i+1)a_i\ \ \left( S_0=1, S_n=S_{n-1}+(2n+1)a_n\right) を導入し、

  • a_n=S_{n-1}-a_{n-1}
  • S_n=S_{n-1}+(2n+1)a_n

という2数列の漸化式を与えられたnの値の回数分評価します。

ここではa_n,S_n,a_{n-1},S_{n-1}の漸化式を導いていますが、これをa_{n+1},S_{n+1},a_n,S_nの漸化式に書き換えれば、コードの構成の所で挙げた漸化式になります。

おわりに

絵でもつけた方が分かり易いのでしょうが、ご勘弁を。
ところで、挑戦者の中から抽選で、出題者増井さんの本「プログラマ脳を鍛える数学パズル」がプレゼントされるそうです。当たると嬉しいですね。