Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-29練習

SRM 507 Div1 Easy 02:58  [http://www.topcoder.com/stat?c=problem_statement&pm=11315&rd=14436:title=SRM 507 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11315&rd=14436:title=SRM 507 Div1 Easy] - shnyaの参戦記録

あー、グラフ彩色問題だー、Easyで出るとは思わなんだと思って最初は、wikipediaとかいろいろ調べてみる。すぐにはわからないことがわかったので、とりあえずダメ元で問題に向き直ってみる。


最低3色*2あれば色塗りできるのか。一度3色塗って、残りの色で塗れるか試せばよさそう。まぁまぁ、これは間違うことないだろと思ったらミスしてた。。。

class CubeStickers {
public:
  string isPossible( vector <string> sticker ) {
    map<string,int> m;
    for(int i = 0; i < int(sticker.size()); ++i){
      m[sticker[i]]++;
    }
    vector<int> v;
    for(typeof(m.begin()) itr = m.begin();itr != m.end(); ++itr){
      v.push_back(itr->second);
    }
    sort(v.begin(),v.end(),greater<int>());
    if(v.size() < 3){
      return "NO";
    }
    for(int i = 0; i < 3; i++)
      v[i]--;
    v.erase(remove_if(v.begin(),v.end(),bind2nd(equal_to<int>(),0)),v.end());
    if(v.size() < 3){
      return "NO";
    }
    return "YES";
  }
};

ちなみに本番で書いたコードはこちら。頭の中では上のコードをイメージしてたのに、なんでこう書いちゃったのやら。。。

Challengeにどうぞ。

class CubeStickers {
public:
  string isPossible( vector <string> sticker ) {
    map<string,int> m;
    for(int i = 0; i < int(sticker.size()); ++i){
      m[sticker[i]]++;
    }
    vector<int> v;
    for(typeof(m.begin()) itr = m.begin();itr != m.end(); ++itr){
      v.push_back(itr->second);
    }
    sort(v.begin(),v.end());
    if(v.size() < 3){
      return "NO";
    }
    for(int i = 0; i < 3; i++)
      v[i]--;
    v.erase(remove_if(v.begin(),v.end(),bind2nd(equal_to<int>(),0)),v.end());
    if(v.size() < 3){
      return "NO";
    }
    return "YES";
  }
};