スポンサーサイト

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

TCO11 Marathon Round 2

2011/06/02 ~ 06/16
TCO11 Marathon Round 2 の参加記録

Tags : プログラミング TopCoder MM

Round 1 で、スーパー適当なコードを書いてギリギリ通過してしまったので、Round 2 は結構がんばって参加した。
といっても、マラソン中に POJ の問題を解いたりしていたし、本当にがんばってた人にしてみれば 「全然やってないじゃん」 ってことになると思う。

結果

222 人中 123 位。 retire.

思考過程

マラソン中に作っていたメモを貼り付けただけ。
2011/06/03 スタート

何もしないコードを submit.
もちろん score 0.00 点。
54 位 (最下位)

1 つの polygon あたりの頂点数は多いほうがいい。
score に 2 乗で利いてくるから。
でも、頂点数が多い polygon をみつけるのは難しそう。

テストケースの作り方が作為的。
頂点数は [50,500) か [500,5000] のどちらかの範囲にある。確率 1/2.
一見、[50,5000] 上の一様分布に見えるがそうではない。
小さい値が出やすくなっている。
頂点数によって処理を場合わけするのがいいだろう。

とりあえず、手当たりしだい polygon を見つけるようにしよう。
まずは、三角形に限定する。

gettimeofday を使って 10 秒間めいっぱい探索するようにした。
3 頂点はランダムに選ぶだけ。御用達の xorshift を使う。

submit できないので、微最適化。
・距離ではなく、距離の 2 乗で比較。
・gettimeofday を 8 回に 1 回だけ呼ぶようにした。
・定数はあらかじめ計算しておく。

D, L に関する条件を満たしやすいようなサンプリング方法を考えるのもいいかも。

submit.
19.16 点。46 位。

使った点を配列の最後にスワップして、以降はサンプリングされないようにした。
set などを使っていないので高速。

3 秒だけ走らせても 10 秒いっぱいまで走らせても結果はほとんど変わらない。
つまり、後のほうになるとぜんぜんマッチしていないということ。

submit.
28.59 点。45 位。
history1.cpp

頂点数と 2 点を指定したら、多角形は 2 通りに決まる。
摂動があるので、そこんとこは工夫しないといけないけど。
このことを使えば、格段に早く polygon が見つけられると思う。
簡易な実装を考える必要がある。

今日は終わり。

2011/06/07 1:00 から再開
18.52 点。107 位まで落ちてた。

2 点を指定して、その線分を 1 辺とする正多角形を探す方針でやってみる。
n-2 個の頂点は、使える頂点全部に対して、理想の位置に一番近いものを採用した。
これを愚直なループでやってるので (特に、頂点数が多いときは) 遅い。
なんとかしたい。
ぜんぜんバグが取れないと思ったら、ベクトルの回転の式が間違ってた。
この方針で三角形だけを探すと、以前の方針より良くはならなかった。
頂点数が 1000 以上あるケースでは、6, 7 角形もそこそこみつかる。

gettimeofday を 32 回に 1 回呼ぶようにした。

チューンすればもっと良くなるだろうけど、とりあえず、
7 角形 : 3 sec
6 角形 : 2 sec
5 角形 : 2 sec
4 角形 : 2 sec
3 角形 : 0.9 sec
で提出してみる。
78.20 点。20 位。87 人抜き!!
history2.cpp

今 5:00.
寝よう。

2011/06/13 18:00 マラソン再開
61.88 点。68 位まで落ちていた。

問題文をよく読むと、点の座標は [0,700) x [0,700) の範囲にあるらしい。
理想の頂点に近い頂点を見つける処理が、線形探索していて遅いので、それを改善する。
Volonoi Diagram は実装重すぎなので、Quad Tree を書く。
Quad Tree の深さは高々 lg 700 < 10.
点の追加はないが、削除は必要。

double を float にしても精度は十分で、ちょっと速くなるかも。

翌日 0:50.
ようやくクエリ処理まで書きあがった。ランダムケースで verified.
クエリの部分問題で、円と(軸に平行な)長方形の交差判定が出てきてびっくりした。
次は削除処理を書かないといけない。

