8つのマスがあり、それぞれのマスにAまたはBを書き込む。ただし、Bを縦にも横にも隣り合わせて書くことはできない。このとき、8つのマスすべてにAまたはBを書き込む方法は何通りあるか。Bを1つも書かない場合も含む。

1. 問題の内容

8つのマスがあり、それぞれのマスにAまたはBを書き込む。ただし、Bを縦にも横にも隣り合わせて書くことはできない。このとき、8つのマスすべてにAまたはBを書き込む方法は何通りあるか。Bを1つも書かない場合も含む。

2. 解き方の手順

この問題は、動的計画法を用いて解くことができる。

まず、各マスに対して、以下の2つの状態を定義する。

* 状態0: そのマスにAを書く

* 状態1: そのマスにBを書く

$dp[i][j]$を、$i$番目のマスまで書き込みが終わっており、最後のマス（$i$番目のマス）の状態が$j$である場合の数とする。

初期条件は、$dp[0][0] = 1$と$dp[0][1] = 1$である。

漸化式は、以下のようになる。

* $dp[i][0] = dp[i-1][0] + dp[i-1][1]$ (i番目にAを書く場合、i-1番目はAでもBでも良い)

* $dp[i][1] = dp[i-1][0]$ (i番目にBを書く場合、i-1番目はAでなければならない)

ただし、マスが縦横に並んでいるため、Bが縦横に隣り合わないように注意する必要がある。

そこで、各マスの状態を以下の様に定義する。

* 状態0: A

* 状態1: B

各マスに番号を以下のように振る

1 2 3

4 5 6

7 8

$dp[i][j]$をi番目のマスまで埋めた時にi番目のマスの状態がjである場合の数とする。

初期状態

$dp[0][0] = 1, dp[0][1] = 1$ (1番目のマス)

遷移

$dp[i][0] = dp[i-1][0] + dp[i-1][1]$ (常にAを置ける)

$dp[i][1]$は、縦横にBが並ばない場合にのみBを置ける

各マスについて、$dp[i][0]$と$dp[i][1]$を計算していく。

1: A, B ($dp[0][0] = 1, dp[0][1] = 1$)

2: AA, AB ($dp[1][0] = 2$), BA ($dp[1][1] = 1$)

3: AAA, AAB, BAA ($dp[2][0] = 3$), ABA ($dp[2][1] = 2$) (2にBを置いた場合、３にはAしか置けない)

4: AAAA, AAAB, BAAA, ABAA ($dp[3][0] = 4$), AABA, BABA, ABAB ($dp[3][1] = 3$)(１にBを置いた場合、４にはAしか置けない)

5: 7

6: 10

7: 17

8: 27

漸化式で解く場合、以下のようになる

$dp[i][j]$: i番目まで決まっていて、i番目がj (A:0, B:1)であるような場合の数

$dp[0][0] = 1$

$dp[0][1] = 1$

$dp[i][0] = dp[i-1][0] + dp[i-1][1]$

隣り合うマスの条件を考慮する必要があるため、DPで状態を管理する必要がある。

全マスをAで埋める場合も含むため、Bを1つも書かない場合も考慮する。

丁寧に場合分けして数え上げることも可能だが時間がかかる。

以下のような数え上げを行う。

Bの個数が0個：1通り (AAAAAAAA)

Bの個数が1個：8通り

Bの個数が2個：条件を満たす組み合わせを数える

Bの個数が3個：条件を満たす組み合わせを数える

...

手計算では難しい。

問題文をよく読むと、Bは縦にも横にも並べて書くことができないとある。

これはかなり厳しい制限なので、Bの個数はかなり少なくなる。

8個のマスにA, Bを書き込むことから考えると、総数は$2^8 = 256$通りある。

そこからBが縦横に隣り合うケースを除いていくことは非常に困難。

プログラムを書いて計算することを検討する。

3. 最終的な答え

41