CODE THANKS FESTIVAL 2018 F - Coins on the tree

解法

辞書順最小を求めるときは前から貪欲に決めていくのが典型。まずv[1]=1と決めてみたときに残りの木の状態と操作回数とコイン枚数について条件を満たせるのであればv[1]=1と決定してしまってよい。条件を満たさないのであればv[1]=2として同様に条件を満たすか判定を行う。この処理を前から順番に行っていくことで答えを求める。

v[i]=jと決定したときにi枚目より後のコインを頂点jの子孫に置くことは不可能である。コインを置く頂点を決めていくと木の使用できる範囲が狭まっていく。操作回数はその頂点の深さ、コインの枚数は置くごとに-1と遷移していく。

答えの列を決めていくのにO(NM)かかるためO(N+M)くらいで判定を行いたい。ある木とコインを置く枚数(=coin)が与えられたときに指定された操作回数(=ope)となるような操作手順が存在するかの判定を行えればよい。根の深さを1としたとき、深さdの頂点にコインを置く場合d回操作が必要になる。したがってcoin個の頂点を選んで深さの合計がopeとなるような選び方が存在するか？という問題になる。これは部分和問題なのでDPしたくなるが計算量的に不可能である。木の深さが飛び飛びの値にはならないことを利用して計算量を落としたい。これを利用するとコインをi枚置く場合の実現可能な操作回数はある区間一つになることがわかる。実現可能な操作回数の下限、上限は貪欲に求めることができO(N+M)程度で判定することができる。

#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 ll MOD = 1000000007;

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

  ll n, m, k;
  cin >> n >> m >> k;
  ll root = -1;
  vector<vector<ll>> g(n);
  REP(i, n) {
    ll p; cin >> p; p--;
    if(p == -1) {root = i; continue;}
    g[p].push_back(i);
  }

  vector<ll> depth(n);
  function<void(ll,ll)> init = [&](ll v, ll d) {
    depth[v] = d;
    for(auto to: g[v]) {
      init(to, d+1);
    }
  };
  init(root, 1);
//  cout << "depth=" << depth << endl;

  vector<bool> used(n);
  // ちょうどope回の操作でcoin枚のコインを置くことが可能か
  auto check = [&](ll ope, ll coin) {
//    cout << "ope=" << ope << " coin=" << coin << endl;
    vector<ll> cnt(n);
    function<void(ll, ll)> dfs = [&](ll v, ll d) {
      if(used[v]) return;

      cnt[d]++;
      for (auto to: g[v]) {
        dfs(to, d + 1);
      }
    };
    dfs(root, 0);

    ll sum = 0;
    REP(i, n) sum += cnt[i];
    if(sum < coin) return false;

    // 操作回数の下限を調べる
    ll idx = 0, lb = 0, co = coin;
    while(idx < n && co > 0) {
      ll tmp = min(cnt[idx], co);
      co -= tmp;
      lb += tmp * (idx + 1);
      idx++;
    }
    // 操作回数の上限を調べる
    idx = n-1, co = coin; ll ub = 0;
    while(idx >= 0 && co > 0) {
      ll tmp = min(cnt[idx], co);
      co -= tmp;
      ub += tmp * (idx+1);
      idx--;
    }

    return lb <= ope && ope <= ub;
  };

  if(!check(k, m)) {
    cout << -1 << endl;
    return 0;
  }

  function<void(ll)> dfs2 = [&](ll v) {
    used[v] = true;
    for(auto to: g[v]) {
      dfs2(to);
    }
  };

  vector<ll> ans(m);
  ll j = 0;
  REP(i, m) {
//    cout << "i=" << i << endl;
    REP(j, n) {
//      cout << "  j=" << j << endl;
      if(used[j]) continue;
      used[j] = true;
      if(check(k-depth[j], m-i-1)) {
        // j以下の部分木を全部trueに
        dfs2(j);
        k -= depth[j];
        ans[i] = j;
        break;
      }
      used[j] = false;
    }
  }

  REP(i, m) cout << ans[i]+1 << (i==m-1?'\n':' ');

  return 0;
}

自力で解けたけど遅い
これ400は詐欺じゃないか

ferinの競プロ帳

競プロについてのメモ

CODE THANKS FESTIVAL 2018 F - Coins on the tree

解法