AtCoder Regular Contest 049 C - ぬりまーす

問題

　 $N(\le 100)$ 頂点のグラフについて、二つのタイプの条件の下に色を塗っていくことを考える。

タイプ1:ある頂点 $x$ に色を塗るとき、既に頂点 $y$ に色が塗られてなければならない。
タイプ2:ある頂点 $u$ に色を塗るとき、既に頂点 $v$ に色が塗られていてはいけない。

　タイプ1の制約は $A(\le 100)$ 個、タイプ2の制約は $B(\le 10)$ 個である。条件を守る限り任意の順番でグラフの頂点を塗れる場合に、最大で何個の頂点を塗ることができるか求めよ。

解法

　解説スライドはスライド中の文字が消えているため下のテキスト部分から解読した。

　タイプ1の制約だけの場合は、塗れるものを塗っていって変化がなくなるまでループを回し続けることで $O(N(N + A))$ で解ける。タイプ2の制約は「頂点 $u$ を塗らないか、あるいは頂点 $v$ に色を塗るときには既に頂点 $u$ に色が塗られてなければならない」と言い換えることができ、後者はタイプ1の制約である。頂点 $u$ を塗らないという制約は簡単に実現できるため、つまりタイプ2の制約については $2^B$ 通り試せばよい。 $B$ は小さいのでこれでこの問題が解けた。

反省

　1時間8分(4WA)でAC。最初はタイプ1の制約もタイプ2の制約もそのまま愚直に考えて、変化がなくなるまでループするという解答を書いて出したところ当然WA。サンプルは合うというのがいやらしい。

　頂点を選択する順番をランダムに選択して何度か実行し最大値を出力するという完全な嘘解法を書いてみて出してみたがダメ。WAは確実に減っているが……。これが解き始めてから30分ほどの時点。

　ちゃんと考察しようと考えなおして強連結成分分解とかdfsでの自己ループ検出とか考えてみたが、結局サンプルが合う解法すらひねり出せず1時間が経ったので解説スライドを見た。

　こういう問題を言い換えるタイプの解法が全然思いつかない。結局考察がほとんどできていないんじゃないか。確信を持っていない解法を書き始めるのはいい加減やめよう。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N, A, B;

ll solve(vector<vector<ll>> edge, vector<bool> forbid) {
    vector<bool> colored(N, false);
    ll result = 0;
    while (true) {
        bool change = false;

        for (ll i = 0; i < N; i++) {
            //i個目の頂点が塗れるか
            if (colored[i] || forbid[i]) {
                continue;
            }

            bool ok = true;
            for (ll to : edge[i]) {
                if (!colored[to]) {
                    ok = false;
                    break;
                }
            }
            if (!ok) {
                continue;
            }
            colored[i] = true;
            change = true;
            result++;
        }

        if (!change) {
            break;
        }
    }
    return result;
}

int main() {
    cin >> N;

    vector<vector<ll>> edgeA(N);

    cin >> A;
    for (ll i = 0; i < A; i++) {
        ll x, y;
        cin >> x >> y;
        x--; y--;
        edgeA[x].push_back(y);
    }
    cin >> B;
    vector<ll> u(B), v(B);
    for (ll i = 0; i < B; i++) {
        cin >> u[i] >> v[i];
        u[i]--; v[i]--;
    }

    ll ans = 0;

    for (ll i = 0; i < (1LL << B); i++) {
        auto edge = edgeA;
        vector<bool> forbid(N, false);
        for (ll j = 0; j < B; j++) {
            if ((1LL << j) & i) {
                edge[v[j]].push_back(u[j]);
            } else {
                forbid[u[j]] = true;
            }
        }

        ans = max(ans, solve(edge, forbid));
    }
    
    cout << ans << endl;
}