SRM 689 div1 easy: ColorfulGarden

問題

TopCoder Statistics - Problem Statement

2 行 n 列の文字群が与えられる。文字を適当に並び替えて, 「隣り合った文字同士は異なる」という性質を満たすように出来る場合, その例を一つ示せ。

解法

一種類の文字の並べ方を考えると, これは (a を並べるとして)
a0a0a
0a0a0
のように上下に交互に並べていくのが一番密に文字を詰め込めます。これ以上に文字を詰め込めることはないので,

一番出現回数の多い文字が n 回を超えている場合, 条件を満たすのは不可能

と言えます。逆に, これ以外の場合は, 次のようにして条件を満たす行列を構成できます。

• 並べる優先順位を決める(上下ジグザグを 2 回繰り返すイメージ)

1638
5274

• 出現回数が多いものから順にさっき決めた並べる順番順に並べる

a6a8
5a74

a6a8
ba7b

aca8
bacb

acad
bacb

class ColorfulGarden {
	public:
	vector <string> rearrange(vector <string> garden) {
		vector<pair<int, char> > cnt(26);
		for (int i = 0; i < 26; i++) cnt[i].second = (char)(i + 'a');
		int n = garden[0].size();
		for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) {
			cnt[garden[i][j] - 'a'].first++;
		}
		sort(cnt.rbegin(), cnt.rend());
		vector<string> ret;
		if (cnt[0].first > n) return ret;
		ret = garden;
		vector<pair<int, int> > ps(2 * n);
		{
			int now = 0;
			for (int i = 0; i < n; i++) {
				ps[i] = make_pair(now, i);
				now ^= 1;
			}
			now = 1;
			for (int i = 0; i < n; i++) {
				ps[i+n] = make_pair(now, i);
				now ^= 1;
			}
		}
		int now = 0;
		for (auto p : cnt) {
			int num = p.first;
			char c = p.second;
			for (int i = 0; i < num; i++) {
				ret[ps[now].first][ps[now].second] = c;
				now++;
			}
		}
		return ret;
	}
};