Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-05-29SRM507 Div1

SRM507 Div1 250 CubeStickers

| 14:02 | SRM507 Div1 250 CubeStickers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM507 Div1 250 CubeStickers - SRM diary(Sigmar) SRM507 Div1 250 CubeStickers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーんうーん・・普通に考えれば3色で塗り分け可能だよな

それから、1色で3枚以上あっても意味ない。同じ色は対面にしか貼れないから。

ということは、、3色未満ならNO

3色以上あるとき、、1枚しかないやつはどうするか・・

1枚しかないのは2つ組み合わせれば1色×2枚の扱いにできるから、2色以上の枚数と1色の枚数を適当に数えればいいや

書いた→サンプル通った→提出

そこそこ早くできた。


ソースコード

class CubeStickers {
public:
	string isPossible(vector <string> sticker) {
		string res;
		map <string, int> mp;
		int n=sticker.size();

		for(int i=0; i<n; i++) mp[sticker[i]]++;

		vector <int> vi;
		for(map <string, int>::iterator mpi=mp.begin(); mpi!=mp.end(); mpi++) vi.push_back(mpi->second);

		sort(vi.begin(), vi.end(), greater <int>());
		if(vi.size()<3) return "NO";
		int cnt=0;
		for(int i=0; i<3; i++) {
			if(vi[i]<2) cnt++;
		}
		if(cnt+3>vi.size()) return "NO";
		return "YES";
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110529