Codeforces #173, B : Painting Eggs

問題文

http://codeforces.com/contest/282/problem/B

概要

二つの数列 A, G が与えられる。
各インデックスに於いて、いずれかの数列を選び、その要素を , の対応する方へ加算する。
最終的に とできる場合はその選び方を出力せよ。
できない場合は -1 を出力せよ。

解法

まず、A の総和を求め、それを すると、 です。
また、各インデックスについて、G を選ぶことにすれば だけこの差を縮めることができます。
更に制約より、一つの変更で許容範囲の外から反対側へ飛び抜けることはありません。
従って、差が許容範囲に収まるまで、先頭から G を選んだことにし続ければよいことになります。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n ), gs( n );
	REP( i, 0, n )
	{
		cin >> as[i] >> gs[i];
	}

	int diff = accumulate( ALL( as ), 0 );
	string res( n, 'A' );

	for ( int i = 0; i < n && 500 < diff; i++ )
	{
		if ( -500 <= diff - ( as[i] + gs[i] ) )
		{
			diff -= as[i] + gs[i];
			res[i] = 'G';
		}
	}

	if ( -500 <= diff && diff <= 500 )
	{
		cout << res << endl;
	}
	else
	{
		cout << -1 << endl;
	}

	return 0;
}