ferinの競プロ帳

競プロについてのメモ

SRM730 div1 easy StonesOnATree

概要

各頂点iに重みw[i]が設定されているn頂点の木が与えられる。 ある頂点に1つ石を置くか、石を一つ取り除く操作を繰り返すゲームをする。ある頂点に石を置くとき、その頂点の子全てに石が置かれている必要がある。 ゲーム中に取りうる、石が置かれている頂点の重みの和の最大を最小化しろ。

n <= 1000 各頂点の子は2以下 頂点の親は自分より番号が小さい, w[i] <= w[i+1]

考えたこと

  • ドワコンのディスクの節約で既出では?
  • 制約が n <= 1000
  • 2分木なのとかをうまく使うんだろうなあと思いながら考える
  • ある頂点に石を置く時に子2つに置かれてないといけない
  • 片方の子に石を置くために根に近づけている最中にもう片方の子に向けて同時に近づけていった方がいい場合があるか?
  • 単調性でドワコンの想定誤答みたいなケースを作れる気がしないのでないと思い込む
  • 子v1,v2を持つ頂点vに石を置くためには下のパターンになりそう max(min(a,b), c)
    • v1に石を置くためにw[v1]、v2以下の部分木でもう片方の子に置くために必要な最大の瞬間 (a)
    • v2に石を置くためにw[v2]、v2以下の部分木でもう片方の子に置くために必要な最大の瞬間 (b)
    • w[v1] + w[v2] + w[v] (c)
  • 子が一つとか葉の場合は特に場合分けせずに適当に渡せばよさそう
  • 再帰的に探索していって出す
  • やばいケースがあるのか不安だったけど通った

するめで証明なしで投げるの怖い
遅かったけどちゃんと通せてよかった

解法

dp[v] = (頂点vを根とする部分木で取りうる最大の重み) dp[v] = (min(w[v1]+dp[v2], w[v2]+dp[v1]), w[v1] + w[v2] + w[v]) みたいな感じになるように探索する

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

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); }

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

VI g[1010];
ll dp[1010];
class StonesOnATree {
   public:
   int minStones(vector <int> p, vector <int> w)
  {
    int n = p.size()+1;
    memset(g, 0, sizeof(dp));
    REP(i, n) g[i].clear();
    REP(i, n-1) g[p[i]].PB(i+1);

    // v以下の部分木で取りうる瞬間的な最大
    function<ll(int)> dfs = [&](int v) -> int {
      ll ret = 0;
      if(g[v].size() == 0) return dp[v] = w[v];
      if(g[v].size() == 1) {
        chmax(ret, dfs(g[v][0]));
        dp[v] = w[v] + w[g[v][0]];
        chmax(ret, dp[v]);
        return ret;
      }
      ll vl = dfs(g[v][0]), vr = dfs(g[v][1]);
      dp[v] = max(min(vl + (ll)w[g[v][1]], vr + (ll)w[g[v][0]]), (ll)w[g[v][0]] + w[g[v][1]] + w[v]);
      chmax(ret, vl); chmax(ret, vr); chmax(ret, dp[v]);
      return ret;
    };

    dfs(0);

    ll ret = 0;
    REP(i, n) chmax(ret, dp[i]);
    return ret;
  }
};