ferinの競プロ帳

競プロについてのメモ

AGC004 D - Teleporter

AGC 競技プログラミング

問題ページ

考えたこと

  • "ぴったり"K回の制約がやっかい
  • 街1のテレポーターが街1につながっていればK回以下で街1にたどり着きさえすればよい
  • 街1のテレポーターが街1以外につながっていて実現可能な構成があるか？
  • なもりグラフのサイクル上の街から首都までの距離を等しくするのが不可能
  • したがって街1→街1としなければ不可能
  • 街1との距離がK以上の街のテレポーターを街1につなげばよさそう
  • 街1との距離は街1を始点としてbfsなりdijkstraなりすれば求まる
  • 距離k以上の街の数を数えたらサンプルが合わない
  • 1 <- i <- j <- k とつながってる場合に街jのテレポーターを変更したら街kにも影響する
  • 距離k+1 + lk(lは整数)となっているような街のテレポーターを変更するとしてみる
  • サンプルは合ったがWA
  • 以下のようなケースでだめ
k=2
1-2-3-4
     -5
  • 街3のテレポーターを変更すればよいが街4,5のテレポーターを変更してしまっている
  • 根にできるだけ近い頂点のテレポーターを変更した方がよさそう
  • 根(街1)から考えるのではなく葉から考えてみる
  • 葉からの距離がKの頂点が存在したら、その頂点の子で距離がK-1の頂点のテレポーターを変更する必要がある
  • この貪欲を葉から順番に行うdfsを書くと通る
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
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()
 
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); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  vector<vector<ll>> g(n);
  ll ret = 0;
  REP(i, n) {
    cin >> a[i];
    a[i]--;
    if(i == 0 && a[i] != 0) {
      a[i] = 0;
      ret++;
    }
    if(i) {
      g[a[i]].push_back(i);
      g[i].push_back(a[i]);
    }
  }

  function<ll(ll,ll)> dfs = [&](ll v, ll p) {
    vector<ll> vec;
    for(auto to: g[v]) {
      if(to == p) continue;
      vec.push_back(dfs(to, v) + 1);
    }
    ll ma = 0, cnt = 0;
    for(auto i: vec) {
      if(i == k) cnt++;
      else chmax(ma, i);
    }
    if(v) ret += cnt;
    return ma;
  };

  dfs(0, -1);
  cout << ret << endl;

  return 0;
}

ARC029 D - 高橋君と木のおもちゃ

ARC 競技プログラミング

問題ページ

二乗の木DPの練習として解いた。

解法

Mステップで使う玉は置かないという選択もできる。木の深い頂点から順番に置いていけば置いた玉が捨てられることはない。したがって、木の頂点にi個置くときはM個中の大きい方i個だけを置くとするのが最善の選択肢になる。i個木に玉を置くとするとき追加される玉の値の和の最大化は実現できた。あとは木から取り除かれるi個の玉の値の和をできるだけ小さくすることができればよい。
これは木DPを用いて実現できる。dp[i][j] = (頂点i以下の部分木からj個取り除いたときの取り除いた玉の値の和の最小) とする。遷移は2つの部分木のマージという形でかける。ret[i]とtmp[i]をマージしてnret[i]にするとする。このときnret[i+j] = min(nret[i+j], ret[i]+tmp[j]) となる。頂点i以下の部分木から取り除く玉の1つ目は必ず頂点iになることに注意。
遷移のマージがO(N^2)で合計O(N^3)っぽいがこれは二乗の木DPと言われるテクで部分木の大きさまでしかみないようにすることでO(N^2)になっている。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#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()
 
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); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  vector<ll> s(n);
  vector<vector<ll>> g(n);
  ll sum = 0;
  REP(i, n) cin >> s[i], sum += s[i];
  REP(i, n-1) {
    ll a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  ll m;
  cin >> m;
  vector<ll> t(m);
  REP(i, m) cin >> t[i];

  using VL = vector<ll>;
  function<VL(ll,ll)> dfs = [&](ll v, ll p) {
    VL ret(2, 0);
    ret[1] = s[v];
    for(auto to: g[v]) {
      if(to == p) continue;
      auto tmp = dfs(to, v);
      VL nret(ret.size()+tmp.size()-1, LLINF);
      nret[0] = 0, nret[1] = s[v];
      FOR(i, 1, ret.size()) REP(j, tmp.size()) {
        if(i+j <= 1) continue;
        chmin(nret[i+j], ret[i] + tmp[j]);
      }
      ret = nret;
    }
    return ret;
  };
  auto dp = dfs(0, -1);

  sort(ALL(t), greater<>());
  FOR(i, 1, m) t[i] += t[i-1];
  ll ret = sum;
  REP(i, m) {
    if(i+1 >= dp.size()) break;
    chmax(ret, sum - dp[i+1] + t[i]);
  }
  cout << ret << endl;

  return 0;
}

