ABC190 E - Magical Ornament

問題概要

数列$A = \{A_1, A_2, ..., A_N\}$が与えられる
Aから重複を許して要素を取り出し、数列を作る
数列の中身には$C_1, C_2, ..., C_K$をそれぞれ一つ以上含んでいる必要がある
また$(A_1, B_1), (A_2, B_2), ..., (A_M, B_M)$の組以外の要素は隣合わせることができない
数列の長さの最小値を求めよ

解法

グラフを使って考える
数列$A$の要素を頂点と考えて、
$(A_1, B_1), (A_2, B_2)...$の組を辺と考える
$C_1, C_2, ..., C_K$が連結でないなら不可能

連結である場合、
$C_1, C_2, ..., C_K$を含むパスの中で長さが最小のものが答えになる
これは$C$をどの順番で辿るかというのをすべて試せば答えが求まる
単純に解くと$K!$かかるが、DPを用いることで$O(2^N*N^2)$で解くことができる(TSPと同じようなやり方)

最終的な解法としては、
$C_i, C_j$間の距離をすべて求める
DPにより、$C$の順列をすべて試す
というようになる

提出コード

https://atcoder.jp/contests/abc190/submissions/20105591