Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-06-07

GCJ 2010 Round 2 : A. Elegant Diamond

13:19 | GCJ 2010 Round 2 : A. Elegant Diamond - naoya_t@topcoder を含むブックマーク はてなブックマーク - GCJ 2010 Round 2 : A. Elegant Diamond - naoya_t@topcoder GCJ 2010 Round 2 : A. Elegant Diamond - naoya_t@topcoder のブックマークコメント

教訓

・問題はよく嫁

・処理しやすい座標系を考える

・斜め移動は(自分の場合)バグりやすいのでご用心

サンプルは通るけどA-smallでIncorrect、なコード

  • enhanced diamondの中心になりうるすべての点について、symmetricなdiamondが作れるか調べてるだけ。O(k^4)。
  • アイデアはコンテスト中に思いついたままだけど、実装するのに時間かかってるしA-small通らないしAからやってても駄目だったなと…泣
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

#define skiplf() do{char buf[256];cin.getline(buf,256);}while(0)

#define X 52
#define W (X*2+1)

char raw[W][W];
bool centerable[W][W];
int k,l,w;

#define VISUALIZE 1

bool test(int cy,int cx){
  rep(i,l){
    int dy=i-w, ay=cy*2-dy; /// (ax+dx)/2=cx, ax=2cx-dx
    if(ay<-X || X<ay) continue;
    rep(j,l){
      int dx=j-w, ax=cx*2-dx;
      if(ax<-X || X<ax) continue;
      if (abs(dx)+abs(dy)>w) continue;
      int d=raw[X+dy][X+dx], a=raw[X+ay][X+ax];
      if(d<0 || a<0) continue;
      if(d!=a) return false;
    }
  }
  return true;
}

int main(){
  int T;cin>>T;
  
  rep(t,T){
    rep(i,W) rep(j,W) { raw[i][j]=-1; centerable[i][j]=false; }

    cin>>k; l=k*2-1; w=k-1;
    skiplf();

    rep(i,l){
      char buf[256]; cin.getline(buf,256);
      int dy=i-w;
      rep(j,l){
        if(!buf[j]) break;
        if(buf[j]<'0' || '9'<buf[j]) continue;
        int dx=j-w;
        raw[X+dy][X+dx] = buf[j]-'0';
      }
    }

#ifdef VISUALIZE
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        int n=raw[X+dy][X+dx];
        if(n>=0)
          printf(" %d", n);
        else
          printf("  ");
      }
      cout<<endl;
    }
#endif

    // x:[-w,+w], y:[-w,+w]; abs(x)+abs(y)<=w
    int minarea = 99999999;
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        if (abs(dx)+abs(dy)>w) continue; // |dx|+|dy|<=w
        if (centerable[X+dy][X+dx] = test(dy,dx)) {
          int abx=abs(dx), aby=abs(dy);
          int k_ = k + abx+aby;
          minarea=min(minarea,k_*k_);
        }
      }
    }

#ifdef VISUALIZE
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        if (abs(dx)+abs(dy)>w) printf("  ");
        else printf(" %c", centerable[X+dy][X+dx] ? 'o' : 'x');
      }
      cout<<endl;
    }
#endif

    printf("Case #%d: %d\n", 1+t, minarea-k*k);
  }
  return 0;
}

間違い発見

  • あ、これでは(上下左右対称ではなく)点対称か…orz (nodchipさんのエントリを見て気がつきました)
  • というわけで上下左右対称に書き直したらsmall/largeともに通った。
  • 主な書き換えポイントはtest()、あと探索範囲をダイヤモンド内だけでなくダイヤモンドを含む(45度ずれた)正方形に広げた
bool test(int cy,int cx){ /// ★MODIFIED
  rep(i,l){
    int dy=i-w, ay=dy, by=cy*2-dy;
    rep(j,l){
      int dx=j-w, ax=cx*2-dx, bx=dx;
      int d=raw[X+dy][X+dx]; if (d<0) continue;
      int a=(-w<=ax && ax<=w && -w<=ay && ay<=w)? raw[X+ay][X+ax] : -1;
      if (a>=0 && d!=a) return false;
      int b=(-w<=bx && bx<=w && -w<=by && by<=w)? raw[X+by][X+bx] : -1;
      if (b>=0 && d!=b) return false;
    }
  }
  return true;
}

