SRM 507 div1 easy:CubeStickers

SRM 507の練習会に参加。結果はeasyとmedを通してそこそこでした。ただmedは再提出して150ptだったし計算量的にやや危なかったので反省ですね。

問題

TopCoder Statistics - Problem Statement

解法

問題の制約で色は6個以上あるので色が5種類以上あれば絶対OK。
3種類の場合は色の分布が2-2-2になっていればOK。それ以外は1つの色が3つ以上あるものが存在するのでNG。
4種類の場合は2種類以上の色が2つ以上の色を持てばOK。それ以外では1つの色が3つ以上あるものが存在するのでNG。

もっとスマートな解法もあるけど本番思いついたのはこれでした。

class CubeStickers {
public:
    string isPossible(vector <string> sticker) {
        map<string, int> M;
        int n = sticker.size();
        for (string s : sticker) {
            M[s]++;
        }
        if (M.size() >= 5) {
            return "YES";
        }
        if (M.size() < 3) return "NO";
        vector<int> v;
        for (auto p : M) {
            v.push_back(p.second);
        }
        sort(v.begin(), v.end());
        if (M.size() == 3) {
            if (v[0] >= 2 && v[1] >= 2 && v[2] >= 2) return "YES";
            else return "NO";
        }
        if (M.size() == 4) {
            if (v[2] >= 2) return "YES";
            return "NO";
        }
        return "YES";
    }
};