Codeforces #712 Div.2 B. Memory and Trident

問題

codeforces.com

要約

R,L,U,D (Right, Left, Up, Down)の4つからなる文字列が与えられる. それぞれの方向に1ずつ移動する
Memoryさんは, 文字を書き換える能力がある.
文字を書き換えて, 最終的に原点に戻ってくるようにしたい.
なん文字書き換えればよいか. 無理のときは-1を出力する

やること

各文字の出現回数を数える.
RとL, UとDが両方共それぞれ偶数同士, 奇数同士ならばOK
また,
RとL, UとDが両方共それぞれ偶数奇数同士ならば, 一文字書き換えると上記の条件に当てはまるのでOK
それ以外の場合は-1を出力する.

偶数奇数同士の時は, max(R,L) -> min(U,D) に変化させてやる.

最後に, max(R,L) - ave(R,L) + max(U,D) - ave(U,D)の個数+前処理の変化回数(1か0)が答えになる

SourceCode

void solve() {
	string str = in();
	int mapping['Z'];
	mapping['R'] = 0;
	mapping['L'] = 1;
	mapping['U'] = 2;
	mapping['D'] = 3;

	vector<int> cnt(4);

	int res = 0;

	REP(i,str.size()) ++cnt[mapping[str[i]]];
	if (cnt[0] > cnt[1]) swap(cnt[0], cnt[1]);
	if (cnt[2] > cnt[3]) swap(cnt[2], cnt[3]);

	int lsb[4]; REP(i, 4) lsb[i] = (cnt[i] & 1);

	if (lsb[0] != lsb[1] and lsb[2] != lsb[3]) {
		--cnt[1]; ++cnt[2];
		++res;
	}
	else if(not(lsb[0] == lsb[1] and lsb[2] == lsb[3])){
		cout << -1 << endl;
		return;
	}

	cout << cnt[1] - (cnt[0] + cnt[1]) / 2 + cnt[3] - (cnt[2] + cnt[3]) / 2 + res << endl;
}