スポンサーサイト

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

CodeChef April 2011 Challenge

2011/04/01 18:30 ~ 04/12 18:30 (JST)
CodeChef のロングコンテストの参加記録。
今回はいつもに比べれば簡単な問題が多かった印象。

Tags : プログラミング CodeChef

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. -
B. AC (1[pt])
C. AC (1[pt])
D. -
E. WA
F. AC (0.901[pts])
Standing : 42/714
Rank (Long) : 204 → 168
Rating (Long) : 40.58 → 54.806


問題

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

A. Central Point
R2 上の格子点が N (≦ 2000) 個与えられる。
座標値は 109 を越えない。
これらの点からの距離の総和が最小になるような格子点を求め、距離の総和を出力せよ。

B. Generalized Independent Sets
無向グラフ G=(V,E) の一般化独立集合(関数) f を次で定義する。

f : V → [0,1] で、
G の任意の閉路 v1 - v2 - ... - v|C| - v1 ( vi ≠ vj ) について
f (v1) + ... + f (v|C|) ≦ floor(|C|/2)
をみたす。


与えられた f が一般化独立集合かどうかを判定せよ。
なお、|C| = 2 のケース (2 頂点間を行って戻る) も閉路と考えることに注意せよ。

1 ≦ |V| ≦ 500
0 ≦ |E| ≦ 2000

C. Graphs in Euclidean Space
重みつき完全無向グラフ G = (V, E) が与えられる。
G の頂点を Rd に射影せよ。

射影のコストは次で計算される。
cost = d・L/K
L = min { b(u,v)/a(u,v) | u, v ∈ V }
K = max { b(u,v)/a(u,v) | u, v ∈ V }
a(u, v) = G における辺 (u, v) の重み
b(u, v) = Rd における u と v のユークリッド距離

コストが小さい解が良い解である。

テストケースの数 ≦ 30
2 ≦ |V| ≦ 300
1 ≦ 辺の重み ≦ 10000

D. Gravel
n グループの石の山がある。
最初、それぞれの山には c 個ずつ石が積まれている。
次の 2 種類の操作を合計 m 回繰り返す。
各グループにある石の個数をシミュレートせよ。

操作 1 : 山 u から山 v までのすべての山に k 個ずつ石を置く。
操作 2 : 山 p に幾つの石があるかを答える。

0 < n ≦ 106
0 < m ≦ 250000

E. Number Game Revisited
2 人で Nim ゲームをする。
各プレイヤーは 1 または 素数だけ数字を減らすことができる。
数字を 0 以下にしたプレイヤーの負け。
先手必勝か後手必勝かを判定せよ。

1 ≦ テストケースの数 ≦ 106
1 ≦ ゲーム開始時の数字 ≦ 109

F. Rectangles Counting
R2 上の格子点が N (≦ 105) 個与えられる。
座標値は 109 を越えない。
どの 3 つの点も、x 座標が等しくなることはない。
これらの点を結んでできる (軸に平行な辺をもつ) 長方形の個数を答えよ。

解答

言語は C++。ただし E は Tcl。
テンプレはここを参照。

A.
int n,x[2000],y[2000];

double f(double x0,double y0){
double sum=0;
rep(i,n) sum+=sqrt((x0-x[i])*(x0-x[i])+(y0-y[i])*(y0-y[i]));
return sum;
}

int main(){
while(scanf("%d",&n),n){
rep(i,n) scanf("%d%d",x+i,y+i);

double xlo,xhi,ylo=0,yhi;
rep(t,4){
xlo=-1e10,xhi=1e10;
rep(k,80){
double xmi1=(xhi+2*xlo)/3,xmi2=(2*xhi+xlo)/3;
if(f(xmi1,ylo)>f(xmi2,ylo)) xlo=xmi1;
else xhi=xmi2;
}
ylo=-1e10,yhi=1e10;
rep(k,80){
double ymi1=(yhi+2*ylo)/3,ymi2=(2*yhi+ylo)/3;
if(f(xlo,ymi1)>f(xlo,ymi2)) ylo=ymi1;
else yhi=ymi2;
}
}

ll x=(ll)(xlo+0.5),y=(ll)(ylo+0.5);
for(int i=-1;i<=1;i++)for(int j=-1;j<=1;j++){
ll xx=(ll)(xlo+j+0.5),yy=(ll)(ylo+i+0.5);
if(f(xx,yy)<f(x,y)) x=xx,y=yy;
}
printf("%.6f\n",f(x,y));
}

return 0;
}

偏導関数の零点を調べる方法で解析的にできるかと思ったけど、式が整理できなくて諦めた。
いくつかのケースで距離の和の x-y グラフを描いてみると、どうやらこれは凸関数になるだろうと推測できたので、三分探索した。
x 方向と y 方向を交互に三分探索しながら、解を更新していく。
1 回ずつ三分探索するだけでは最適解は求められないので、何回か反復してみると通った。
gradient の値を調べたりすれば、もっと速く収束されられるような気はする。

