torus711 のアレ

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

Codeforces #156, Division 2, B : Code Parsing

概要

'x', 'y' からなる文字列について、以下の二つの操作ができる。

  1. 最も先頭に近い "yx" なる部分について、この二文字を入れ替える
  2. 最も先頭に近い "xy" なる部分について、この二文字を消去する

文字列 S について、次の次のような操作をする。

  1. 文字列に対して、上記の操作のいずれかをできる場合、2 に行き、そうでない場合は終了する
  2. 操作 1 が可能なら操作 1 を、そうでない場合は操作 2 を実行し、1 に戻る

最終的に得られる文字列を出力せよ。

解法

最終的に、'x' と 'y' のペアは全て消滅します。
従って、出現する個数の差の分だけ、多い方の文字を出力します。

コード

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

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

	string s;
	cin >> s;

	int xs = count( ALL( s ), 'x' ), ys = s.size() - xs;

	if ( xs < ys )
	{
		cout << string( ys - xs, 'y' ) << endl;
	}
	else
	{
		cout << string( xs - ys, 'x' ) << endl;
	}

	return 0;
}