頂点数が \(N\)で，任意の\(i, j \) に対し 「頂点 \(i\)と頂点\(j\) の間に辺がある」 \(\iff\) 「 \(S_i\) と \(S_j\) がちょうど1文字だけ異なる」となるように辺を張った単純無向グラフ \(G\) を考えると，本問題はこのグラフ上でのハミルトン路の存在判定に帰着されます．

本稿における記号について

• \(S\) の添字は 0-indexed で扱います．
• 真と \(1\) ，偽と \(0\) をそれぞれ同一視します．
• 非負整数 \(a\) の \(2^i\) の位を \([a]_i\) で表します．
• bitwise 論理積演算を \(\mathbin{\&}\) で表します．

グラフ \(G\) の構築

まず \(G\) は，文字列の比較により \(\Theta(N^2 M)\) 時間 で隣接行列として求めることができます． またこれを

\[ [g_j]_i \coloneqq G \text{で頂点} i, j \text{間に辺がある} \]

となる数列 \((g_i)_{0 \le i \lt N}\) として持っておきます．

ハミルトン路の存在判定

次にハミルトン路の存在判定です． 巡回セールスマン問題を解く際と同様に

\[ [\mathrm{dp}_S]_v \coloneqq \text{これまでに通った頂点集合が } S \text{ で，} v \text{で終わる単純パスは存在するか} \]

というDPテーブルを埋めます． 「配るDP」による更新式は

\[ [\mathrm{dp}_{S \cup \{v'\}}]_{v'} \leftarrow [\mathrm{dp}_{S \cup \{v'\}}]_{v'} \lor \left( [\mathrm{dp}_{S}]_v \land [g_{v'}]_v \right) \qquad(v' \notin S) \]

のように表せ， \(\Theta(2^N N^2)\) 時間 で埋めることができますが，本問題では存在判定のみすればよいことを利用して \(\Theta(2^N N)\) 時間で埋める方法を紹介します．

\[ \begin{aligned} (\mathrm{dp}_S \mathbin{\&} g_{v'}) \ne 0 & \iff {}^{\exists}v \;( [\mathrm{dp}_{S}]_v \land [g_{v'}]_v) \\ & \iff \mathrm{dp}_S \text{から} [\mathrm{dp}_{S \cup \{v'\}}]_{v'} \leftarrow 1 \text{と「配る」遷移ができる} \end{aligned} \]

であるので，各 \(v\) に対する \([\mathrm{dp}_S]_v\) から \([\mathrm{dp}_{S \cup \{v'\}}]_{v'}\) への\(N\)個の遷移を，ビット演算を用いることでまとめて \(\Theta(1)\) 時間で行うことができます．

以上から本問題を全体 \(\Theta(N^2M + 2^N N)\) 時間で解くことができます．

実装例(Python): https://atcoder.jp/contests/abc302/submissions/46214188