👻

ABC190 E - Magical Ornament

2021/02/13に公開

問題概要

数列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

Discussion

ログインするとコメントできます