TopCoder SRM 725 Div2 Hard: HiddenTreeDiv2

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → 掲載されてないぽい (unrated だから？)

頂点が 個あり、それぞれの頂点について値 が与えられる。以下の条件を満たす DAG が構成できるか判定せよ。

• それぞれの頂点について、入次数は高々
• 頂点 から到達できる頂点集合 ( を含む) を とおくとき、 を満たす

解説

頂点 から辺を張る先の頂点集合を とすると、 が成り立ちます。入次数が高々 という条件から、「前までに登場した頂点のなかで、まだ辺が入ってきていない頂点である集合」の部分集合が の候補です。

「前までに登場した・・・」とありますが、頂点を適切な順序で処理しなければなりません。これは要素が増えれば増えるほど総和は単調増加ですから、総和が小さい方から処理すれば良いです。ここまでくると、次のような DP が考えられます。

前までに登場した頂点のなかで、まだ辺が入ってきていない頂点集合が である状態にできるか (bool 値)

• 番目の要素を処理するとき、 番目はさっき追加したばかりでまだ辺が入っていないはずなので、 番目のビットは立っているはず
• ビットが立っているのは 番目までしかないはず

以上に気をつけて bit DP をします。ある要素について一度も更新が起こらなければ Impossible、そうでなければ Possible です。

ソースコード

int dp[1 << 14];
class HiddenTreeDiv2 {
    public:
    string isPossible(vector<int> a, vector<int> b) {
        vector< pair<ll, ll> > items;
        int N = a.size();
        for(int i=0; i<N; i++) items.push_back(make_pair(b[i], a[i]));
        sort(items.begin(), items.end());

        memset(dp, false, sizeof(dp));
        dp[0] = true;
        for(int i=0; i<N; i++) {
            bool ok = false;
            for(int bit=0; bit<(1<<i); bit++) {
                if(!dp[bit] || (i != 0 && !(bit >> (i-1) & 1))) continue;

                for(int nbit=bit;; nbit=(nbit-1)&bit) {
                    long long int sum = 0;
                    for(int k=0; k<i; k++) {
                        if(nbit >> k & 1) sum += items[k].first;
                    }
                    if(sum + items[i].second == items[i].first) {
                        int mask = (bit ^ nbit) | (1 << i);
                        dp[mask] = true;
                        ok = true;
                    }
                    if(nbit == 0) break;
                }
            }
            if(!ok) return "Impossible";
        }
        return "Possible";
    }
};