Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2333-eddda0c8
この記事にトラックバックする(FC2ブログユーザー)

SRM560 DIV1 MEDIUM - DrawingPointsDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM560 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

最初,2次元平面上の幾つかの整数座標に点がある.
毎ターン以下の操作を行う.
 (x+0.5, y+0.5), (x+0.5, y-0.5), (x-0.5, y+0.5), (x-0.5, y-0.5) に点があるなら,(x, y)に点を追加する(すべてのx,yについて)
 そして,前のターンにあった点を全部消す
そのような操作を経て,何ターンか後の点の配置が(相対座標で)与えられる.(つまり,座標は平行移動しているかもしれない)
それは,最大で何ターン経過しているかを求める問題.
与えられる点の数は1以上50以下で,点の相対座標の絶対値は70以下の整数からなる.

解法

答えに対する2分探索をする.
kターン経過後に,与えられた配置にできるかどうかを判定するのは,
初期配置になくてはならない点はすぐに求まり,それのみからkターンだけシミュレーションして,
与えられた点のみ残れば,kターン後にそのような配置になれる.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int N = 300;
int mp[800][800], next[800][800];

class DrawingPointsDivOne {
public:
int maxSteps(vector <int> x, vector <int> y) {
  int i,j,k,n,t;
  int A, B, C, res;

  A = 0; B = 150;
  while(B>A){
    C = (A+B+1)/2;
    if(B-A > 30) C = (A+B+B+B+1)/4;
    
    rep(i,N) rep(j,N) mp[i][j] = 0;
    rep(k,x.size()) rep(i,C+1) rep(j,C+1) mp[x[k]+i+71][y[k]+j+71] = 1;

    rep(t,C){
      rep(i,N) rep(j,N) next[i][j] = 0;
      rep(i,N-1) rep(j,N-1) if(mp[i][j] && mp[i+1][j] && mp[i][j+1] && mp[i+1][j+1]) next[i][j] = 1;
      rep(i,N) rep(j,N) mp[i][j] = next[i][j];
    }

    k = 0;
    rep(i,N) rep(j,N) k += mp[i][j];
    if(k==x.size()) A=C; else B=C-1;
  }

  res = A;
  if(res == 150) res = -1;
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2333-eddda0c8
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。