2019年6月6日木曜日

TDPC M - 家

TDPC M - 家

部屋i,j{1,...,R}i, j \in \{1, ..., R\}と部屋の集合S{1,...,R}S \subseteq \{1, ..., R\}が与えられたとき、iiからjjへの経路でSSに含まれるすべての部屋をちょうど1回ずつ通るものの数をf(i,j,S)f(i, j, S)とする。部屋jjに隣接する部屋の集合をN(j)N(j)とするとき、ffの漸化式は

f(i,j,S)={1(S={i}={j})kSN(j)f(i,k,S{j})(i,jS)0()f(i, j, S) = \begin{cases} 1 & (S = \{i\} = \{j\})\\ \sum_{k \in S \cap N(j) }f(i, k, S \setminus\{j\}) & (i, j \in S) \\ 0 & (それ以外) \end{cases}
と書ける。さらに、aija_{ij}を部屋iiからjjへの経路の総数として行列A=(aij)ZR×RA = (a_{ij}) \in {\mathbb Z}^{R \times R}を与えるとき、aija_{ij}ffを使って

aij=S{1,...,R}f(i,j,S)a_{ij} = \sum_{S \subseteq \{1, ..., R\}} f(i, j, S)

と書ける。DPすればAAO(R32R){\mathcal O}(R^3 2^R)で求まる。

さて、ある階の部屋iiからひとつ下の階の部屋jjへの経路の総数はk=1Raikakj\sum_{k=1}^{R} a_{ik}a_{kj}で求まり、これはA2A^2iijj列に等しい。帰納的に、HH階の部屋1から1階の部屋1への経路の総数はAHA^Hの第1行第1列に等しいことがわかる。全体の計算量はO(R32R+R3logH){\mathcal O}(R^3 2^R + R^3\log H)