TopCoder SRM 730 Div1 Easy StonesOnATree、Div2 Hard StonesOnATreeDiv2

２完したけど遅かったのでレート減。
https://community.topcoder.com/stat?c=problem_statement&pm=14812
https://community.topcoder.com/stat?c=problem_statement&pm=14811

問題

根付き木が与えられる。
各点にはコストW[i]が降られており、根に近いほど小さい。

頂点に以下のルールで石を置いていくことを考える。

• 石を新たに置く場合、置く先の頂点が葉であるか、全ての子頂点にすでに石が置かれていなければならない。
• すでに置いた石を取り除いてもよい。

上記ルールの下で、根頂点に石が置かれた状態にすることを考える。
途中、石の置かれた頂点のコストの総和の最大値を最小化せよ。

なお、Div1では木が二分木だがDiv2ではその縛りがない。

解法

各頂点vに対し、dp(v) := vのみに石が置かれた状態にするまでに遷移する状態のコストの総和の最大値の最小値　を考える。
これを葉から順に求めていこう。

頂点vに石を置くには子頂点にもすべて石を置かなければならないので、まずdp(v)の最小値はそこになる。
あとは、vに石が置かれていないが子頂点すべてに石を置いた状態を作ることを考える。
あるvの子頂点をc0、c1、c2…と順に石を置いた状態を作る場合、W[i]は根に近いほど小さいのでc_iに石を置いた状態を作るにはc0～c(i-1)はすでに石が置かれた状態になるのがベストである。
この前提のもとで子頂点はどの順で石を置くのが良いか考えよう。

このような問題を考えるときは、隣接する候補のどちらを先にするのが良いかを考え、ソートするのが鉄板である。
今、仮にいくつか子頂点に石を置いた状態を考え、そこに至るコストの総和の最大値の最小値がSとする。
次に頂点aとbどちらを先に石を置くかを考える。
先にaを置くと、a,b両方置いた状態に至るまでのコストの総和の最大値はS+W[a]+dp(b)であり、bが先だとS+W[b]+dp(a)である。
よってW[a]+dp(b)＜W[b]+dp(a)、すなわちW[a]-dp[a]が小さい順に石を置くのが良い。
あとはシミュレートしていくだけ。

Div1Easyの場合は子頂点は最大２個なので、ソートとか考えず、dp(v) = min(W[a]+W[b]+W[v], W[a]+dp(b), W[b]+dp(a))で良い。

class StonesOnATree {
	public:
	int minStones(vector <int> p, vector <int> w) {
		vector<int> E[1010];
		int dp[1010];
		int N=p.size()+1;
		
		int i;
		FOR(i,N-1) E[p[i]].push_back(i+1);
		
		for(int i=N-1;i>=0;i--) {
			dp[i]=w[i];
			if(E[i].size()==1) dp[i]=max(w[i]+w[E[i][0]],dp[E[i][0]]);
			if(E[i].size()==2) dp[i]=max(w[i]+w[E[i][0]]+w[E[i][1]],min(max(dp[E[i][0]],w[E[i][0]]+dp[E[i][1]]),max(dp[E[i][0]]+w[E[i][1]],dp[E[i][1]])));
		}
		return dp[0];
		
	}
}

class StonesOnATreeDiv2 {
	public:
	int minStones(vector <int> p, vector <int> w) {
		vector<int> E[1010];
		int dp[1010];
		int N=p.size()+1;
		
		int i;
		FOR(i,N-1) E[p[i]].push_back(i+1);
		
		for(int i=N-1;i>=0;i--) {
			dp[i]=w[i];
			vector<pair<int,int>> V;
			FORR(e,E[i]) {
				dp[i]+=w[e];
				V.push_back({dp[e]-w[e],w[e]});
			}
			int ma=0;
			sort(ALL(V));
			reverse(ALL(V));
			int S=0;
			FORR(v,V) {
				ma=max(ma,S+v.first+v.second);
				S+=v.second;
			}
			dp[i]=max(dp[i],ma);
		}
		return dp[0];
		
	}
}

まとめ

本番二分木の条件を見落とした…。