hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

TopCoder SRM 725 Div2 Hard: HiddenTreeDiv2

するめうめ

tsutaj.hatenablog.com

問題概要

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

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

  • それぞれの頂点について、入次数は高々  1
  • 頂点  x から到達できる頂点集合 ( x を含む) を  S_x とおくとき、  b_x = \sum_{i \in S_x} a_i を満たす

解説

頂点  x から辺を張る先の頂点集合を  T_x とすると、  b_x = \sum_{i \in T_x} b_i + a_x が成り立ちます。入次数が高々  1 という条件から、「前までに登場した頂点のなかで、まだ辺が入ってきていない頂点である集合」の部分集合が  T_x の候補です。

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

 \mathrm{dp} \left[ S \right] := 前までに登場した頂点のなかで、まだ辺が入ってきていない頂点集合が  S である状態にできるか (bool 値)

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

以上に気をつけて 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";
    }
};