1:15 削除処理が書きあがった。ちょっとだけ verified. 多分あってる。
そんなことなかった。同じ点を 2 回消そうとしたら落ちる。

3:20 all bugs fixed.
実行してみたけどあまりよくならない :'(
O(log n) ではあるけど、QuadTree::query が多分遅い。交差判定とかしてるし。
頂点数 >= 6 のときは QuadTree の方がたくさん多角形を作れている。
線形探索とのハイブリッドをやってみよう。
それでもよくならない。

入力データの性質によって、頂点数の多い多角形が見つかる数がぜんぜん違う。

一応、ハイブリッド版を提出する。
時間配分は
8 角形 : 3 sec
7 角形 : 3 sec
6 角形 : 2 sec
5 角形 : 1 sec
4 角形 : 0.5 sec
3 角形 : 0.4 sec
Example だと良くなるのも悪くなるのもある程度。
提出前は 59.78 点。74 位。
60.81 点。69 位。
history3.cpp
誤差。

どう時間配分すればどういうときに良くなるか、統計を取るのがいい。
寝てる間に PC にがんばってもらった。
シェルスクリプトを書いて seed = 1, ..., 100 のときのデータを採った。
点の総数 NP に対して、n 角形がいくつ見つかったかの割合。
8 角形が作れる割合と NP, nD の間に相関はまったく見られなかった。
データをさらに詳しく見る必要がある。

データの相関係数を調べてみたが、作れる 8 角形の数との相関はなさそうだった。

2011/06/15 15:00
一辺の長さが長い多角形から順に見つけていくようにしたら悪くなった。提出しない。
探す多角形の頂点数を動的に変化させた (n回連続で見つかったらn_vertex++とか) が悪くなった。提出しない。

seed 6 なんかは、6 角形以上がほとんどみつからないので、
4, 5 角形を探す時間を長くしたら Score が 1000 点くらいあがった。
本質的な改善案が思いつかないので、時間配分を変えて submit する。
提出前 54.16 点。104 位。
7 角形 : 3 sec
6 角形 : 2 sec
5 角形 : 2 sec
4 角形 : 2.2 sec
3 角形 : 0.7 sec
53.92 点。104 位。だめ。

点の総数が 250 個以下のときは、5 sec のシミュレーションを 2 回やっていい方を出すようにした。
時間配分は history3.cpp と同じで
8 角形 : 3 sec
7 角形 : 3 sec
6 角形 : 2 sec
5 角形 : 1 sec
4 角形 : 0.5 sec
3 角形 : 0.4 sec
提出前は 53.33 点。108 位。
54.39 点。105 位。
history4.cpp

一辺の長さが短い多角形のほうが見つかりやすいかと思って、
2 点目は 1 点目に近い点がサンプリングされやすくした。悪くなった。

50.20 点。123 位で終了。
T シャツほしかった...


感想

なぜこの競技がマラソンと名づけられているのかが少し分かった気がする。
良いスコアを出すためには、アルゴリズム力や実装力だけでなくて、体力や持久力、さらには情報収集能力がいる。

結果は残念だったけど、四分木も実装できたし、かなり楽しかった。

ソースコード

#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<sys/time.h>

#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

#define dbgi(a) fprintf(stderr,"%s = %lld\n",#a,(long long)(a));
#define dbgf(a) fprintf(stderr,"%s = %.2f\n",#a,(double)(a));
#define dbgs(a) fprintf(stderr,"%s = %s\n",#a,(a));

using namespace std;

typedef long long ll;

const int INF=1<<29;
const double PI=acos(-1);

unsigned xor128(){
static unsigned x=123456789,y=362436069,z=521288629,w=88675123;
unsigned t=x^(x<<11);
x=y; y=z; z=w;
return w=(w^(w>>19))^(t^(t>>8));
}

ll gettime(){
static timeval tv;
gettimeofday(&tv,NULL);
return tv.tv_sec*1000000LL+tv.tv_usec;
}

#define sq(x) (x)*(x)
#define sqsum(x,y) (sq(x)+sq(y))
#define round(x) (int)(x+0.5)

struct Point{
int x,y;
Point(){}
Point(int X,int Y):x(X),y(Y){}
};