ARC101 E - Ribbons on Tree

競技プログラミング AtCoder

問題ページ

考えたこと

  • とりあえず木DPっぽい
  • dp[頂点i][部分木iでまだペアが確定していない頂点の数j] みたいなのを考える
  • 頂点数がdpテーブルに来てるし二乗の木DPっぽい
  • 遷移がどうなるか考えるけど全くまとまらない
  • 数学できれいになるのかなあと思って計算するけど何もわからない
    -----解説を見た-----
  • 少なくとも1本に覆われている → 一本も覆われていない頂点がない
  • 包除原理で数える
  • 辺の数の偶奇(=包除原理の正負)で分け、DPをつかって計算する
  • dp[i][j][k] = (頂点i以下の部分木で頂点iと連結な頂点がj個で辺の偶奇がkのときの組み合わせ数) とする
  • 遷移は頂点iとiの子toをつなぐときと切断するときで場合分けする
    • iとtoを切断する→to以下の部分木の組み合わせが確定して辺のとり方(解説のg)を掛ける
    • iとtoをつないだまま→頂点数がi以下とto以下の和になる
  • 3乗っぽいけど間に合う2乗の木DP
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
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()
 
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); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

struct mint {
  ll x;
  mint(): x(0) { }
  mint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}
  ll get() const { return x; }
  // e乗
  mint pow(ll e) {
    ll a = 1, p = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    return mint(a);
  }
  // Comparators
  bool operator <(mint b) { return x < b.x; }
  bool operator >(mint b) { return x > b.x; }
  bool operator<=(mint b) { return x <= b.x; }
  bool operator>=(mint b) { return x >= b.x; }
  bool operator!=(mint b) { return x != b.x; }
  bool operator==(mint b) { return x == b.x; }
  // increment, decrement
  mint operator++() { x++; return *this; }
  mint operator++(signed) { mint t = *this; x++; return t; }
  mint operator--() { x--; return *this; }
  mint operator--(signed) { mint t = *this; x--; return t; }
  // Basic Operations
  mint &operator+=(mint that) {
    x += that.x;
    if(x >= MOD) x -= MOD;
    return *this;
  }
  mint &operator-=(mint that) {
    x -= that.x;
    if(x < 0) x += MOD;
    return *this;
  }
  mint &operator*=(mint that) {
    x = (ll)x * that.x % MOD;
    return *this;
  }
  mint &operator/=(mint that) {
    x = (ll)x * that.pow(MOD-2).x % MOD;
    return *this;
  }
  mint &operator%=(mint that) {
    x = (ll)x % that.x;
    return *this;
  }
  mint operator+(mint that) const { return mint(*this) += that; }
  mint operator-(mint that) const { return mint(*this) -= that; }
  mint operator*(mint that) const { return mint(*this) *= that; }
  mint operator/(mint that) const { return mint(*this) /= that; }
  mint operator%(mint that) const { return mint(*this) %= that; }
};
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  vector<vector<ll>> g(n);
  REP(i, n-1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<mint> c(n+1);
  c[2] = 1;
  for(ll i=4; i<=n; i+=2) c[i] = c[i-2] * (i-1);

  // 2乗の木DP
  function<vector<vector<mint>>(ll,ll)> dfs = [&](ll v, ll par) {
    auto ret = make_v<mint>(2,2);
    ret[1][0] = 1;
    for(auto to: g[v]) {
      if(to == par) continue;
      auto tmp = dfs(to, v);
      auto nret = make_v<mint>(ret.size()+tmp.size()-1, 2);
      REP(i, ret.size()) REP(j, tmp.size()) {
        // vからtoまでの辺を切断
        nret[i][0] += ret[i][0] * tmp[j][1] * c[j] + ret[i][1] * tmp[j][0] * c[j]; 
        nret[i][1] += ret[i][0] * tmp[j][0] * c[j] + ret[i][1] * tmp[j][1] * c[j];
        // vからtoまでの辺をつないだまま
        nret[i+j][0] += ret[i][0] * tmp[j][0] + ret[i][1] * tmp[j][1];
        nret[i+j][1] += ret[i][0] * tmp[j][1] + ret[i][1] * tmp[j][0];
      }
      swap(ret, nret);
    }
    return ret;
  };

  auto ret = dfs(0, -1);
  mint ans = 0;
  REP(i, ret.size()) {
    ans += ret[i][0] * c[i];
    ans -= ret[i][1] * c[i];
  }
  cout << ans << endl;

  return 0;
}

ARC072 E - Alice in linear land

競技プログラミング AtCoder 要復習

問題ページ