[ 2011/04/14 追記 ]

Weber problem という問題そのままだった。
効率のいいアルゴリズムまで、Wikipedia にばっちり書いてある。

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

template<class T>
struct AdjList:public vector< vector< Edge<T> > >{
AdjList(){}
AdjList(int n,const vector< Edge<T> > &v=vector< Edge<T> >()):vector< vector< Edge<T> > >(n,v){}
template<class U> AdjList(U b,U e):vector< vector< Edge<T> > >(b,e){}
};

bool checkEvenCycle(const AdjList<int> &adj){
int n=adj.size();
rep(u,n)rep(i,adj[u].size()){
if(adj[u][i].w<0){
printf("Bad Cycle: %d %d -1\n",u,adj[u][i].v);
return false;
}
}
return true;
}

bool checkOddCycle(const AdjList<int> &adj){
int n=adj.size();
rep(u0,n){
vi d[2],parent[2];
rep(i,2){
d[i].assign(n,INF);
parent[i].assign(n,-1);
}
d[0][u0]=0;

/* Dijkstra */
int ans=-1;
priority_queue< pair<int,pii> > pq; pq.push(mp(0,mp(0,u0)));
while(!pq.empty()){
pair<int,pii> a=pq.top(); pq.pop();
int flg=a.second.first,u=a.second.second;
if(d[flg][u]<-a.first) continue;
if(flg==1 && u==u0){ ans=d[flg][u]; break; }

rep(i,adj[u].size()){
int v=adj[u][i].v,w=adj[u][i].w;
if(d[flg][u]+w<d[!flg][v]){
d[!flg][v]=d[flg][u]+w;
pq.push(mp(-d[!flg][v],mp(!flg,v)));
parent[!flg][v]=u;
}
}
}

/* construct cycle */
if(~ans && ans<1000){
vi path;
for(int flg=1,u=u0;;u=parent[flg][u],flg=!flg){
path.pb(u);
if(flg==0 && u==u0) break;
}

int p0,p1;
vi seen(n,-1);
rep(i,path.size()){
int u=path[i];
if(~seen[u]){
p0=seen[u];
p1=i;
break;
}
seen[u]=i;
}

printf("Bad Cycle:");
for(int i=p0;i<p1;i++) printf(" %d",path[i]);
puts(" -1");
return false;
}
}

return true;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n,m; scanf("%d%d",&n,&m);
int f[500];
rep(u,n){
double tmp; scanf("%lf",&tmp);
f[u]=(int)(1000*tmp+EPS);
}
AdjList<int> adj(n);
rep(i,m){
int u,v; scanf("%d%d",&u,&v);
adj[u].pb(Edge<int>(u,v,1000-(f[u]+f[v])));
adj[v].pb(Edge<int>(v,u,1000-(f[v]+f[u])));
}

if(checkEvenCycle(adj) && checkOddCycle(adj)) puts("Ok");
}

return 0;
}

[ 2011/04/15 追記 ]

Editorials を見ながら解いた。
総じて難しかった。
解法は Editorials のものと全く同じなので、大雑把に書く。

閉路長の偶奇で場合分けする。
偶数長の bad cycle があるかどうかは、長さ 2 の閉路 (⇔ 辺) を調べれば十分。
奇数長の bad cycle があるかどうかは次のようにして調べる。
辺の重み = 1 - 両端の頂点の重みの和
と定めれば、
奇数長の閉路 C が bad cycle ⇔ C の辺の重みの和 < 1
が成立。
ゆえに、奇数長の bad cycle を探すためには、奇数長の閉路で重み最小のものを探せばいい。
具体的には、頂点集合 V をコピーしたものをもう 1 つ用意して、その間に辺を張って二部グラフを作ったあと、二部グラフ上の最短経路を求めればいい。これは Dijkstra でできる。
また、この方法で見つけた閉路は同じ頂点を 2 回通っているかもしれないので、出力する際はそれを考慮して自己交差のない部分だけを取り出す必要がある。

C.
const int d=4;
int n,dis[300][300],x[300],y[300],z[300],w[300];

struct P{
int x,y,z,w;
P(){}
P(int X,int Y,int Z,int W):x(X),y(Y),z(Z),w(W){}
bool operator<(const P &p)const{
if(x!=p.x) return x<p.x;
if(y!=p.y) return y<p.y;
if(z!=p.z) return z<p.z;
if(w!=p.w) return w<p.w;
return false;
}
};

bool cmp(const P &p,const P &q){
return (ll)p.x*p.x+(ll)p.y*p.y+(ll)p.z*p.z+(ll)p.w*p.w<(ll)q.x*q.x+(ll)q.y*q.y+(ll)q.z*q.z+(ll)q.w*q.w;
}

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));
}

