Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-29練習

SRM 470 Div1 Easy 05:15  [http://www.topcoder.com/stat?c=problem_statement&pm=10915&rd=14153:title=SRM 470 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10915&rd=14153:title=SRM 470 Div1 Easy] - shnyaの参戦記録

貪欲にシミュレーションする問題。けど、とにかく大変。

本番だったら絶対撃墜されていた。


class DoorsGame {
public:
  int determineOutcome( string doors, int trophy ) {
    string a = doors.substr(0,trophy);
    string b = doors.substr(trophy);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    a.erase(unique(a.begin(), a.end()),a.end());
    b.erase(unique(b.begin(), b.end()),b.end());
    set<char> ma,mb,mall;
    set_intersection(a.begin(), a.end(),
                     b.begin(), b.end(), inserter(mall,mall.begin()));
    set_difference(a.begin(), a.end(),
                   b.begin(), b.end(), inserter(ma,ma.begin()));
    set_difference(b.begin(), b.end(),
                   a.begin(), a.end(), inserter(mb,mb.begin()));
    int res = 0;
    while(1){
      char af = a[0];
      if(ma.size() == 0){
        af = *(mall.begin());
        mall.erase(mall.begin());
      }else{
        af = *(ma.begin());
        ma.erase(ma.begin());
      }
      a.erase(remove(a.begin(), a.end(),af),a.end());
      b.erase(remove(b.begin(), b.end(),af),b.end());
      res++;
      if(a.size() == 0 && b.size() == 0) return 0;
      if(a.size() == 0) return res;
      if(b.size() == 0) return -res;

      char bf = b[0];
      if(mb.size() == 0){
        bf = *(mall.begin());
        mall.erase(mall.begin());
      }else{
        bf = *(mb.begin());
        mb.erase(mb.begin());
      }
      a.erase(remove(a.begin(), a.end(),bf),a.end());
      b.erase(remove(b.begin(), b.end(),bf),b.end());
      res++;
      if(a.size() == 0 && b.size() == 0) return 0;
      if(b.size() == 0) return -res;
      if(a.size() == 0) return res;
    }
    return res;
  }
};