Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-22

SRM212 Div2 Hard: LargestCircle

| 04:27 | SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder SRM212 Div2 Hard: LargestCircle - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例(その2)。

  • とりうる中心&半径について全て試してみた
  • 普通にコンパイルするとTest Case #6で2.6秒かかったが、-O3 で161msec。余裕
  • 718.97points (19'25''), Passed System Test
class LargestCircle {
  int in(int x,int y,int r, int u,int v){
    return (u-x)*(u-x) + (v-y)*(v-y) - r*r;
  }
 public:
  int radius(vector<string> grid) {
    int h=sz(grid), w=sz(grid[0]);
    if (h==1 || w==1) return 0;
    int R = 0;
    for(int x=1;x<=w-1;x++){
      int dxmax=min(x,w-x);
      for(int y=1;y<=h-1;y++){
        int dymax=min(y,h-y);
        int rmax=min(dxmax,dymax);
        for(int r=rmax;r>=1;r--){
          bool ok=true;
          for(int u=0;u<w;u++){
            for(int v=0;v<h;v++){
              if(grid[v][u]=='#'){
                int a = in(x,y,r, u,v);
                int b = in(x,y,r, u+1,v);
                int c = in(x,y,r, u,v+1);
                int d = in(x,y,r, u+1,v+1);
                if ((a>=0 && b>=0 && c>=0 && d>=0) || (a<=0 && b<=0 && c<=0 && d<=0)) {
                } else {
                  ok=false; goto out;
                }
              }
            }
          }
       out:
          if (ok) R>?=r; // ←コンパイル時にwarning出るね
        }
      }
    }
    return R;
  }
};
  • >?= なのか <?= なのかぱっと分からないので両方試したのは内緒。
  • コンパイル時にwarning出るが構わない

LargestCircle.cpp: In member function ‘int LargestCircle::radius(std::vector<std::string, std::allocator<std::string> >)’:

LargestCircle.cpp:75: warning: minimum/maximum operators are deprecated

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090522