class QuadTree{
struct Node{
Point p;
int t,l,b,r;
Node *child[4]; // topright, topleft, bottomleft, bottomright
Node(int T,int L,int B,int R):t(T),l(L),b(B),r(R){
child[0]=child[1]=child[2]=child[3]=NULL;
}
bool isleaf()const{
return !child[0] && !child[1] && !child[2] && !child[3];
}
};
Node *root;

void maketree(Node *&u,int t,int l,int b,int r,const vector<Point> &ps){
u=new Node(t,l,b,r);

int m=ps.size();
if(m==1){ u->p=ps[0]; return; }

int n[4]={},xmid=(l+r)/2,ymid=(t+b)/2;
rep(i,m){
if(ps[i].y<ymid){
if(ps[i].x>=xmid) n[0]++;
else n[1]++;
}
else{
if(ps[i].x< xmid) n[2]++;
else n[3]++;
}
}

vector<Point> ps2[4];
rep(i,4){
ps2[i].resize(n[i]);
n[i]=0;
}
rep(i,m){
if(ps[i].y<ymid){
if(ps[i].x>=xmid) ps2[0][n[0]++]=ps[i];
else ps2[1][n[1]++]=ps[i];
}
else{
if(ps[i].x< xmid) ps2[2][n[2]++]=ps[i];
else ps2[3][n[3]++]=ps[i];
}
}

if(n[0]>0) maketree(u->child[0],t,xmid,ymid,r,ps2[0]);
if(n[1]>0) maketree(u->child[1],t,l,ymid,xmid,ps2[1]);
if(n[2]>0) maketree(u->child[2],ymid,l,b,xmid,ps2[2]);
if(n[3]>0) maketree(u->child[3],ymid,xmid,b,r,ps2[3]);
}

void killtree(Node *u){
rep(i,4) if(u->child[i]) killtree(u->child[i]);
delete u;
}

// 円 (q, R2) と u に対応する矩形が共通部分を持つかどうかを判定
bool intersect(const Point &q,const Node *u,int R2){
const int &t=u->t,&l=u->l,&b=u->b,&r=u->r,&x=q.x,&y=q.y;
// q is in the rectangle
if(t<=y && y<b && l<=x && x<r) return true;

// some vertices are in the circle
if(sqsum(l-x,t-y)<=R2 || sqsum(l-x,b-y)<=R2
|| sqsum(r-x,t-y)<=R2 || sqsum(r-x,b-y)<=R2) return true;

// some edges intersect the circle
if(t<=y && y<b){
int x1=(x<l?l-x:x-l);
int x2=(x<r?r-x:x-r);
int xmin=(x1<x2?x1:x2);
return sq(xmin)<=R2;
}
if(l<=x && x<r){
int y1=(y<t?t-y:y-t);
int y2=(y<b?b-y:y-b);
int ymin=(y1<y2?y1:y2);
return sq(ymin)<=R2;
}

return false;
}

Point query(const Point &q,const Node *u,int &R2){
if(u->isleaf()) return u->p;

Point ans(INF,0);
rep(i,4) if(u->child[i] && intersect(q,u->child[i],R2)) {
Point tmp=query(q,u->child[i],R2);
if(tmp.x<INF){
int d2=sqsum(tmp.x-q.x,tmp.y-q.y);
if(d2<R2) R2=d2;
if(ans.x==INF || d2<sqsum(ans.x-q.x,ans.y-q.y)) ans=tmp;
}
}
return ans;
}

// return true <=> delete u
bool erase(const Point &q,Node *&u){
if(u->isleaf()){
if(q.x==u->p.x && q.y==u->p.y){
delete u;
u=NULL;
return true;
}
return false;
}

int i;
for(i=0;i<4;i++) if(u->child[i]) {
int &t=u->child[i]->t,&l=u->child[i]->l,&b=u->child[i]->b,&r=u->child[i]->r;
if(t<=q.y && q.y<b && l<=q.x && q.x<r) break;
}
if(i<4 && erase(q,u->child[i])){
for(i=0;i<4;i++) if(u->child[i]) break;
if(i==4){
delete u;
u=NULL;
return true;
}
}
return false;
}

void print(const Node *u){
if(u->isleaf()) fprintf(stderr,"(%d, %d)\n",u->p.x,u->p.y);
else rep(i,4) if(u->child[i]) print(u->child[i]);
}

public:
QuadTree(const vector<Point> &ps):root(NULL){
maketree(root,0,0,700,700,ps);
}

~QuadTree(){ if(!root) killtree(root); }

Point query(const Point &q){
int inf=INF;
if(!root) return Point(inf,0);
else return query(q,root,inf);
}

void erase(const Point &q){
if(!root) return;
if(erase(q,root)) root=NULL;
}

void print(){ if(root) print(root); }
};

