torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #173, B : Painting Eggs

概要

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

解法

まず、A の総和を求め、それを Sum_a すると、| S_a - S_b | = Sum_a です。
また、各インデックスについて、G を選ぶことにすれば A_i + B_i だけこの差を縮めることができます。
更に制約より、一つの変更で許容範囲の外から反対側へ飛び抜けることはありません。
従って、差が許容範囲に収まるまで、先頭から 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;
}