inline int delta(){ return xor128()&15; }

double findBottleNeck(int &umin,int &vmin,int &umax,int &vmax){
double K2=1e60,L2=-1e60;
rep(u,n)rep(v,u){
double Euc2=(double)(x[u]-x[v])*(x[u]-x[v])+(double)(y[u]-y[v])*(y[u]-y[v])+(double)(z[u]-z[v])*(z[u]-z[v])+(double)(w[u]-w[v])*(w[u]-w[v]);
double ratio2=Euc2/dis[u][v]/dis[u][v];
if(ratio2<K2){
K2=ratio2;
umin=u,vmin=v;
}
if(ratio2>L2){
L2=ratio2;
umax=u,vmax=v;
}
}
return L2/K2;
}

int main(){
pii ord[300];
P p[300];

int T; scanf("%d",&T);
while(T--){
scanf("%d",&n);
rep(u,n)rep(v,n) scanf("%d",dis[u]+v);

rep(u,n) ord[u]=mp(accumulate(dis[u],dis[u]+n,0),u);
sort(ord,ord+n);

int n4=(int)(sqrt(sqrt(n))+0.5);
rep(u,n){
p[u].x=10000*(u/n4/n4/n4)-5000;
p[u].y=10000*(u/n4/n4%n4)-5000;
p[u].z=10000*(u/n4%n4)-5000;
p[u].w=10000*(u%n4)-5000;
}
sort(p,p+n,cmp);

set<P> used;
rep(u,n){
x[ord[u].second]=p[u].x;
y[ord[u].second]=p[u].y;
z[ord[u].second]=p[u].z;
w[ord[u].second]=p[u].w;
used.insert(p[u]);
}

double sc2=1e60;
rep(l,2){
double R1,R2;
if(l==0) R1=1.008,R2=0.992;
if(l==1) R1=1.005,R2=0.995;
rep(k,50){
int umin,vmin,umax,vmax;
double tmp=findBottleNeck(umin,vmin,umax,vmax);
if(sc2<tmp) break;
sc2=tmp;

used.erase(P(x[umin],y[umin],z[umin],w[umin]));
used.erase(P(x[vmin],y[vmin],z[vmin],w[vmin]));

int xmid=(x[umin]+x[vmin])/2,ymid=(y[umin]+y[vmin])/2,zmid=(z[umin]+z[vmin])/2,wmid=(w[umin]+w[vmin])/2;
x[umin]=(int)(xmid+R1*(x[umin]-xmid))+delta();
x[vmin]=(int)(xmid+R1*(x[vmin]-xmid))+delta();
y[umin]=(int)(ymid+R1*(y[umin]-ymid))+delta();
y[vmin]=(int)(ymid+R1*(y[vmin]-ymid))+delta();
z[umin]=(int)(zmid+R1*(z[umin]-zmid))+delta();
z[vmin]=(int)(zmid+R1*(z[vmin]-zmid))+delta();
w[umin]=(int)(wmid+R1*(w[umin]-wmid))+delta();
w[vmin]=(int)(wmid+R1*(w[vmin]-wmid))+delta();

while(used.count(P(x[umin],y[umin],z[umin],w[umin]))>0){
x[umin]+=delta();
y[umin]+=delta();
z[umin]+=delta();
w[umin]+=delta();
}
used.insert(P(x[umin],y[umin],z[umin],w[umin]));

while(used.count(P(x[vmin],y[vmin],z[vmin],w[vmin]))>0){
x[vmin]+=delta();
y[vmin]+=delta();
z[vmin]+=delta();
w[vmin]+=delta();
}
used.insert(P(x[vmin],y[vmin],z[vmin],w[vmin]));

used.erase(P(x[umax],y[umax],z[umax],w[umax]));
used.erase(P(x[vmax],y[vmax],z[vmax],w[vmax]));

xmid=(x[umax]+x[vmax])/2,ymid=(y[umax]+y[vmax])/2,zmid=(z[umax]+z[vmax])/2,wmid=(w[umax]+w[vmax])/2;
x[umax]=(int)(xmid+R2*(x[umax]-xmid))+delta();
x[vmax]=(int)(xmid+R2*(x[vmax]-xmid))+delta();
y[umax]=(int)(ymid+R2*(y[umax]-ymid))+delta();
y[vmax]=(int)(ymid+R2*(y[vmax]-ymid))+delta();
z[umax]=(int)(zmid+R2*(z[umax]-zmid))+delta();
z[vmax]=(int)(zmid+R2*(z[vmax]-zmid))+delta();
w[umax]=(int)(wmid+R2*(w[umax]-wmid))+delta();
w[vmax]=(int)(wmid+R2*(w[vmax]-wmid))+delta();

while(used.count(P(x[umax],y[umax],z[umax],w[umax]))>0){
x[umax]+=delta();
y[umax]+=delta();
z[umax]+=delta();
w[umax]+=delta();
}
used.insert(P(x[umax],y[umax],z[umax],w[umax]));

while(used.count(P(x[vmax],y[vmax],z[vmax],w[vmax]))>0){
x[vmax]+=delta();
y[vmax]+=delta();
z[vmax]+=delta();
w[vmax]+=delta();
}
used.insert(P(x[vmax],y[vmax],z[vmax],w[vmax]));
}
}

printf("%d\n",d);
rep(u,n) printf("%d %d %d %d\n",x[u],y[u],z[u],w[u]);
}

return 0;
}

