kmjp's blog

競技プログラミング参加記です

TopCoder SRM 679 Div1 Easy FiringEmployees

今年初SRM。Easy早解き+1Chalしたけどレート微減だった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14122

問題

社員番号0~Nの(N+1)人の会社がある。
0番の社員は社長である。
それ以外の社員はそれぞれ1人自分より若い番号M[i]の人をボスとする。
そのためボスと部下の関係は社長を根とした木を成す。

各社員の給料はS[i]であり、売上はP[i]である。
よって社員を雇う利益(損失)はP[i]-S[i]である。

各社員は任意に解雇することができる。
ただし解雇するとその部下もすべて連鎖的に解雇することになる。
残った社員の利益の総和を最大化せよ。

解法

各人の利益をC[i]=P[i]-S[i]とする。
葉から順に、「自分のSubTreeの利益の総和が負なら、自分以下を切る。そうでなければSubTreeの総和を親に加算する」という処理を行い、社長の総利益を答えればよい。

class FiringEmployees {
	public:
	int fire(vector <int> M, vector <int> S, vector <int> P) {
		int C[3050]={};
		for(int i=M.size();i>0;i--) C[M[i-1]]+=max(0,P[i-1]-S[i-1]+C[i]);
		return C[0];
	}
}

まとめ

一見O(N^2)っぽい制限だけどそんなことはなかった。