はまやんはまやんはまやん

hamayanhamayan's blog

RGB Coloring 2 [AtCoder Beginner Contest 199(Sponsored by Panasonic) D]

https://atcoder.jp/contests/abc199/tasks/abc199_d

2020/4/25修正。後半部分が嘘解法でした。

前提知識

解説

https://atcoder.jp/contests/abc199/submissions/22051608

制約を見ると全部の状態を全列挙しても大丈夫そうな感じがある。
本当に全列挙をすると320となり、これは間に合わない。
例4を見ると全列挙では320になってしまうが、実際は辺による関係がない場合は独立に組合せを考えることが出来そうである。

連結成分ごとに考える

辺による関係があるものについてグループ化して考えることにする。
グラフではその関係を連結関係といい、連結関係として辿っていけるまとまりを連結成分と言う。
連結成分ごとに組合せを考えれば、全体の答えはその積となる。
この操作を行うにはUnionFindが得意なので、UnionFindで連結成分を見つけてそれぞれに計算を行おう。

get関数

与えられた連結成分について問題を解いていく。
連結成分のとある部分について色を決定したとする。この時に使える色は3種類である。
そのある部分に隣接する頂点について色を決定したとする。
この時に使える色は遷移前の色以外の2種類である。
更にその次の遷移先で使える色は少なくとも遷移前の色は使えないので2種類以下である。
よって、「最初は3種類だけど、他は2種類以下となる」ので、最終的な計算量はO(2^|V|)となる。
(|V|は頂点数を指します)
つまり、全探索しても間に合う。

実装にはdfsを使う。
与えられた頂点について塗る順を決定するのにdfs2関数を使っていて、
実際に塗る検証をdfs関数でやっている。
dfsの実装に慣れていないとパパっと書くのは難しい問題。
重複順列の実装や木構造のdfsでの練習が足りない場合はそちらを学んでもいいかもしれない。

注意ですが、実際は少し実装が違います → 嘘解法でした

https://atcoder.jp/contests/abc199/submissions/22040329
グループごとに適当に塗っても通るだろうと思っていましたが、スターグラフを構築し、
葉でない頂点が最後に塗られるように順番を工夫することで319通りの塗りを達成できるのでTLEします。
ちゃんと横着せずに隣接点を塗りましょう…
@kanra8241さん、ありがとうございます。

int N, M;
vector<int> E[20];
//---------------------------------------------------------------------------------------------------
int vis[20];
void dfs2(int cu, vector<int>& arranged) {
    if (vis[cu]) return;
    vis[cu] = 1;

    arranged.push_back(cu);

    fore(to, E[cu]) dfs2(to, arranged);
}
//---------------------------------------------------------------------------------------------------
int col[20];
ll dfs(int _cu, vector<int>& vs) {
    if (_cu == vs.size()) return 1;
    int cu = vs[_cu];

    vector<int> cnt(3, 0);
    fore(to, E[cu]) if (0 <= col[to]) cnt[col[to]]++;

    int res = 0;
    rep(c, 0, 3) if (cnt[c] == 0) {
        col[cu] = c;
        res += dfs(_cu + 1, vs);
        col[cu] = -1;
    }
    return res;
}
ll get(vector<int> vs) {
    rep(i, 0, N) col[i] = -1;
    rep(i, 0, N) vis[i] = 0;

    vector<int> arrangedVs = vector<int>();
    dfs2(vs[0], arrangedVs);
    return dfs(0, arrangedVs);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    UnionFind uf(N);
    rep(i, 0, M) {
        int A, B; cin >> A >> B;
        A--; B--;
        uf(A, B);

        E[A].push_back(B);
        E[B].push_back(A);
    }

    map<int, vector<int>> grp;
    rep(i, 0, N) grp[uf[i]].push_back(i);
    ll ans = 1;
    fore(p, grp) ans *= get(p.second);
    cout << ans << endl;
}