ABC199 D - RGB Coloring 2 (400)
コンテスト中の考察
$ 3^n
は間に合わない
連結成分の頂点と辺の数から求まる?
分からず
解説の方法
DFSをして移動元と同じ色にしないようにするとパターンは
$ 2^n
通りになる
全パターンを試してDFSして条件を満たすものがあるかを求める
実装的には各bitを頂点に対応させて、移動元の色を除いて0なら小さい方、1なら大きい方の色にする
DFSが
$ \mathcal{O}(N)
なので全体で
$ \mathcal{O}(N 2^N)
問題:
https://atcoder.jp/contests/abc199/tasks/abc199_d
提出:
https://atcoder.jp/contests/abc199/submissions/22040054
#ABC199
#400pt
#D
#ABC
#AtCoder
#bit全探索