naoya_t@topcoder

GCJ 2010 Round 2 : C. Bacteria

16:34 |

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;
}