　一般に $2$ 行 $n$ 列のマス目を塗り分けることを考える．以下，$x$ 行 $y$ 列のマス目が黒で塗られていることを $(x,y)=B$，白で塗られていることを $(x,y)=W$ と表す．\
　問題文の条件を満たす塗り分け方であって，$(1,1)=(2,1)=W$ である塗り分け方の数，$(1,1)=W,(2,1)=B$ である塗り分け方の数，$(1,1)=(2,1)=B$ である塗り分け方の数をそれぞれ $a_n,b_n,c_n$ とする．

　$(1,1)=(2,1)=W$ であるとき，次のいずれかが成り立つ．ただし，$n\geq 4$ としている．
$$\begin{cases}
(1,2)=(2,2)=W\\\\
(1,2)=(2,2)=(1,3)=(2,3)=B,(1,4)=(2,4)=W
\end{cases}$$
前者の場合，残りのマス目の塗り分け方は $a_{n-1}$ 通り，後者の場合は $a_{n-3}$ 通りだけある．\
　$(1,1)=W,(2,1)=B$ であるとき，次のいずれかが成り立つ．ただし，$n\geq 3$ としている．
$$\begin{cases}
(1,2)=W,\quad (2,2)=B\\\\
(1,2)=(2,2)=(1,3)=B,\quad (2,3)=W
\end{cases}$$
前者の場合，残りのマス目の塗り分け方は $b_{n-1}$ 通り，後者の場合は $b_{n-2}$ 通りだけある．\
　$(1,1)=(2,1)=B$ であるとき，次が成り立つ．ただし，$n\geq 2$ としている．
$$(1,2)=(2,2)=W$$
したがって残りのマス目の塗り分け方は $a_{n-1}$ 通りだけある．

以上より，$n\geq 1$ に対して次の漸化式が成り立つ．
$$\begin{cases}
a_{n+3}=a_{n+2}+a_n\\\\
b_{n+2}=b_{n+1}+b_n\\\\
c_{n+1}=a_n
\end{cases}$$
これと $a_1=1, ~ a _2=2, ~ a_3=2, ~ b_2=1, ~ b_3=2$ ( $b_1=0$ であるが，例外的に $b_3 = 2$ となることに注意せよ) より順次計算していくと
$$a _ {10}=32, \quad b _ {10}=55, \quad c _ {10}=22$$
を得るので，求めたい値は $a _ {10}+2b _ {10}+c _ {10}=\bf164$ である．
公式解説
https://onlinemathcontest.com/contests/omc234/editorial/11129
　以下，黒を $B$，白を $W$ などと表している部分が何か所かある．\
　まず $2×10$ のマスの角が黒であるとしよう．この場合，考えられる塗り分け方は（上下反転を除いて）次のいずれかである．

$$\begin{array}{|c|c|c}
    \hline
    B & B & \cdots \\\\
    \hline
    W & ＊ & \cdots\\\\
    \hline
\end{array} \\\\$$

$$\begin{array}{|c|c|c}
    \hline
    B & W & \cdots \\\\
    \hline
    B & W & \cdots\\\\
    \hline
\end{array} \\\\$$

　次に $2×10$ のマスの角以外が黒であるとしよう．この場合，考えられる塗り分け方は（上下反転を除いて）次のいずれかである．

$$\begin{array}{c|c|c|c|c}
    \hline
    \cdots & B & B & B & \cdots \\\\
    \hline
    \cdots & ＊ & W & ＊ & \cdots\\\\
    \hline
\end{array} \\\\$$

$$\begin{array}{c|c|c|c|c}
    \hline
    \cdots & B & B & W & \cdots \\\\
    \hline
    \cdots & W & B & B & \cdots\\\\
    \hline
\end{array} \\\\$$

$$\begin{array}{c|c|c|c|c|c}
    \hline
    \cdots & W & B & B & W & \cdots \\\\
    \hline
    \cdots & W & B & B & W & \cdots\\\\
    \hline
\end{array} \\\\$$

---

　以上の考察より，もし角が

$$\begin{array}{|c|c|c}
    \hline
    B & B & \cdots \\\\
    \hline
    W & ＊ & \cdots\\\\
    \hline
\end{array} \\\\$$

で始まれば，そのあと黒で塗られる領域は，途切れることなく右端まで続く．\
　一方，もし角が

$$\begin{array}{|c|c|c}
    \hline
    B & W & \cdots \\\\
    \hline
    B & W & \cdots\\\\
    \hline
\end{array} \\\\$$

$$\begin{array}{|c|c}
    \hline
    W &  \cdots \\\\
    \hline
    W &  \cdots\\\\
    \hline
\end{array} \\\\$$

のいずれかで始まれば，右端もこれらを左右反転させた形となる．\
　あとはそれぞれの場合について，何通りあるか数えればよい．

---

(i)　左端，右端ともに"黒白"である場合\
　$2$ ～ $9$ 列目のうち，$2$ マスとも黒で塗りつぶされる列があれば，その両隣の列は黒と白が $1$ マスずつである．黒で塗りつぶされる列が $k$ 列あるとすれば，そのような塗り方は ${}\_{9-k}\mathrm{C}\_{k}$ 通りである．よって
$$2×({}\_{9}\mathrm{C}\_{0}+{}\_{8}\mathrm{C}\_{1}+{}\_{7}\mathrm{C}\_{2}+{}\_{6}\mathrm{C}\_{3}+{}\_{5}\mathrm{C}\_{4})=110$$

(ii)　左端，右端ともに"黒黒"である場合\
　$3$ ～ $8$ 列目のうち，$2$ 行 $2$ 列を黒く塗りつぶされた箇所がいくつあるかで場合分けすればよい．このような塗り方は $9$ 通りである．\
※ 地道に数えてもよいが，計算で求めるなら，例えば $1+{}\_{5}\mathrm{C}\_{1}+{}\_{3}\mathrm{C}\_{2}$ である．それぞれの項は，$2$ 行 $2$ 列の黒が $0,1,2$ 個の場合をそれぞれ表している．

(iii)　左端，右端ともに"白白"である場合\
　$2$ ～ $9$ 列目のうち，$2$ 行 $2$ 列を黒く塗りつぶされた箇所がいくつあるかで場合分けすればよい．このような塗り方は $19$ 通りである．\
※ $1+{}\_{7}\mathrm{C}\_{1}+{}\_{5}\mathrm{C}\_{2}+{}\_{3}\mathrm{C}\_{3}$

(iv)　左端，右端の一方が"黒黒"，他方が"白白"である場合\
　左端が"黒黒"とすれば，$3$ ～ $9$ 列目のうち，$2$ 行 $2$ 列を黒く塗りつぶされた箇所がいくつあるかで場合分けすればよい．このような塗り方は $13$ 通りである．左端が"白白"の場合もあり得るので $13×2=26$ 通り．\
※ $2×(1+{}\_{6}\mathrm{C}\_{1}+{}\_{4}\mathrm{C}\_{2})$
動的計画法を使わない方法
https://onlinemathcontest.com/contests/omc234/editorial/11129/706
　$2\times 10$ のマス目があり，各マスを黒または白で塗ります．次の条件を満たすマスを**良いマス**と呼びます．
- そのマスと辺を共有して隣接しているマスのうち黒，白で塗られたものの数をそれぞれ $B,W$ とすると，$B\geq W\geq1$ が成り立つ．

黒で塗られたマスが全て良いマスであるような塗り方は何通りありますか？\
　ただし，回転や反転で一致するものは区別し，全て白または全て黒で塗ってもよいものとします．