(部分集合の部分集合を列挙・差集合)ARC-056-C-部門分け

問題URL→http://arc056.contest.atcoder.jp/tasks/arc056_c

分からなかったので解説を見たが、まだ良く分かっていない。
結局他の人のコードを見た。

最初、コードの下のほうのビット演算が何を意味しているのか分からなかったが、
どうやら部分集合の部分集合を列挙しているらしい。
蟻本に書いてあった。←これなくしたい

集合の演算でi^jは集合iと集合jの差集合i-jを表す!!(ただしjがiの部分集合のとき)

独立な集合i,j間の辺の重みの総和は全ての部分集合に含まれる辺の総和を前計算しておくと
ある集合iの辺の総和をsouwa(i)として
i,j間の辺の重みの総和は
souwa(i|j) – souwa(i)-souwa(j)で求められる!

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N, K;
int w[20][20];
int clq[1<<17];
int dp[1<<17];

signed main()
{
    cin >> N >> K;
    REP(i,N) REP(j,N) cin >> w[i][j];

    REP(i,1<<N) {
        int s = 0;
        REP(j,N) if (i & (1 << j)) {
            for (int k=j+1; k<N; k++) if (i & (1 << k)) {
                s += w[j][k];
            }
        }
        clq[i] = s;
    }

    dp[0] = 0;
    for (int i=1; i<(1<<N); i++) {
        dp[i] = 0;
        //↓部分集合iの部分集合を列挙する
        for (int j=i; j>0; j=(j-1)&i) {
            dp[i] = max(dp[i], dp[i^j] + clq[j] + K);
        }
    }

    cout << dp[(1<<N)-1] - clq[(1<<N)-1] << endl;
}

(トポロジカルソートの数え上げ・DP)ABC-041-D-徒競走

問題URL→http://abc041.contest.atcoder.jp/tasks/abc041_d

トポロジカルソートの数え上げはO(2^N)で出来るようだ。
詳しい解説は公式解説を参照。

漸化式は最も右に置かれる要素によって場合わけをする。(詳しくは公式解説参照)

#include <iostream>
#include <vector>
#include <string.h>
#include <climits>
#include <algorithm>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N, M;
int x, y;
vi G[20];

int dp[1<<16];

