TopCoder SRM 628 Div1 Medium CircuitsConstruction

割とすんなり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=13237

問題

N個の抵抗があり、それぞれの抵抗値が与えられる。
また、N個の抵抗を2種類の組み合わせを(N-1)回用いて作成した回路が文字列で与えられる。

実世界とは異なり、２つの抵抗を組み合わせた場合の抵抗値は以下のようになる。

• A型で組み合わせた抵抗の抵抗値は両者の和となる。
• B型で組み合わせた抵抗の抵抗値は両者の最大値となる。

N個の抵抗の位置を互いに入れ替えられる場合、回路全体の抵抗値を最大化せよ。

解法

各抵抗の抵抗値を1と仮置きし、DFSで回路全体の抵抗値Xを求めてみると良い。
Xは、最大で抵抗何個分の抵抗値の和が答えになるかを示している。
よってあとはN個のうちから抵抗の大きい順にX個選択するだけ。

class CircuitsConstruction {
	public:
	int dfs() {
		char c=CC[cur++];
		
		if(c=='X') return 1;
		else if(c=='A') return dfs()+dfs();
		else return max(dfs(),dfs());
	}
	
	int maximizeResistance(string circuit, vector <int> conductors) {
		CC=circuit;
		cur=0;
		
		sort(conductors.begin(),conductors.end());
		return accumulate(conductors.rbegin(),conductors.rbegin()+dfs(),0);
	}
}

もっと短く書ける。

char* p;
int e(){char c=*p++;return c=='X'?1:(c=='A'?e()+e():max(e(),e()));}
int maximizeResistance(string c, vector<int>v){int l=v.size();p=&c[0];sort(&v[0],&v[l]);return accumulate(&v[l-1-e()],&v[l],0);}

まとめ

ちょっとEuler-tourとかで無駄に遠回りしたけど、最終的にすんなり解けて良かった。