「クロッシング・ワード」問題解答 ( CodeIQ )

CodeIQ 数学

CodeIQというところでプログラミング問題「クロッシング・ワード」に解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 標準入力$n\,( n\le 10^8 )$に対して、縦3マス横$n$マスの領域に「クロスワード」の流儀に沿って任意の個数の黒マスを配置する方法が何通りあるかを $F(n)$ とするとき、$F(n)$を1000000で割った余りを出力する
    ※全く配置しない方法も含む
  • クロスワードでの黒マスを配置するルールは次の通り
    • どの黒マスも、縦横に隣接させない
    • 全ての白マスが縦または横で連結されている ( 黒マスによって盤面が分断されない )

N.G.な配置としては、問題にあったような次の例が挙げられます。

https://codeiq.jp//sites/default/files/answer_ready/2841/2.png

O.K.な配置の例としては、これまた問題にあった次の図が挙げられます。すなわち $F(2)=11$となります。

https://codeiq.jp//sites/default/files/answer_ready/2841/3.png

解説

不真面目に解説

今回、次のRuby(94)を提出しました。

n=eval *$<;t=x=2;y=3;3.upto(n<(z=n<2?4:11)?n:(n-z)%31e5+z){x,y,z=y,z,(z*3+x*2-t=-t)%10**6};p z

なんでかは良く分かりませんが、$F(n)$に関しては、

  • $n\ge 2$ において漸化式 $F(n+3)=3F(n+2)+2F(n)-2(-1)^{n-1}$ が成立し、
  • $n\ge 11$ 以降、$mod\,10^6$ においては、周期310万 ( 本当は周期387,500 ) で繰り返す

という性質があるからです。つまり、$F(1)=4$ 以外では、周期の範囲内で漸化式を素直に回す実装です。

これで 1-tweetable でありながら$O(1)$ですね! ( 無理やり )

真面目に解説

とはいえ「なんでかは良く分かりませんが」で済ませるのは流石にアレなので。

まずは、先頭列の配置によって4種類に場合分けします。$a_n$～$d_n$はそれぞれの配置に応じたパターン数です ( なお$b_n$に該当する配置に関しては、上下反転した分 2倍してカウントします )

f:id:ange1:20170406215642p:plain

といいつつも、$c_n,\,d_n$ に該当する配置では次の列を全部白マスにせざるを得ませんから、結局$a$として表すことになります。つまり、実質$a_n,\,b_n$の2種類が残ります。

f:id:ange1:20170406215656p:plain

なので、$a_n,\,b_n$ それぞれで漸化式を探ります。まずは$a_n$に該当する配置 ( 例によって上下反転のパターンがあるところは 2倍しています )

f:id:ange1:20170406215709p:plain

続いて $b_n$に該当する配置

f:id:ange1:20170406215718p:plain

ここまで整理すると次の通りです。

  • $F(n)=a_n+2b_n+c_n+d_n$ 特に $n\ge 2$ において $F(n)=a_n+2b_n+2a_{n-1}$
  • $n\ge 3$ において $a_n = a_{n-1}+2b_{n-1}+2a_{n-2}+2b_{n-2}$
  • $n\ge 3$ において $b_n = a_{n-1}+b_{n-1}+a_{n-2}$

パターンの列挙は割愛しますが、初期値として、

  • $a_1=1,\,b_1=1,\,a_2=5,\,b_2=2$

…さて。2種類の数列による連立した漸化式です。が、これも1種類の数列を扱うときと同じように行列で表すことができます。すなわち、

$$ \begin{pmatrix} a_n \\ b_n \\ a_{n-1} \\ b_{n-1} \\ \end{pmatrix}= \begin{pmatrix} 1 & 2 & 2 & 2 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix} \begin{pmatrix} a_{n-1} \\ b_{n-1} \\ a_{n-2} \\ b_{n-2} \\ \end{pmatrix} $$

$a,\,b$それぞれの項を交互にかみ合わせるのがミソです。なお、$a_0,\,b_0$ まで値を拡張して ( この値それ自身に意味はない )、次のようにまとめることができます。
※$F(1)$だけは、どうしてもまとめきれないため、別扱いになります

$$ \begin{pmatrix} a_n \\ b_n \\ a_{n-1} \\ b_{n-1} \\ \end{pmatrix}= \begin{pmatrix} 1 & 2 & 2 & 2 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix}^{n-1} \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \\ \end{pmatrix}\,\,( n\ge 1 )\\ F(n)=\begin{pmatrix} 1 & 2 & 2 & 0 \end{pmatrix} \begin{pmatrix} a_n \\ b_n \\ a_{n-1} \\ b_{n-1} \\ \end{pmatrix}=\begin{pmatrix} 1 & 2 & 2 & 0 \end{pmatrix} \begin{pmatrix} 1 & 2 & 2 & 2 \\ 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix}^{n-1} \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \\ \end{pmatrix}\,\,( n\ge 2 ) $$

ということで、行列のべき乗で計算できることが分かりました。今回$n$が億近く行く可能性がありますが、バイナリ法を使えば十分です。

…がこれでは実装した時の文字数が全然普通です。なんとか工夫の余地はないものでしょうか。

そうして考えてみると、今まで良く見てきたのは (数列の漸化式)→(行列表現) という変換でした。では逆もできるのではないでしょうか。

今回の係数行列の固有多項式は$\lambda^4-2\lambda^3-3\lambda^2-2\lambda-2$です。ということから、実は隣接5項間漸化式 $F(n+4)=2F(n+3)+3F(n+2)+2F(n+1)+2F(n)$ が導き出せるのです。
最終的には$mod\,10^6$での剰余を求めるので、周期としてはそれぞれ$mod\,2^6,\,mod\,5^6$で考えることになるのですが、前者は最初の数項を除けば周期2に収まってしまうため、全体としては後者の周期387,500が支配的になります。

残念ながら、この固有多項式の根は、$mod\,10^6$でも綺麗に求めることはできません。しかし、唯一 -1 だけは整数解がありますから、これを利用すると、

  • $F(n+3)=3F(n+2)+2F(n)-2(-1)^{n-1}$

と、結局、非斉次ながら隣接4項間の漸化式を導くことができます。
※余談ながら、この固有値 -1 を利用して、行列計算をする場合でも、行列サイズを4×4から3×3に落とすこともできます。

終わりに

今回なかなか難解でした。が、結局は線形代数の強力さを改めて実感する問題でした。
え? 素直にバイナリ法で実装しろよ? そこはまあ、その。