SRM507 Div1 easy CubeStickers

topcoder

問題概要

サイコロにステッカーをはる。
ステッカーの色がstringのvectorで与えられる。
隣り合う面が同じ色であってはいけない。
与えられた色のリストでそのような張り方が実現できるか答えよ。

解法

どうがんばっても、同じ色のステッカーは2枚張れない。
2枚以上同じ色があっても意味がない。
ある場所にステッカーを張ると、もう1枚張る同じ色のステッカーの場所は
一意であり、かつ、その場所は他の場所に張られたステッカーのもう一枚の場所にもならないので、
他の色のステッカーが2枚張ってあるからといって、別のステッカーが2枚張れなくなることはない。
よって、2枚以上同じ色のステッカーがあった場合は無視して、
その数が6枚を超えれば張ることが可能である。

ソース

#include<string>
#include<vector>
#include<map>
 
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
 
using namespace std;
class CubeStickers {
public:
  string isPossible(vector <string> sticker) {
    map<string, int>  M;
    FOR(it, sticker){
      M[*it]++;
    }
    int cnt = 0;
    FOR(it, M){
      if(it->second >= 2)cnt+=2;
      else cnt++;
    }
    if(cnt >= 6)return "YES";
    else return "NO";
  }
};