天下一文字列集合 https://beta.atcoder.jp/contests/tenka1-2014-quala/tasks/tenka1_2014_qualA_c
文字列 s と t を同じ文字列で表現できるとき、s と t の間に無向辺を張る、ということを考えよう。このようにして作った無向グラフのあるクリークに属する頂点すべては 1 つの文字列で表現できるため、与えられたグラフをできるだけ少ない個数のクリークに分解する問題になる。
これは dp[S] := 頂点集合 S をクリークに分解する時の個数の最小値 とし、S と共通部分を持たず、かつクリークである集合 T をぶつけて、dp[S|T] = min(dp[S|T], dp[S] + 1) のように更新すれば良い。計算量 O((2^N)^2)
あとはしれっと余事象で解く必要があるけど、「〜〜〜の中に一度でも出現する」系は余事象でやったほうが絶対わかりやすい。そういう意味での類題は http://arc058.contest.atcoder.jp/tasks/arc058_c
夏合宿2015day2D 真っ暗な部屋 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2709)
はじめは $ dp[S][k] = k $ 回の指示で集合 $ S $ の状態にできるか (bool 値) を解く DP を考えたが、指示の上限はいくつか、計算量は大丈夫か、などなど迷ってしまった (実際サンプルくらいの回数であれば正しく動くが大きいケースだと無理)
集合に対しての最短路を解けば良いと考えるとあとは早かった。集合に対して最短路をやったのはたぶん初めてなのでこの調子で柔軟に対処したい
競プロ / ここはチラ裏です / http://tsutaj.hatenablog.com