naoya_t@topcoder

SRM211 Div1 Medium: grafixMask

過去問, 練習, Tutorials | 00:28 |

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

• 問題がなかなか頭に入らなかった
• ニコ動をBGMにしながらは無理か
• いつもpriority_queue使うけど今日は普通のqueueで。合理的に使い分けているわけではない
• 214.27points (50'0''), passed system test

#define RC 240000
class grafixMask {
 public:
  vector<int> sortedAreas(vector<string> rectangles) {
    vector<int> wh(RC,0); // r*600+c
    int rem=RC;
    tr(rectangles,it){
      vector<int> rs = map_atoi(split(*it));
      for(int r=rs[0]; r<=rs[2]; r++){
        for(int c=rs[1]; c<=rs[3]; c++){
          int rc=r*600 + c;
          if(wh[rc]==0){ wh[rc]=-1; rem--; }
        }
      }
    }

    vector<int> ans;
    int room=1;
    while(rem){
      // find emptypoint
      int erc=-1;
      rep(rc,RC) if (wh[rc]==0){ erc=rc; goto found; }
      if (erc==-1) goto err;
   found:
      // flood fill
      queue<int> q;
      vector<bool> vac(RC,false);
      rep(rc,RC) if(wh[rc]==0) vac[rc]=true;
      q.push(erc); vac[erc]=false;
      while(!q.empty()){
        int rc=q.front(); q.pop();
        if(wh[rc]==0){ wh[rc]=room; rem--; }
        int r=rc/600, c=rc%600;
        if(1<=r && vac[rc-600]){ q.push(rc-600); vac[rc-600]=false;}
        if(r<=398 && vac[rc+600]){ q.push(rc+600); vac[rc+600]=false;}
        if(1<=c && vac[rc-1]){ q.push(rc-1); vac[rc-1]=false;}
        if(c<=598 && vac[rc+1]){ q.push(rc+1); vac[rc+1]=false;}
      }
      room++;
    }
    ans.resize(room-1); rep(i,room-1) ans[i]=0;
    rep(rc,RC){
      if (wh[rc]>0) ans[wh[rc]-1]++;
    }
    sort(all(ans));
 err:
    return ans;
  }
};

SRM211 Div1 Easy: grafixCorrupt

過去問, 練習 | 22:56 |

• 241.58points (5'19'' ...もっと速く!!)
• passed system test

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

class grafixCorrupt {
  int match(const string& s1, const string& s2){
    int l=sz(s1),c=0;
    rep(i,l){
      if(s1[i]==s2[i]) c++;
    }
    return c;
  }
  
 public:
  int selectWord(vector <string> dictionary, string candidate) {
    int n=sz(dictionary);
    int at=-1,sc=0;
    rep(i,n){
      int s=match(dictionary[i],candidate);
      if (s>sc) {sc=s; at=i;}
    }
    return at;
  }
};