考えたこと

  • まずどんな動きをするのか試してみる
  • 進行方向が反転だったりを考える必要はなくて目的地までの距離だけ使えばよさそう
  • 現在の目的地までの距離をXでd[i]を入力するとX' = min(X, abs(X-d[i])) に変化する
  • Xは単調に減少していくいうことがわかった
  • 書き換えるという動作で何ができるのか
  • まずX'がXより遠い位置になることはない
  • 移動する距離を1~XにすればX'を0~X-1にすることはできる
  • また移動する距離をinfにすればXから移動しないのでXにもできる
  • つまり書き換えるという操作は0~Xのどこかの距離に移動させるという操作になる
  • p番目を書き換えたとき、0~p-1番目の操作をした後の目的地までの距離をYとする
  • p番目では0~Yの距離になる
  • p+1番目以降の操作で目的地にたどり着けない距離があるか？(=0~Yの内に目的地にたどり着けないのがあるか？)が判定できればよい
  • 区間[p+1,n)について考えるので後ろから見たくなる
  • dp[i][j] = (i番目以降の移動で距離jから目的地にたどり着くか？)を考えてdpテーブルを書いてみる
  • たどり着ける点が連続にならんでいるときは最大の値だけ持てばよいのでできそう
  • 不連続なときがよくわからない
  • Dがどこかの範囲で抑えられて空間が大丈夫でインラインDPができるとか考えたけどわからない ----- 解説を見た -----
  • たどり着けない最小の距離だけ持っておけばよいらしく、後ろから見れば解けるらしい

不連続のケースが結局よくわかってないので要復習

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#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 INF = (1LL<<60);
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); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  vector<ll> v(n+1);
  cin >> v[0];
  REP(i, n) cin >> v[i+1];

  vector<ll> a(n+1);
  a[0] = v[0];
  FOR(i, 1, n+1) a[i] = min(abs(a[i-1]-v[i]), a[i-1]);

  vector<ll> b(n+2);
  b[n+1] = 1;
  for(ll i=n; i>=1; --i) {
    if(min(abs(b[i+1] - v[i]), b[i+1]) == b[i+1]) {
      b[i] = b[i+1];
    } else {
      b[i] = b[i+1] + v[i];
    }
  }

  ll q;
  cin >> q;
  REP(test, q) {
    ll p;
    cin >> p;
    if(b[p+1] <= a[p-1]) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }

  return 0;
}

CODE FESTIVAL 2016 Elimination Tournament Round 1 A - グラフ / Graph

AtCoder 競技プログラミング

問題ページ

考えたこと

  • Q=1ならどうか？
  • SとTの間に重み0の辺を張ってMSTを求めればよい
  • MSTを求めるのをQ回やったら当然TLE
  • MST+αのやつは元のグラフのMSTを求めてそこからいじるのがよくあるパターン
  • 元のグラフのMSTと辺を追加したグラフのMSTは何が違うか
  • 基本閉路を考えると辺を追加したことで削除できる辺はパスs-t上の辺
  • 重みを最小化するには重みが最大の辺を消すべき
  • パスs-t間の重みが最大の辺を求めるにはN回dfsしておけばよい
  • dfs前計算 + クエリに答える部分でO(N^2 + Q) で解ける

基本閉路、基本カットセット、辺を交換していくことで任意の全域木Sから任意の別の全域木Tに移せるあたりを知っておくとMST関連の問題で便利だと思う

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;
 
#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()
 
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); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

struct UnionFind {
  vector<int> par, s;
  UnionFind(int n=2e5) { init(n); }
  void init(int n) { 
    s.assign(n, 1); par.resize(n); 
    iota(par.begin(), par.end(), 0);
  }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];
    else par[y] = x, s[x] = s[x] + s[y];
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return s[find(x)]; }
};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n, m;
  cin >> n >> m;
  auto e = make_v<ll>(m, 3);
  REP(i, m) {
    cin >> e[i][1] >> e[i][2] >> e[i][0];
    e[i][1]--, e[i][2]--;
  }

  ll sum = 0;
  UnionFind uf(n);
  vector<vector<PII>> g(n);
  sort(ALL(e));
  REP(i, m) {
    if(uf.same(e[i][1], e[i][2])) continue;
    uf.unite(e[i][1], e[i][2]);
    g[e[i][1]].push_back({e[i][2], e[i][0]});
    g[e[i][2]].push_back({e[i][1], e[i][0]});
    sum += e[i][0];
  }

  auto d = make_v<ll>(n, n);
  fill_v(d, 0);
  function<void(ll,ll,ll,ll)> dfs = [&](ll v, ll p, ll s, ll dist) {
    d[s][v] = dist;
    ll ret = 0;
    for(auto to: g[v]) {
      if(to.first == p) continue;
      dfs(to.first, v, s, max(dist,to.second));
    }
  };
  REP(i, n) dfs(i, -1, i, 0);

  ll q;
  cin >> q;
  REP(i, q) {
    ll s, t;
    cin >> s >> t;
    s--, t--;
    cout << sum - d[s][t] << endl;
  }

  return 0;
}

