WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM696 Div1 Easy "Gperm"

考えたこと

むずい!Div1 Easyってこんなにむずかったっけ!?
1時間考えてもできない・・
せや!他の人のソースコードを見て何やってるか考えたろ!

解法

ヒーローは頂点を色で塗っていく流れだが、それを逆にして、色が全て塗られた状態から始めてそれを消していくと考える。
なぜかというと、問題通りの流れでやると、頂点に1つ色を塗っても付随する辺によるコストが増えるのかはたまた変わらないのか分からない。
逆の流れでやると、頂点の色を1つ消すと付随する辺によるコストが必ず減るため、状態の管理が楽ちんになるからである!(たぶん)

辺iによるコストが発生していれば0、発生していなければ1というbitDPを行う。
dp[bit] := 辺の状態をbit(辺iによるコストが発生していればbit[i]は0、発生していなければ1)にしたときの最小コスト

初期値

何も行動を起こさないときのコストは0であるから
dp[0] = 0

更新

それぞれのbitの状態にて、頂点ごとに色を消していき、bitの状態の最小コストを更新していく。
その時にかかるコストはbitで0(コストが発生)の数。

結果

dp[(1 << 辺の数) - 1]

事後

if (1年以上ブランク && 環境をAtomに変更 && 鳥頭) {
    俺.SRM力 /= 10;
}

ソースコード

const int INF = 55 * 25;

int mask[55];
int dp[1 << 20];

class Gperm {
    public:
    int countfee(vector<int> x, vector<int> y) {
        int n = x.size();

        // 頂点の色を消すとコストが発生しなくなる辺のbitを1に立てる
        memset(mask, 0, sizeof(mask));
        for (int i = 0; i < n; i++) {
            mask[x[i]] |= (1 << i);
            mask[y[i]] |= (1 << i);
        }

        // dpする
        for (int b = 0; b < (1 << n); b++) {
            dp[b] = INF;
        }
        dp[0] = 0;
        // 状態ごと
        for (int b = 0; b < (1 << n); b++) {
            // 頂点ごと
            for (int i = 0; i < 50; i++) {
                int nb = b | mask[i];
                dp[nb] = min(dp[nb], dp[b] +  n - __builtin_popcount(b));
            }
        }
        return dp[(1 << n) - 1];
    }
};