SRM696 div1 easy Gperm

考えたこと

• 頂点集合はもてないけど辺集合は持てるねみたいな感じのbitDPっぽさ
• dp[S] = (Sに含まれる辺は両端が赤い頂点な辺) とかをしたくなる
• どの辺の両端を赤くしたら他の辺で赤くならないといけない辺があったりいろいろ依存関係がある
• 1-2,1-3,1-4,1-5 が辺としてあるとき、頂点2,3,4,5を全て塗ってから頂点1を塗れば同時に塗れる
• 頂点を (2,3) → (1) → (4) → (5) の順番で塗っていくとする
• 一回1を塗ると(4,5)をまとめて塗るのが不可能になってる
• 多重辺があると当然同時に塗られるし自己ループがあると塗るタイミングがいろいろ複雑になる
• このへんの依存関係をうまくまとめて遷移を書く方法が全く思い浮かばない
  -----解説を見た-----
• 逆の操作として考える
• そもそも全頂点が赤いとして減らしていく
• dp[S] = (Sに含まれる辺は少なくとも片方が赤くない頂点)
• 遷移についてはある頂点を赤くなくすると考える

状態は辺で持つが遷移は辺中心でなく頂点中心に考える発想がなかった

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

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

    // nxt[i] = (i番目の頂点を消すと影響がある辺)
    VI nxt(n);
    REP(i, n) REP(j, m) {
      if(x[j]==i || y[j]==i) {
        nxt[i] |= 1<<j;
      }
    }

    // dp[i] = (集合iの辺は無効な辺)
    VI dp(1LL<<m, INF);
    dp[0] = 0;
    REP(i, 1LL<<m) {
      // 頂点jを落とすとnxt[j]の辺が無効になる
      REP(j, n) {
        chmin(dp[i | nxt[j]], dp[i] + (m-__builtin_popcountll(i)));
      }
    }
    return dp[(1LL<<m)-1];
  }
};