QUPC2018 G - Tapu & Tapi 2

競技プログラミング AtCoder

問題ページ

部分点

たぷとたぴが連結にならないようにする→カットなので最小カットを求めればよい。N<=500ならば最大フローを求めるアルゴリズムで間に合うのでdinicなどのライブラリを貼ればよい。

満点解法

木DPをする。dp[i][j] = (頂点iの部分木でiと連結な成分に{両方いない、たぷがいる、たぴがいる}(=j)のときの辺を切断する最小コスト) とする。cをiの子、iとcの辺の重みをwとする。c以下の部分木が条件を満たさないならiとcの辺を切断しなければならない。逆に条件を満たすなら辺を切断する必要はない。したがって、このDPの遷移は

  • dp[i][両方いない] = min(dp[c][両方いない], dp[c][たぷがいる] + w, dp[c][たぴがいる] + w) (頂点iにはたぷもたぴもいない)
  • dp[i][たぷがいる] = min(dp[c][両方いない], dp[c][たぷがいる], dp[c][たぴがいる] + w) (頂点iにたぴはいない)
  • dp[i][たぴがいる] = min(dp[c][両方いない], dp[c][たぷがいる] + w, dp[c][たぴがいる]) (頂点iにたぷはいない)

となる。これを木DPとして葉から計算していけばよい。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define int ll
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()
 
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); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n, x, y;
  cin >> n >> x >> y;
  vector<vector<pair<ll,ll>>> g(n);
  REP(i, n-1) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  vector<ll> exist_a(n), exist_b(n);
  REP(i, x) {
    int p; cin >> p, p--, exist_a[p] = 1;
  }
  REP(i, y) {
    int q; cin >> q, q--, exist_b[q] = 1;
  }

  // dp[i][mask] = (頂点i以下の部分木の連結成分にたぷ、たぴを含んでいる状況がmaskのときのminコスト)
  auto dp = make_v<ll>(n, 3);
  fill_v(dp, LLINF);
  function<void(int,int)> dfs = [&](int v, int p) {
    if(g[v].size()==1 && p!=-1) {
      if(exist_a[v]) {
        dp[v][1] = 0;
      } else if(exist_b[v]) {
        dp[v][2] = 0;
      } else {
        dp[v][0] = 0;
      }
      return;
    }

    if(!exist_a[v] && !exist_b[v]) dp[v][0] = 0;
    if(!exist_b[v]) dp[v][1] = 0;
    if(!exist_a[v]) dp[v][2] = 0;
    for(auto to: g[v]) {
      if(to.first == p) continue;
      dfs(to.first, v);
      if(!exist_a[v] && !exist_b[v]) {
        dp[v][0] += min({dp[to.first][0], dp[to.first][1]+to.second, dp[to.first][2]+to.second});
      }
      if(!exist_b[v]) {
        dp[v][1] += min({dp[to.first][0], dp[to.first][1], dp[to.first][2]+to.second});
      }
      if(!exist_a[v]) {
        dp[v][2] += min({dp[to.first][0], dp[to.first][1]+to.second, dp[to.first][2]});
      }
    }
  };

  dfs(0, -1);
  cout << min({dp[0][0], dp[0][1], dp[0][2]}) << endl;

  return 0;
}

QUPC2018 F - Team Making

競技プログラミング AtCoder

問題ページ

解法

bitDPで数え上げる。dp[S] = (集合Sがすでにチームが決まっているときの組み合わせ数) とする。TをSに含まれない要素の集合とすると集合Tから1人、2人、3人を選んでチームとする。このチームをSに新たに加えた集合をS'とするとdp[S'] += dp[S]という遷移になる。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
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()
 
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); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n, K;
  cin >> n >> K;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  vector<ll> dp(1LL<<n);
  dp[0] = 1;
  REP(i, (1LL<<n)-1) {
    vector<ll> v;
    REP(j, n) {
      if(!(i&1<<j)) {
        v.push_back(j);
      }
    }
    // 集合iに含まれない人から選ぶ
    ll x = v[0];
    // 1人チーム
    dp[i | 1<<x] += dp[i];
    FOR(j, 1, v.size()) {
      // 2人チーム　平均の条件を確認
      if(a[x] + a[v[j]] <= 2*K) {
        dp[i | 1<<x | 1<<v[j]] += dp[i];
      }
      FOR(k, j+1, v.size()) {
        // 3人チーム　平均の条件を確認
        if(a[x] + a[v[j]] + a[v[k]] <= 3*K) {
          dp[i | 1<<x | 1<<v[j] | 1<<v[k]] += dp[i];
        }
      }
    }
  }

  cout << dp[(1<<n)-1] << endl;
  return 0;
}