問題

$N$ 個の文字列 $S_1, \dots, S_N$ が与えられる.

先手と後手の2人がこの $N$ 個の文字列を用いてしりとりをする. 先手から交互に以下を満たすような整数 $i~(1 \leq i \leq N)$ を選ぶ.

条件を満たすような $i$ を選べなくなったら負けである.

両者が勝利のために最善を尽くした場合, 勝つのはどちらか?

bit dp で解くことにする. $\{1,2, \dots, N \}$ の空ではない部分集合 $S$ と整数 $i~(1 \leq i \leq N)$ に対して, ${\rm DP}[S,i]$ を

既に選ばれている整数の集合が $S$ で, 特に最後に選ばれた整数が $i$ である場面で回ってきた時, その人必勝ならば $T$ , 必敗ならば $F$ とする.

このとき, $S_i$ の先頭と末尾の文字をそれぞれ $\alpha_i, \beta_i$ とすると, 更新式はまだ選ばれていないしりとり可能な文字列を候補にし, 1つでもその先で必敗しなくてはならないので,

$\displaystyle {\rm DP}[S,i]=\lnot \bigwedge_{\substack{j \not \in S \\ A_i=B_j}} {\rm DP}[S \cup \{j\},j]$

である.

先手必勝であるための必要十分条件は最初に選ぶ文字列で場合分けすることによって,

$\displaystyle \lnot \bigwedge_{j=1,2, \dots, N} {\rm DP}[\{j\}, j]=T$

となる.

Kazun の競プロ記録