class QualityPolygons{
int t_limit8,t_limit7,t_limit6,t_limit5,t_limit4,t_limit3;

vector<string> solve(vector<int> points,int sidesDiff,int radiiDiff){
const ll t_ini=gettime();
const double sidesRatio=sq(1-sidesDiff/100.0);
const double radiiRatio=sq(1-radiiDiff/100.0);

int n=points.size()/2;
vector<Point> ps(n);
static int x[5000],y[5000],f[700][700];
rep(i,n){
ps[i].x=x[i]=points[2*i];
ps[i].y=y[i]=points[2*i+1];
f[y[i]][x[i]]=i; // f は x[idx[i]] と y[idx[i]] から idx0[i] を得る逆写像
}

QuadTree qt(ps);

double cosine[10],sine[10];
rep(i,10){
cosine[i]=cos(2*PI/i);
sine[i]=sin(2*PI/i);
}

int n_unused=n;
static int unused[5000];
rep(i,n) unused[i]=i;

int n_vertex=8;
ll t_fin,deltat;
vector<string> ans;
for(int t=0;n_unused>=3;t++){
if((t&127)==0){
t_fin=gettime();
deltat=t_fin-t_ini;
if (deltat<t_limit8);
else if(deltat<t_limit7) n_vertex=7;
else if(deltat<t_limit6) n_vertex=6;
else if(deltat<t_limit5) n_vertex=5;
else if(deltat<t_limit4) n_vertex=4;
else if(deltat<t_limit3) n_vertex=3;
else break;
}

// idx : 入力で与えられた points の添え字
// idx0 : unused[] の添え字, unused[idx0[i]]==idx[i]
static int idx[10],idx0[10];
idx0[0]=xor128()%n_unused;
idx0[1]=xor128()%n_unused;
idx[0]=unused[idx0[0]];
idx[1]=unused[idx0[1]];
if(idx[0]==idx[1]) goto FAILED;

static double x_ideal[10],y_ideal[10];
rep(i,2){
x_ideal[i]=x[idx[i]];
y_ideal[i]=y[idx[i]];
}
for(int i=2;i<n_vertex;i++){
double deltax=x_ideal[i-1]-x_ideal[i-2],deltay=y_ideal[i-1]-y_ideal[i-2];
x_ideal[i]=x_ideal[i-1]+deltax*cosine[n_vertex]-deltay*sine[n_vertex];
y_ideal[i]=y_ideal[i-1]+deltax*sine[n_vertex]+deltay*cosine[n_vertex];
}

for(int i=2;i<n_vertex;i++){
if(n_vertex>=6){
Point q=qt.query(Point(round(x_ideal[i]),round(y_ideal[i])));
if(q.x==INF) goto FAILED;
idx0[i]=f[q.y][q.x];
}
else{
rep(j,n_unused){
const double d1=sqsum(x[unused[ j ]]-x_ideal[i],y[unused[ j ]]-y_ideal[i]);
const double d2=sqsum(x[unused[idx0[i]]]-x_ideal[i],y[unused[idx0[i]]]-y_ideal[i]);
if(j==0 || d1<d2) idx0[i]=j;
}
}
idx[i]=unused[idx0[i]];
}
rep(i,n_vertex) rep(j,i) if(idx0[i]==idx0[j]) goto FAILED;

// 重心と辺の長さに関する条件のチェック
{
double gx=0,gy=0;
rep(i,n_vertex){
gx+=x[idx[i]];
gy+=y[idx[i]];
}
gx/=n_vertex,gy/=n_vertex;

double Dmax=0,Dmin=1e300;
double Lmax=0,Lmin=1e300;
rep(i,n_vertex){
int ii=i+1; if(ii==n_vertex) ii=0;
double D=sqsum(x[idx[i]]-gx,y[idx[i]]-gy);
double L=sqsum(x[idx[i]]-x[idx[ii]],y[idx[i]]-y[idx[ii]]);
if(Dmax<D) Dmax=D;
if(Dmin>D) Dmin=D;
if(Lmax<L) Lmax=L;
if(Lmin>L) Lmin=L;
}
if(Dmin<radiiRatio*Dmax) goto FAILED;
if(Lmin<sidesRatio*Lmax) goto FAILED;
}

// found nice polygon, output
static char tmp[1024];
if(n_vertex<=5){
if (n_vertex==3) sprintf(tmp,"%d %d %d",idx[0],idx[1],idx[2]);
else if(n_vertex==4) sprintf(tmp,"%d %d %d %d",idx[0],idx[1],idx[2],idx[3]);
else sprintf(tmp,"%d %d %d %d %d",idx[0],idx[1],idx[2],idx[3],idx[4]);
}
else{
if (n_vertex==6) sprintf(tmp,"%d %d %d %d %d %d",idx[0],idx[1],idx[2],idx[3],idx[4],idx[5]);
else if(n_vertex==7) sprintf(tmp,"%d %d %d %d %d %d %d",idx[0],idx[1],idx[2],idx[3],idx[4],idx[5],idx[6]);
else sprintf(tmp,"%d %d %d %d %d %d %d %d",idx[0],idx[1],idx[2],idx[3],idx[4],idx[5],idx[6],idx[7]);
}
ans.push_back(tmp);

// remove vertices from QuadTree
rep(i,n_vertex) qt.erase(ps[idx[i]]);

// swap used vertices to the tail of array
rep(i,n_vertex){
int last=n_unused-1;
// i 番目の頂点 u を削除する (配列の最後の頂点を u にコピーして、配列サイズを 1 減らす)
f[y[unused[last]]][x[unused[last]]]=f[y[idx[i]]][x[idx[i]]];
unused[idx0[i]]=unused[last];
// 配列の最後の頂点 v も削除するべき頂点だったら、整合性が保たれるように idx0 を書き換える
for(int j=i+1;j<n_vertex;j++){
if(idx0[j]==last){
f[y[idx[i]]][x[idx[i]]]=f[y[idx[j]]][x[idx[j]]];
idx0[j]=idx0[i];
break;
}
}
n_unused--;
}

FAILED:;
}

return ans;
}

int score(const vector<string> &ans){
int n=ans.size(),sc=0;
rep(i,n){
int m=count(all(ans[i]),' ')+1;
sc+=m*m;
}
return sc;
}

public:
vector<string> choosePolygons(vector<int> points,int sidesDiff,int radiiDiff){
if(points.size()>2*250){
t_limit8=3000000;
t_limit7=6000000;
t_limit6=8000000;
t_limit5=9000000;
t_limit4=9500000;
t_limit3=9990000;
return solve(points,sidesDiff,radiiDiff);
}
else{
t_limit8=1500000;
t_limit7=3000000;
t_limit6=4000000;
t_limit5=4500000;
t_limit4=4750000;
t_limit3=4970000;
vector<string> ans[2];
ans[0]=solve(points,sidesDiff,radiiDiff);
ans[1]=solve(points,sidesDiff,radiiDiff);
return score(ans[0])<score(ans[1])?ans[1]:ans[0];
}
}
};

#ifdef LOCAL
int main(){
int n,sidesDiff,radiiDiff;
vector<int> points;
vector<string> ret;
QualityPolygons QP;

scanf("%d",&n);
points.resize(n);
rep(i,n) scanf("%d",&points[i]);
scanf("%d%d",&sidesDiff,&radiiDiff);

ret=QP.choosePolygons(points,sidesDiff,radiiDiff);
printf("%d\n",ret.size());
rep(i,ret.size()) puts(ret[i].c_str());
fflush(stdout);

return 0;
}
#endif

ジャスト 400 行。

† 3 行おきに scan して、間の行は scan したラインをコピーしただけ
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。