int main(){
  int T;cin>>T;
  
  rep(t,T){
    rep(i,W) rep(j,W) { raw[i][j]=-1; centerable[i][j]=false; }

    cin>>k; l=k*2-1; w=k-1;
    skiplf();

    rep(i,l){
      char buf[256]; cin.getline(buf,256);
      int dy=i-w;
      rep(j,l){
        if(!buf[j]) break;
        if(buf[j]<'0' || '9'<buf[j]) continue;
        int dx=j-w;
        raw[X+dy][X+dx] = buf[j]-'0';
      }
    }

#ifdef VISUALIZE
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        int n=raw[X+dy][X+dx];
        if(n>=0)
          printf(" %d", n);
        else
          printf("  ");
      }
      cout<<endl;
    }
#endif

    // x:[-w,+w], y:[-w,+w]; abs(x)+abs(y)<=w
    int minarea = 99999999;
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        // if (abs(dx)+abs(dy)>w) continue; /// ★REMOVED
        if (centerable[X+dy][X+dx] = test(dy,dx)) {
          int abx=abs(dx), aby=abs(dy);
          int k_ = k + abx+aby;
          minarea=min(minarea,k_*k_);
        }
      }
    }

#ifdef VISUALIZE
    rep(i,l){
      int dy=i-w;
      rep(j,l){
        int dx=j-w;
        printf(" %c", centerable[X+dy][X+dx] ? 'o' : '.'); /// ★CHANGED
      }
      cout<<endl;
    }
#endif
    printf("Case #%d: %d\n", 1+t, minarea-k*k);
  }
  return 0;
}

補足

