SRM689 Div1 Easy "ColorfulGarden"
解法
それぞれの色の花において、その数がガーデンの幅(rowの長さ)を超えているものがあれば、どう配置しても隣り合ってしまうため配置不可となる。
逆にそうでない場合、以下のようにすれば必ず配置可能となる。
ガーデンの幅 = 7 aの数 = 3 bの数 = 6 cの数 = 5 とする。 数を降順にソートする。 b = 6 c = 5 a = 3 数が大きいものから順にジグザグに配置していく ①bを配置 row0 : b b b row1 : b b b ②cを配置 (ここでは右端に到達するため、左端からまたジグザグに配置しなおしている) row0 : b c b c b c row1 : c b c b b ③aを配置 row0 : b c b c b a c row1 : c b c b a b a 完成!
この方法では、「中途半端な位置から 数 = ガーデンの幅 の花を配置する」と隣り合ってしまいNGとなるが、数を大きいものから順に配置することによって、それを回避している。
ソースコード
class ColorfulGarden { public: vector<string> rearrange(vector<string> garden) { int n = garden[0].size(); // それぞれの色の数を数える int nums[26]; memset(nums, 0, sizeof(nums)); for (int i = 0; i < 2; i++) { for (int j = 0; j < n; j++) { nums[garden[i][j] - 'a']++; } } // nを超過しているかチェック for (int i = 0; i < 26; i++) { if (nums[i] > n) { vector<string> emptyList; return emptyList; } } // 大きいものから順に文字列結合する string str = ""; while(true) { int id = 0; int n = 0; for (int i = 0; i < 26; i++) { if (n < nums[i]) { id = i; n = nums[i]; } } if (n == 0) break; nums[id] = 0; for (int i = 0; i < n; i++) { str += id + 'a'; } } // 答えリストを作成 string str0 = ""; for (int i = 0; i < n; i++) { int id = i; if (i % 2 != 0) id += n; str0 += str[id]; } string str1 = ""; for (int i = 0; i < n; i++) { int id = i; if (i % 2 == 0) id += n; str1 += str[id]; } vector<string> ans; ans.push_back(str0); ans.push_back(str1); return ans; } };