int rec(int S)
{
    if (dp[S] > 0) return dp[S];
    if (S == 0) return 1;

    int res = 0;
    REP(i,N) {
        if (S >> i & 1) {
            bool ok = true;
            for (int v : G[i]) {
                if (S >> v & 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                res += rec(S & ~(1 << i));
            }
        }
    }

    return dp[S] = res;
}

signed main()
{
    cin >> N >> M;
    REP(i,M) {
        cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
    }

    cout << rec((1 << N) - 1) << endl;
}

(bitDP・配るDP)ABC-025-D-25個の整数

問題URL→http://abc025.contest.atcoder.jp/tasks/abc025_d

コンテスト本番で満点で通している人が2人だけの難問。
ポイントがいくつかある。

一つ目は1から順番に埋めていくということ。
この条件を加えることで次回以降に埋める数字は今の数字より大きいという制約が掛かる。

二つ目はその数字を置こうとしている場所の左右または上下に片方だけ既に数字が埋まっている場合はあとで矛盾が生まれる。
よってこれを避けていくと矛盾のない埋め方が得られる。

三つめはbitDPを使うということ。これまでに埋めた値は今見ている値より小さいことがすでに分かっているので、
埋めた場所だけ分かればよい。これはbitDPでできる。
2^25が約3*10^7というところからbitDPを検討すべき。

今回の問題のような小さい値から順番に埋めていくテクニックはとても汎用的。
二つ目のポイントは部分に注目して場合分けして考察するようにしよう。

配るDP

また^でどちらか片方のみtrueの場合を検出できる。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
//*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int A[25];
int fix[26];    //既に指定されている数字の場所fix[5]:5が入っている場所インデックス
int dp[1<<25];
vector<int> V;

signed main()
{
    REP(i,26) fix[i] = -1;
    REP(i,25) {
        cin >> A[i];
        if (A[i] == 0) V.push_back(i);
        else fix[A[i]] = i;
    }

    dp[0] = 1;
    //配るDP
    for (int mask=0; mask<(1<<25)-1; mask++) if (dp[mask]) {
        int b = __builtin_popcount(mask) + 1;   //次に置く数字
        if (fix[b] >= 0) {
            //次に置く数字bの場所が指定されていた場合
            int r = fix[b];
            int y = r / 5;
            int x = r % 5;
            if ((mask & (1 << r)) == 0) {
                //これから置く場合
                if (y > 0 && y < 4 && ((mask >> (r - 5)) ^ (mask >> (r + 5))) & 1) continue;
                if (x > 0 && x < 4 && ((mask >> (r - 1)) ^ (mask >> (r + 1))) & 1) continue;
                dp[mask ^ (1 << r)] += dp[mask];
                if (dp[mask ^ (1 << r)] >= MOD) dp[mask ^ (1 << r)] -= MOD;
            }
        } else {
            for (int r : V) {
                int y = r / 5;
                int x = r % 5;
                if ((mask & (1 << r)) == 0) {
                    if (y > 0 && y < 4 && ((mask >> (r - 5)) ^ (mask >> (r + 5))) & 1) continue;
                    if (x > 0 && x < 4 && ((mask >> (r - 1)) ^ (mask >> (r + 1))) & 1) continue;
                    dp[mask ^ (1 << r)] += dp[mask];
                    if (dp[mask ^ (1 << r)] >= MOD) dp[mask ^ (1 << r)] -= MOD;
                }
            }
        }
    }

    cout << dp[(1<<25)-1] << endl;
}

(bitDP)ARC-010-C-積み上げパズル

問題URL→http://arc010.contest.atcoder.jp/tasks/arc010_3

全然分からんかったので次の解説スライドを見た。
https://www.slideshare.net/yumainoue965/arc-010-c-15658047

どうやらbitDPらしい。コードはこの方のを参考にさせてもらった。

まだ理解しきれていないのでまた復習しよう。

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
const int INF = 1e9;

unordered_map<char, int> U; //文字, インデックス
int S[10];      //ポイント
int T[5000];    //色
int dp[2][1024][10];    //使った色の集合

//https://www.slideshare.net/yumainoue965/arc-010-c-15658047
//↑のとdpの添え字の順番が異なる

signed main()
{
    int n, m, y, z;
    cin >> n >> m >> y >> z;

    REP(i,m) {
        char a;
        cin >> a >> S[i];   //文字とポイント
        U[a] = i;
    }

    string b;
    cin >> b;
    REP(i,b.length()) {
        T[i] = U[b[i]];
    }

    REP(i,1<<m) {
        REP(j,m) {
            dp[0][i][j] = LONG_LONG_MIN / 3;
        }
    }

    REP(i,n) {
        REP(j,1<<m) {
            REP(k,m) {
                dp[(i+1)&1][j][k] = LONG_LONG_MIN / 3;
            }
        }
        //使い始める
        dp[(i+1)&1][1<<T[i]][T[i]] = S[T[i]];
        REP(j,1<<m) {
            REP(k,m) {
                //使う
                if (k == T[i]) {
                    dp[(i+1)&1][j|(1<<T[i])][T[i]] = max(dp[(i+1)&1][j|(1<<T[i])][T[i]], dp[i&1][j][k] + S[T[i]] + y);
                } else {
                    dp[(i + 1) & 1][j | (1 << T[i])][T[i]] = max(dp[(i + 1) & 1][j | (1 << T[i])][T[i]], dp[i & 1][j][k] + S[T[i]]);
                }
                //使わない
                dp[(i+1)&1][j][k] = max(dp[(i+1)&1][j][k], dp[i&1][j][k]);
            }
        }
    }

    int ans = 0;
    REP(j,1<<m) {
        REP(k,m) {
            if (j + 1 == (1 << m)) dp[n&1][j][k] += z;
            ans = max(ans, dp[n&1][j][k]);
        }
    }

    cout << ans << endl;
}