スポンサーサイト

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

CodeChef August Long Contest 2011

CodeChef August Long Contest 2011 の参加記
2011/08/01 18:30 ~ 08/12 18:30 (JST)

例によって問題は難しくて、例によって 1 日延びた。

Tags : プログラミング CodeChef 未解決

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. -
B. AC [0.997 pts]
C. -
D. -
E. AC [1 pts]
F. -
Standing : 46/629
Rank (Long) : 121 → 113
Rating (Long) : 83 → 90.774


問題

問題セットの原文はここを参照。

A.

B. Complex Spanning Tree
20 × 20 の格子グラフがあって、辺には複素数の重みがついている。
このグラフの全域木を 1 つ求めよ。
全域木に使われている辺の重みの和の絶対値が大きいほど良い解である。

C.

D. Coloring in Hypercube
N 次元空間の格子点に色 (白 or 黒) を塗ることを考える。

原点は黒で塗る。
座標値に負の数を含む点は白で塗る。
それ以外の点 (x1, x2, ..., xN) については、N 個の点
(x1-1, x2, ..., xN)
(x1, x2-1, ..., xN)
:
(x1, x2, ..., xN-1)
の中に黒点が偶数個あれば黒で、奇数個あれば白で塗る。

N 次元の直方体が指定されるので、その直方体の中 (境界含む) にある黒点の個数を mod 1000000009 で求めよ。

直方体の座標値は 0 以上 1015 以下。

E. Infinite Grid Game
2 次元の格子点上で 2 人でゲームをする。
スタート (m, n) とゴール (p, q) が与えられる。
スタートにある点を交互に動かしていって、ゴールに着いたプレイヤーの勝ち。

点 (x, y) は、次の場所にのみ動かすことができる。
・ (x', y) ( ただし p ≦ x' < x )
・ (x, y') ( ただし q ≦ y' < y )
・ (x-a, y-a) ( ただし 0 < a ≦ min(x-p, y-q) )

両プレイヤーが最善手を打つとき、先手必勝か後手必勝かを答えよ。

1 ≦ m, n ≦ 1000
0 ≦ p < m
0 ≦ q < n

F.

解答

言語は C++。テンプレはここを参照。

A.


B.
const double PI=acos(-1);

double theta;

struct Complex{
int x,y;

double abs2()const{ return (double)x*x+(double)y*y; }

double proj2()const{ return this->abs2()*cos(atan2(y,x)-theta); }

bool operator<(const Complex &z)const{ return proj2()<z.proj2(); }
};

template<class T> struct Edge{
int u,v;
T w;
Edge(int U,int V,T W):u(U),v(V),w(W){}
bool operator<(const Edge &e)const{ return w<e.w; }
};

class UnionFind{
int n;
vector<int> a;
public:
UnionFind(int N):a(N,-1),n(N){}
int find(int x){
if(a[x]<0) return x;
return a[x]=find(a[x]);
}
void unite(int x,int y){
x=find(x),y=find(y);
if(x!=y){ a[x]+=a[y]; a[y]=x; n--; }
}
int size(){ return n; }
};

int main(){
int n; scanf("%d",&n);
vector< Edge<Complex> > E;
rep(i,n) rep(j,n-1) {
int x,y; scanf("%d%d",&x,&y);
E.push_back(Edge<Complex>(n*i+j,n*i+(j+1),(Complex){x,y}));
}
rep(j,n) rep(i,n-1) {
int x,y; scanf("%d%d",&x,&y);
E.push_back(Edge<Complex>(n*i+j,n*(i+1)+j,(Complex){x,y}));
}

double best=-1,best_theta;
rep(k,301){
theta=-(1-k/300.0)*PI+k/300.0*PI;

sort(E.begin(),E.end());

int x=0,y=0;
UnionFind uf(n*n);
rep(i,E.size()){
int u=E[i].u,v=E[i].v;
if(uf.find(u)!=uf.find(v)){
x+=E[i].w.x;
y+=E[i].w.y;

uf.unite(u,v);
if(uf.size()==1) break;
}
}

double score=(double)x*x+(double)y*y;
if(best<score){
best=score;
best_theta=theta;
}
}

// output
theta=best_theta;
sort(E.begin(),E.end());

UnionFind uf(n*n);
rep(i,E.size()){
int u=E[i].u,v=E[i].v;
if(uf.find(u)!=uf.find(v)){
printf("%d %d %d %d\n",u/n+1,u%n+1,v/n+1,v%n+1);
uf.unite(u,v);
if(uf.size()==1) break;
}
}

return 0;
}

複素数とか言ってるけど、ただのベクトル演算。

Kruskal 法まがいのアルゴリズム。
答えのベクトルの方向を決めうちして、その向きに近い重みをもった辺から順に採用するようにした。

これだけで 0.997 点ももらえた。

最適解を出している人がたくさんいて、tiebreaker problem の役割を果たしていなかった。

C.


D.

包除原理で問題を分解すれば、原点を 1 つの頂点とする直方体のみを考えればいいことは分かる。
そこから先が進まなかった。
入力値が大きすぎるので素直に DP はできない。
n = 2 の場合を書き下してみると、Sierpinski gasket みたいな形が出てきた。

Editorials によると多項係数とか Lucas の定理がどうこうらしい。 fmm...

n = 2 の図形は Pascal's triangle を mod 2 で見たときのものだという知識はあった。
なぜそこから、二項係数 → n項係数!! という発想が出なかったんだろう。

E.
int main(){
const double phi=(1+sqrt(5))/2;

static bool lose[1001][1001];
for(int i=0;;i++){
int a=i*phi,b=i*phi*phi;
if(b>1000) break;
lose[a][b]=lose[b][a]=true;
}

int T; scanf("%d",&T);
while(T--){
int m,n,p,q; scanf("%d%d%d%d",&m,&n,&p,&q);
puts(!lose[m-p][n-q]?"Alice":"Bob");
}

return 0;
}

Wythoff's Game という有名な問題。
黄金比を使って表される 2 本のライン上でだけ後手必勝になる。
( 証明は知らない )

POJ や GCJ で類題を解いたことがあったのですぐに解けた。

F.

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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