まず、問題の意図を読み取るのがそれほど簡単じゃない。

辺の重みと頂点間の距離が一致するように、グラフをユークリッド空間に射影するのは一般にはできないように思える。
その「頂点間の距離関係」をできるだけ保つような射影を考えろ、ということだと思う。
評価値の L は、距離が一番縮んだところの倍率で、K は距離が一番伸びたところの倍率。
高次元だと余裕を持って埋め込めるイメージなので、d は小さいほうがいい。
まぁ、問題文に書いてるんだけど。

いろいろ試したところ d=4 でいいスコアがでたので、次元は 4 に固定して考えた。

まず、一辺が 4√n くらいの 4 次元立方体の格子点に頂点を配置した。
その際、少しでもいい初期配置を選ぶために、他の頂点との距離の和が小さい頂点ほど、立方体の中のほうに配置されるようにした。

あとは、ボトルネックになっている頂点対をみつけてそれらの位置を遠ざける or 近づけるという処理を時間いっぱいまで繰り返した。
ボトルネックを見つける処理が、毎回 O(n2) 時間もかかって遅い。RMQ を使うと高速化できるけど、結局実装はしなかった。

最終スコアは 226837.474247 だった。

D.
/*
1
2 3
4 5 6 7
8 9 A B C D E F
*/


int N; // power of 2 (n<=N)
ll a[1<<21];

void add(int s,int t,ll c,int u=1,int l=0,int r=N){
if(s==l && t==r){ a[u]+=c; return; }
int m=(l+r)/2;
if(s<m) add(s,min(t,m),c,2*u ,l,m);
if(m<t) add(max(s,m),t,c,2*u+1,m,r);
}

ll find(int u){
ll sum=0;
for(int i=N+u;i>0;i/=2) sum+=a[i];
return sum;
}

int main(){
int n,m,c; scanf("%d%d%d ",&n,&m,&c);
for(int i=1;;i<<=1)if(n<=i){ N=i; break; }
add(0,n,c);
while(m--){
if(getchar()=='S'){
int u,v,k; scanf("%d%d%d ",&u,&v,&k);
u--,v--;
add(u,v+1,k);
}
else{
int u; scanf("%d ",&u);
u--;
printf("%lld\n",find(u));
}
}

return 0;
}

Segment Tree のようなデータ構造を使った。( これも Segment Tree と呼んでいいのかわからない。
完全二分木で、葉が石山に対応する。
各ノードは 1 つの値を持っていて、根から葉へのパス上のノードの値の合計が、葉 (に対応する石山) にある石の数を表す。
文章で説明するよりコードを見てもらう方が分かりやすいと思う。
どちらのクエリも O(log n) でできる。

E.
for {gets stdin t} {$t>0} {incr t -1} {if [expr ([gets stdin]%4)==1] {puts ALICE} else {puts BOB}}

小さいケースをシミュレートしてみたところ、明確なパターンがあったのでそれを書いただけ。
mod 4 で 1 余るかどうか。
小さい入力に対するコーナーケースもない。

なぜこれでいいのかは証明できてないが。
( 最初、ゴールドバッハ予想とかが使えるんじゃないかと思ったけど、多分関係ない。)

F.
int main(){
for(int n;scanf("%d",&n),n;){
pii p[100000];
rep(i,n) scanf("%d%d",&p[i].first,&p[i].second);
sort(p,p+n);

map<pii,int> ypaircnt;
rep(i,n-1){
if(p[i].first==p[i+1].first){
++ypaircnt[mp(p[i].second,p[i+1].second)];
i++;
}
}

ll ans=0;
map<pii,int>::iterator it;
for(it=ypaircnt.begin();it!=ypaircnt.end();++it){
int cnt=it->second;
ans+=(ll)cnt*(cnt-1)/2;
}
printf("%lld\n",ans);
}

return 0;
}

3 つ以上の点が同じ x 座標を共有することはないという条件が使える。
x 座標が等しい点対をすべて求めておく。
2 組の点対の y 座標の組が一致すれば、それらを使って長方形を作ることができる。
O(n log n).
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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