hogecoder

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

TopCoder SRM 725 Div1 Med: HiddenTree

するめうめ

tsutaj.hatenablog.com

問題概要

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

頂点が  N 個あり、それぞれの頂点について値  b_i が与えられる。各頂点に  a_i という値を適切に決めたとき、以下の条件を満たす DAG がいくつできるか求めよ。なお、  a_i の値が異なっていても、グラフが同型 (頂点のラベルと辺の対応が完全に一致する) であれば区別しないものとする。

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

解説

Div2 Hard と方針はほぼ同じで、数え上げパートが増えただけです。

方針は Div2 Hard の方の記事 を参照してください。

ソースコード

int dp[1 << 14];
class HiddenTree {
    public:
    int count(vector<int> b) {
        int N = b.size();
        sort(b.begin(), b.end());

        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        int ret = 0;
        for(int i=0; i<N; i++) {
            for(int bit=0; bit<(1<<i); bit++) {
                if(i != 0 && !(bit >> (i-1) & 1)) continue;
                for(int mask=bit;; mask=(mask-1)&bit) {
                    ll sum = 0;
                    for(int k=0; k<i; k++) {
                        if(mask >> k & 1) sum += b[k];
                    }

                    if(sum < (ll)b[i]) {
                        int nbit = (bit ^ mask) | (1 << i);
                        (dp[nbit] += dp[bit]) %= MOD;
                        if(i == N-1) (ret += dp[bit]) %= MOD;
                    }

                    if(mask == 0) break;
                }
            }
        }
        return ret;
    }
};

TopCoder SRM 725 Div1 Easy: FiveRooks

するめうめ

tsutaj.hatenablog.com

問題概要

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

 8 \times 8 の盤面にルークがいくつか置かれている。

行の座標どうしが unique に、列の座標どうしが unique になるようにルークを  5 つ選べ。

解説

 {}_{64} C_{5} \approx 7.6 \times 10^{6} なので、適当に全探索したら通ります。

ソースコード

class FiveRooks {
    public:
    const int S = 64;

    bool check(vector<string> board, int x) {
        int r = x / 8, c = x % 8;
        return board[r][c] == 'R';
    }

    void ins(set<int> &R, set<int> &C, vector<int> &ret, int x) {
        int r = x / 8, c = x % 8;
        R.insert(r);
        C.insert(c);
        ret.push_back(r);
        ret.push_back(c);
    }

    vector<int> find(vector<string> board) {
        rep(i,0,S) rep(j,i+1,S) rep(k,j+1,S) rep(l,k+1,S) rep(m,l+1,S) {
            bool ok = true;
            ok &= check(board, i);
            ok &= check(board, j);
            ok &= check(board, k);
            ok &= check(board, l);
            ok &= check(board, m);
            if(!ok) continue;

            vector<int> ret;
            set<int> R, C;
            ins(R, C, ret, i);
            ins(R, C, ret, j);
            ins(R, C, ret, k);
            ins(R, C, ret, l);
            ins(R, C, ret, m);

            if(R.size() != 5 || C.size() != 5) continue;
            return ret;
        }
        return vector<int>();
    }
};

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";
    }
};