TopCoder, SRM 628, Division 1, Level 2 : CircuitsConstruction

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13237&rd=16009

問題概要

　特殊な電気回路について考える。回路の構成は文字列で表される。
　まず、単一の素子は一つの回路である。これは、文字列 "X" として表される。
　また、二つの回路を接続したものも回路である。接続の方法にはタイプ A とタイプ B の二種類がある。タイプ A の場合、新しい回路の抵抗は接続された回路の抵抗の和になる。他方、タイプ B の場合、新しい回路の抵抗は、接続された回路の抵抗の内大きい方となる。回路の接続は、接続される回路を表す文字列を C1, C2 とすると、"A" + C1 + C2 及び "B" + C1 + C2 と表される。
　今、回路の構成を表す文字列 及び、所持している素子の抵抗を表す配列 が与えられる。 は、 番目の素子の抵抗を表し、 は に現れる文字 'X' の個数に等しい。素子は回路中の 'X' の部分に自由に配置できるとしたとき、回路全体の抵抗として可能な値の最大値を求めよ。

解法

　抵抗の計算の仕方から、回路全体の抵抗はいくつかの素子の抵抗の和になっていることが分かります。各接続部分について考えると、接続されている回路に含まれる素子の数をそれぞれ とすれば、タイプ A の場合は 個の素子の抵抗の和、タイプ B の場合は配置によりますが、数が多い方に高い抵抗の素子を詰め込むことで 個の素子の抵抗の和にできます。このように考えると、回路全体の抵抗に寄与する素子の数を、葉に近い方からからボトムアップに求めることができます。全体に寄与する素子の数が求まったら、抵抗の大きい素子から優先的に配置した方が得なので（かつ、タイプ B の接続の都合もある）、 の要素の内、大きいものから個数分を足し合わせた値が最適解となります。
　文字列 を何らかの方法で構文解析する必要がありますが、単純な文法なので DFS などでも大丈夫です。以下のコードでは再帰下降パーサとして実装しています。

コード

using PII = pair<int,int>;

#define ALL( c ) (c).begin(), (c).end()

#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

PII parse( const string &circuit, int pos = 0 )
{
	if ( circuit[ pos ] == 'X' )
	{
		return MP( 1, pos + 1 );
	}

	const char t = circuit[ pos ];
	PII res1 = parse( circuit, pos + 1 );
	PII res2 = parse( circuit, res1.snd );

	return MP( t == 'A' ? res1.fst + res2.fst : max( res1.fst, res2.fst ), res2.snd );
}


class CircuitsConstruction
{
public:
	int maximizeResistance( string circuit, vector <int> conductors )
	{
		sort( ALL( conductors ), greater<int>() );
		const int n = parse( circuit ).fst;
		return accumulate( conductors.begin(), conductors.begin() + n, 0 );
	}
};