Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM558 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

x軸上にR個の赤い点,x軸より上にB個の青い点が与えられる.(R, Bは300以下)
問題文の図のように,赤い点を2個,青い点を2個選んで,きつね耳のような形にする方法は何通りあるか求める問題.
条件は,内側の三角形は,外側にふれてはならず,それぞれの三角形について,青い点は赤い2点の中になければいけないなど.
座標は正整数で10000以下.

解法

青い2点の選び方は全部試す.
すると,2点を結ぶ直線とx軸の交点,および,2点のx座標を境目に,赤い点がどの三角形にしようできるかが決まる.
あとは適当にそれぞれに使用出来る赤い点の数を数えて,組み合わせの数を足していく.
赤い点を愚直に数えてO(B^2 R),赤い点を累積和とか用意しておけばO(B^2 + R + 座標の最大値).

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

int read_int_from_char(const char in[],int l,int ret[]){
  int i,n,fg,mfg;
  if(l<0) {for(i=0;;i++) if(in[i]<' ') break; l=i;}
  n=0; fg=0; mfg=0; ret[0]=0;
  rep(i,l+1){
    if(in[i]=='-'){mfg=1; continue;}
    if(isdigit(in[i])){ret[n]=ret[n]*10+in[i]-'0'; fg=1; continue;}
    if(!fg) continue;
    fg=0; if(mfg){ret[n]=-ret[n]; mfg=0;}
    ret[++n]=0;
  }
  return n;
}

int sumR[20010];
int get(int a, int b){ if(a>b) return 0; if(a < 0) a = 0; if(b > 20000) b = 20000; return sumR[b+1] - sumR[a]; }

class Ear {
public:
ll getCount(vector <string> redX_baka1, vector <string> blueX_baka1, vector <string> blueY_baka1) {
  int i,j,k;
  string redX_baka, blueX_baka, blueY_baka;
  int redX[400], blueX[400], blueY[400], red, blue;
  int b1, b2;
  ll left, right, t;
  int dY, cX, abX, diff;
  ll res = 0;

  rep(i,redX_baka1.size()) redX_baka += redX_baka1[i];
  rep(i,blueX_baka1.size()) blueX_baka += blueX_baka1[i];
  rep(i,blueY_baka1.size()) blueY_baka += blueY_baka1[i];

  red = read_int_from_char(redX_baka.c_str(), -1, redX);
  blue = read_int_from_char(blueX_baka.c_str(), -1, blueX);
  blue = read_int_from_char(blueY_baka.c_str(), -1, blueY);

  rep(i,20010) sumR[i] = 0;
  rep(i,red) sumR[redX[i]+1]++;
  REP(i,1,20010) sumR[i] += sumR[i-1];

  rep(b1,blue) rep(b2,blue){
    if(blueY[b1] <= blueY[b2]) continue;
    dY = blueY[b1] - blueY[b2];

    abX = blueX[b2] - blueX[b1];
    if(abX < 0) abX = -abX;
    diff = abX * blueY[b2] / dY;

    if(blueX[b1] >= blueX[b2]){
      cX = blueX[b2] - diff;
      t = get(0, cX - 1);
      left = t * (t-1) / 2 + get(cX, blueX[b2]-1) * t;
      t = get(blueX[b1]+1, 19999);
      right = t * (t-1) / 2 + get(blueX[b2]+1, blueX[b1]) * t;
    } else {
      cX = blueX[b2] + diff;
      t = get(0, blueX[b1]-1);
      left = t * (t-1) / 2 + get(blueX[b1], blueX[b2]-1) * t;
      t = get(cX+1, 19999);
      right = t * (t-1) / 2 + get(blueX[b2]+1, cX) * t;
    }

    res += left * right;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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