WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};