概要
'x', 'y' からなる文字列について、以下の二つの操作ができる。
- 最も先頭に近い "yx" なる部分について、この二文字を入れ替える
- 最も先頭に近い "xy" なる部分について、この二文字を消去する
文字列 S について、次の次のような操作をする。
- 文字列に対して、上記の操作のいずれかをできる場合、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; }