Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM521 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

2次元平面上にk個 (40以下) の点が与えられる.
各点の座標は整数で,絶対値は10^8以下.
点の集合がn-squaredとは,以下の条件を満たす,一辺の長さがnの正方形が存在すること:
 集合の点をすべて,その正方形の周上または内部に含み,集合の点でない点は1つも含まない
 各辺がx軸かy軸に平行
10^8以下の整数nlow,nhighが与えられるので,与えられた点の集合で,それがm-squaredになるようなnlow以上nhigh以下のmが存在するものの数を求める問題.

解法

まず,答えの可能性のある集合を列挙する.
x座標の範囲 (下端と上端),y座標の範囲で4重ループを回す.ここまででO(40^4).
後は,それが,nlow以上,nhigh以下の正方形で囲めるかを判定して,囲めるなら,その点の集合を答えに入れる.
中にある点の集合を愚直に求めれば,全体でO(40^5).

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

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

#define ll long long

class RangeSquaredSubsets {
public:
long long countSubsets(int nlow, int nhigh, vector <int> x, vector <int> y) {
  int i,j,k,n;
  int x1, x2, y1, y2;
  int x_min, x_max;
  int y_min, y_max;
  set<ll> s;
  set<int> Xset, Yset;
  set<int>::iterator it;
  vector<int> X, Y;

  s.insert(0LL);

  n = x.size();
  rep(i,n){
    Xset.insert(x[i]);
    Yset.insert(y[i]);
  }

  for(it=Xset.begin(); it!=Xset.end(); it++) X.push_back(*it);
  for(it=Yset.begin(); it!=Yset.end(); it++) Y.push_back(*it);

  rep(x1,X.size()) REP(x2,x1,X.size()){
    x_min = X[x2] - X[x1];
    x_max = 1000000000;
    if(x1-1 >= 0 && x2+1 < X.size() && x_max > X[x2+1] - X[x1-1] - 1) x_max = X[x2+1] - X[x1-1] - 1;

    if(x_min < nlow)  x_min = nlow;
    if(x_max > nhigh) x_max = nhigh;

    if(x_min > x_max) continue;

    rep(y1,Y.size()) REP(y2,y1,Y.size()){
      y_min = Y[y2] - Y[y1];
      y_max = 1000000000;
      if(y1-1 >= 0 && y2+1 < Y.size() && y_max > Y[y2+1] - Y[y1-1] - 1) y_max = Y[y2+1] - Y[y1-1] - 1;

      if(y_min < nlow)  y_min = nlow;
      if(y_max > nhigh) y_max = nhigh;

      if(y_min > y_max) continue;
      if(y_min > x_max) continue;
      if(y_max < x_min) continue;

      {
        ll vec = 0;
        rep(i,n){
          if(X[x1] <= x[i] && x[i] <= X[x2]); else continue;
          if(Y[y1] <= y[i] && y[i] <= Y[y2]); else continue;
          vec |= (1LL<<i);
        }
//        printf("%d %d : %d %d : %lld\n",x1,x2,y1,y2,vec);
        s.insert(vec);
      }
    }
  }

  return s.size() - 1;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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