if (centerable[X+dy][X+dx] = test(dy,dx)) {

とか書いてるけど if ( (c.. = t..) == true ) の意味ですからね。仕事コードではこういう書き方は厳禁ですよ!

GCJ 2010 Round 2 : B. World Cup 2010

14:57 | GCJ 2010 Round 2 : B. World Cup 2010 - naoya_t@topcoder を含むブックマーク はてなブックマーク - GCJ 2010 Round 2 : B. World Cup 2010 - naoya_t@topcoder GCJ 2010 Round 2 : B. World Cup 2010 - naoya_t@topcoder のブックマークコメント

後回しにしてたBが簡単すぎて泣きそう

教訓

もちつけ

コンテスト中の思考

  • そもそも何で後回しにしたかというと最初に個々のチームについて考えてしまったからで
  • それだと上の方で重複しててどうのこうのとか。(もう馬鹿かと。)
  • 再帰でなんとかなるよねきっと
  • 各チームについて、買わなければならないチケット数 = (P-見逃してもよい回数) だよね。そこまでは簡単
  • あるぇーどういう再帰で書いたらいいんだ(焦)
  • 後で考えるか…
  • その「後」が来なかった件

冷静に解き直したコード

  • 落ち着いて書いたら20分かからなかった
  • small/largeとも瞬殺&一発AC
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int P, es;
vector<int> M;
vector<vector<int> > prices;
vector<vector<int> > minm;

#define NON 1e9+1 // 100000x1000=1e9...

map<int,int> mm;

int sub(int lev,int idx,int seen){
  // 0..10<4>, 0..1023<10>, 0..10<4>
  int k=(lev<<14)|(idx<<4)|seen;
  if(found(mm,k)) return mm[k];
  
  if (seen < minm[lev][idx]) return mm[k]=NON;
  if (lev==P) return mm[k]=0;
  int skip_this = sub(lev+1,2*idx,seen) + sub(lev+1,2*idx+1,seen);
  int watch_this = prices[lev][idx] + sub(lev+1,2*idx,seen+1) + sub(lev+1,2*idx+1,seen+1);
  int min_ = min(skip_this, watch_this);
  return mm[k]=((min_ >= NON)? NON : min_);
}

int main(){
  int T;cin>>T;
  rep(t,T){
    mm.clear();
    
    cin>>P; es=1<<P;
    M.resize(es);
    rep(i,es) cin>>M[i];
    
    prices.resize(P); minm.resize(P+1); minm[P].resize(es);
    rep(i,es) minm[P][i]=P-M[i];
    for(int j=P-1;j>=0;--j){
      int es_j=1<<j;
      prices[j].resize(es_j); rep(i,es_j) cin>>prices[j][i];
      minm[j].resize(es_j); rep(i,es_j) minm[j][i]=max(minm[j+1][i*2]-1,minm[j+1][i*2+1]-1);
    }
    
    int ans=sub(0,0,0);
    printf("Case #%d: %d\n", 1+t, ans);
  }
  return 0;
}

GCJ 2010 Round 2 : C. Bacteria

16:34 | GCJ 2010 Round 2 : C. Bacteria - naoya_t@topcoder を含むブックマーク はてなブックマーク - GCJ 2010 Round 2 : C. Bacteria - naoya_t@topcoder GCJ 2010 Round 2 : C. Bacteria - naoya_t@topcoder のブックマークコメント

smallは簡単なシミュレーションで解ける。

  • B small/large + C smallだけ1時間36分以内に解ければ通っていた件。いまの自分に必要なのは落ち着くことと問題の捨て方

small版 (AC)

  • 気がつくべきこと:上と左の両方に誰かいないと発生しない=最初にバクテリアがいる座標をすべて含む長方形を考えると、その外へは決して広がって行かない
int main(){
  int C;cin>>C;
  rep(c,C){
    char mp[2][103][103]; memset(mp,0,sizeof(mp));
    
    int R;cin>>R;
    int xmin=100,xmax=0,ymin=100,ymax=0;
    rep(r,R){
      int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
      x1++; y1++; x2++; y2++;
      xmin=min(xmin,x1); xmax=max(xmax,x1);
      ymin=min(ymin,y1); ymax=max(ymax,y1);
      xmin=min(xmin,x2); xmax=max(xmax,x2);
      ymin=min(ymin,y2); ymax=max(ymax,y2);
      for(int x=x1;x<=x2;x++) for(int y=y1;y<=y2;y++) mp[0][x][y]=1;
    }

    int st=0;
    while(1){
      int s0 = st%2, s1 = (st+1)%2, cells = 0;
#ifdef VISUALIZE
      printf("step %d\n", st+1);
      for(int y=ymin;y<=ymax;y++) {
        for(int x=xmin;x<=xmax;x++) putchar('0'+mp[s0][x][y]);
        putchar('\n');
      }
#endif
      rep(x,103) rep(y,103) cells += (mp[s1][x][y] = mp[s0][x][y]);
      if (cells == 0) break;
      
      for(int x=xmin;x<=xmax;x++) {
        for(int y=ymin;y<=ymax;y++) {
          if(mp[s0][x][y]){
            if(mp[s0][x-1][y]==0 && mp[s0][x][y-1]==0) mp[s1][x][y]=0;
          } else {
            if(mp[s0][x-1][y]==1 && mp[s0][x][y-1]==1) mp[s1][x][y]=1;
          }
        }
      }
      st++;
    }
    printf("Case #%d: %d\n", 1+c, st);
  }
  return 0;
}

large対策版(途中)

  • 盤面をバクテリア満載長方形のブロックに区切ってlifeゲーム
  • smallで試すと #5,#50,#91,#100が通らない。漏れているパターンがありそう
  • 1ステップごとに進めてるのでlargeが不安 →(間違ってるけど)現状で2分前後で完了
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(__typeof__((c).begin()) i=(c).begin(); i!=(c).end(); i++)

#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))

typedef pair<int,int> ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define caar(x) (x).first.first
#define cdar(x) (x).first.second
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

typedef pair<ii,ii> box;

int main(){
  int C;cin>>C;
  rep(c,C){
    int R;cin>>R;
    int xmin=100,xmax=0,ymin=100,ymax=0;

    vector<int> x1(R),y1(R),x2(R),y2(R);
    set<int> xx,yx;
    rep(r,R){
      cin>>x1[r]>>y1[r]>>x2[r]>>y2[r];
      // 切れ目の座標を集めておく
      x2[r]++; y2[r]++;
      xx.insert(x1[r]); yx.insert(y1[r]);
      xx.insert(x2[r]); yx.insert(y2[r]);
    }
    // 切れ目を並べ替えて
    vector<int> x_(all(xx)); int xn=x_.size()-1;
    vector<int> y_(all(yx)); int yn=y_.size()-1;
    map<int,int> xm; rep(i,xn+1) xm[x_[i]]=i;
    map<int,int> ym; rep(i,yn+1) ym[y_[i]]=i;

    vector<int> wx(xn+1,1); rep(i,xn) wx[1+i]=x_[i+1]-x_[i];
    vector<int> wy(yn+1,1); rep(i,yn) wy[1+i]=y_[i+1]-y_[i];

    vector<vector<ii> > mp(xn+1,vector<ii>(yn+1,ii(0,0)));
    vector<vector<int> > full(xn+1,vector<int>(yn+1,1)); rep(x,xn) rep(y,yn) full[1+x][1+y] = wx[1+x]+wy[1+y]-1;
    rep(r,R){
      for (int x=xm[x1[r]]; x<xm[x2[r]]; ++x)
        for (int y=ym[y1[r]]; y<ym[y2[r]]; ++y)
          mp[1+x][1+y] = ii(full[1+x][1+y], 0);
    }

    int st=0;
    do {
      vector<vector<ii> > mp2=mp;
      int cnt=0; rep(x,xn) rep(y,yn) if (mp[1+x][1+y].first + mp[1+x][1+y].second) cnt++;
      if (cnt==0) break;

#ifdef VISUALIZE
        printf("st=%d¥n", st);
        FOR(y,1,yn) {
          FOR(x,1,xn)
              printf(" %2d", mp[x][y].first);
              //printf(" %2d/%2d/%2d", mp[x][y].first, mp[x][y].second, full[x][y]);
          cout << endl;
        }
#endif

      cnt=0;
      FOR(x,1,xn) FOR(y,1,yn) {
        if (mp[x][y].first > 0 && mp[x][y].second == 0 && mp[x][y].first < full[x][y]) {
          mp2[x][y].first++; cnt=max(cnt,1);
        }
        
        if (mp[x][y].first > 0) {
          // dismiss
          if ((mp[x-1][y].first==0 || wx[x-1]<=(-mp[x-1][y].second))
              && (mp[x][y-1].first==0 || wy[y-1]<=(-mp[x][y-1].second))) {
            mp2[x][y].second--;
            cnt=max(cnt,1);
          }
        } else {
          // gen
          if ((mp[x-1][y].first >= wx[x-1] && -mp[x-1][y].second < wx[x-1])
              && (mp[x][y-1].first >= wy[y-1] && -mp[x][y-1].second < wy[y-1])) {
            mp2[x][y] = ii(1,0);
            cnt=max(cnt,1);
          }
        }

        // regularize
        if (mp2[x][y].first + mp2[x][y].second == 0) mp2[x][y] = ii(0,0);
      }

      st += cnt;
      mp=mp2;
    } while (1);

    printf("Case #%d: %d¥n", 1+c, st);
  }
  return 0;
}

GCJ 2010 Round 2 : D. Grazing Google Goats

12:32 | GCJ 2010 Round 2 : D. Grazing Google Goats - naoya_t@topcoder を含むブックマーク はてなブックマーク - GCJ 2010 Round 2 : D. Grazing Google Goats - naoya_t@topcoder GCJ 2010 Round 2 : D. Grazing Google Goats - naoya_t@topcoder のブックマークコメント

長らくハマってしまい敗退の原因となった問題D。

比較的容易と思って飛びついたD-smallでしたが、結果が合わないのは精度の問題でした。long doubleで解決するような話。

教訓

浮動小数点数の精度とかたまには考えたほうがいいよ。long doubleかわいいよlong double

  • 1位のbmerryのコード(AC)をダウンロードしてsmallのデータを食わせてみたら自分のと随分違う値が出てる
  • あー。これってもしかしてdoubleの計算誤差かー!!!
  • double変数をlong doubleに置き換える。
    • sin→sinl,cos→cosl,hypot→hypotlなど
  • で、とりあえずsmallはAC
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

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

typedef long double ldouble;
typedef pair<ldouble,ldouble> dd;

int N,M;
vector<dd> p,q;

ldouble hypot(dd x1, dd x2){
  return hypotl(x1.first-x2.first, x1.second-x2.second);
}
ldouble yogen(ldouble a,ldouble b,ldouble c){
  return acosl((a*a+b*b-c*c)/(a*b*2));
}
ldouble ougi(ldouble r,ldouble th=M_PI*2){
  return th*r*r/2;
}
ldouble deg(ldouble rad){
  return 180.0*rad/M_PI;
}
ldouble area2(int m){
  dd qm = q[m];
  dd p0=p[0], p1=p[1];
  ldouble r0=hypot(p0,qm), r1=hypot(p1,qm), d=hypot(p0,p1);
  if(r0<r1) { swap(r0,r1); swap(p0,p1); } // r0 > r1に揃える
  ldouble theta=yogen(r0,r1,d);
  ldouble th0=yogen(r0,d,r1), th1=yogen(r1,d,r0);
  ldouble h=r0*sinl(th0);

  if (r0+r1==d) {
    return 0; // midpoint
//} else if (th1 <= M_PI/4) {
//  return ougi(r0,2*th0) + ougi(r1,2*th1) - d*h;
  } else if (r0<r1+d) {
    return ougi(r0,2*th0) + ougi(r1,2*th1) - d*h;
  } else {
    return ougi(r1);
  }
  
  return m;
}

int main(){
  int T;cin>>T; // S:1-100  L:1-10
  rep(t,T){
    p.clear(); q.clear();
    cin>>N>>M;
    rep(n,N){ double x,y; cin>>x>>y; p.pb( dd(x,y) ); } // S:2    L:2-5000
    rep(m,M){ double x,y; cin>>x>>y; q.pb( dd(x,y) ); } // S:1-10 L:1-1000

    printf("Case #%d:", 1+t);
    rep(m,M) printf(" %.9Lf", area2(m));
    printf("¥n");
  }
  return 0;
}
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100607