スポンサーサイト

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

CodeChef The February 2011 Cook-Off

2011/02/21 1:00~3:30 (JST)
CodeChef の月一ショートコンテストの参加記録。

今回は全然解けなくてくやしい。

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

結果

問題を、問題ページの上から順に A, B, .., E と呼ぶことにする。
A. 2TLE
B. -
C. -
D. 2WA
E. AC
Standing : 114/301


問題

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

A. Breaking Into Atoms
全体集合 X := {0, 1, 2, .., n-1} の部分集合 S1, .., Sm が与えられる。

A1, .., Ak ⊂ X を次の条件をみたすように選ぶとき、ありうる最小の k を求めよ。
・ ∪[i=1→k] Ak = X ( Ai は互いに排反 )
・ すべての i, j で、Ai ⊂ Sj または Ai ∩ Sj = φ

1 ≦ n ≦ 100; 1 ≦ m ≦ 30

B. Dance Floor Energy
ホールで B 人の男性と G 人の女性がダンスパーティーをする。
各男性、女性について
・ ホールに来る時間
・ ホールを去る時間
・ ダンスをしたい相手のリスト
が分かっている。
1 組の男女は、お互いが相手とダンスをしたいと思っているときにダンスをすることができる。
どの人も、同時に高々 1 人としかダンスできない。

パーティーの開始時刻を 0, パーティーの終了時刻を L とする。
パーティーの各時刻において、ダンスしている組が最大になるようにペアを作る。
ペアの組み換えにかかる時間は無視する。
このとき、ダンスしている組数とダンスの合計時間のリストを出力せよ。

C.
読んでない。

D. Integer Sequences
0, 1, .., 2n-1 を並べ替えた数列で、隣接する項は 2 進数表示したときにちょうど 1 bit だけ違うようにする。
さらに、隣接する項に a b または b a という並びが登場してはいけない。
このような並びを 1 つ求めよ。
答えがないときは -1 と答えよ。
( 数列の最初と最後も隣接しているものとする )

1 ≦ n ≦ 15; 0 ≦ a, b ≦ 2n-1

E. Three Way Communications
3 つのトランシーバの位置と、トランシーバの電波受信半径が与えられる。
各トランシーバは電波の中継をすることもできる。
任意の 2 つのトランシーバが通話できる位置にあるかどうかを判定せよ。

解答

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

A. (時間外)
vvi toConnectedComponents(const vvb &adj){
int n=adj.size();
vvi res;
vb visited(n);
rep(i,n)if(!visited[i]){
vi comp;
queue<int> qu; qu.push(i); visited[i]=true;
while(!qu.empty()){
int u=qu.front(); qu.pop();
comp.pb(u);
rep(v,n)if(adj[u][v] && !visited[v]){ qu.push(v); visited[v]=true; }
}
res.pb(comp);
}
return res;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int m,n; scanf("%d%d",&n,&m);
bool S[30][100]={};
rep(i,m){
int sz; scanf("%d",&sz);
rep(j,sz){
int x; scanf("%d",&x);
S[i][x]=true;
}
}

vvb adj(n,vb(n));
rep(x,n)rep(y,x){
bool b=true;
rep(i,m)if(S[i][x]^S[i][y]){ b=false; break; }
adj[x][y]=adj[y][x]=b;
}

printf("%d\n",toConnectedComponents(adj).size());
}

return 0;
}

複雑な問題に見えるけど、サンプルを書き下してみると様子がわかる。
ようするに、X を各 Si で区切ったときにいくつの部分に分かれるかを求めればいい。
そこまではいいが、いい実装方法が思いつかず迷走。
vector とか set とか集合演算とかたくさん使って何とか書き上げるも TLE。
あとで Editorials を見て解く。

[ 2011/02/24 追記 ]

解いた。
Editorials の解説どおりの naive な実装。

X の元 x, y に対して、
x ~ y ⇔ すべての i で、Si は x, y を共に含む or どちらも含まない
と定義すれば、これは同値関係。この関係を使って同値類に分割したときの同値類の個数が答え。
グラフの問題に還元すれば、連結成分の個数を求める問題。
作り置きしておいた toConnectedComponents がさっそく役に立った。

B. (時間外)
int hall[2][200];   // whether person is in hall

enum {IN=0,OUT=1};
struct Event{
int t,id,io,sex;
Event(){}
Event(int T,int ID,int IO,int S):t(T),id(ID),io(IO),sex(S){}
bool operator<(const Event &e)const{
if(t!=e.t) return t<e.t;
return io<e.io;
}
};

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 augment(int u,vb &visited,const AdjList<int> &adj,vi match[2]){
if(u==-1) return true;
if(!hall[0][u]) return false;

rep(i,adj[u].size()){
int v=adj[u][i].v;
if(hall[1][v] && !visited[v]){
visited[v]=true;
if(augment(match[1][v],visited,adj,match)){
match[0][u]=v;
match[1][v]=u;
return true;
}
}
}

return false;
}

bool augment(const AdjList<int> &adj,vi match[2]){
int L=match[0].size(),R=match[1].size();
vb visited(R);
rep(u,L)if(match[0][u]==-1){
if(augment(u,visited,adj,match)) return true;
}
return false;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int ngirl,nboy,tend; scanf("%d%d%d",&nboy,&ngirl,&tend);
int n=nboy+ngirl;

vector<Event> events;
static bool love[2][200][200];
memset(love,0,sizeof(love));
rep(i,2)rep(u,i?ngirl:nboy){
int tin,tout,m; scanf("%d%d%d",&tin,&tout,&m);
events.pb(Event(tin ,u,IN ,i));
events.pb(Event(tout,u,OUT,i));
rep(j,m){
int v; scanf("%d",&v);
love[i][u][v]=true;
}
}
sort(events.begin(),events.end());

AdjList<int> adj(nboy);
rep(u,nboy)rep(v,ngirl){
if(love[0][u][v] && love[1][v][u]) adj[u].pb(Edge<int>(u,v,1));
}

vi match[2];
match[0].assign(nboy,-1);
match[1].assign(ngirl,-1);

memset(hall,0,sizeof(hall));
int ans[201]={},nmatch=0,tpre=0;
rep(k,events.size()){
Event e=events[k];
int u=e.id,t=e.t,sex=e.sex,io=e.io;
hall[sex][u]=(io==IN);

ans[nmatch]+=t-tpre;
tpre=t;

if(io==OUT && ~match[sex][u]){ // remove a matching
int partner=match[sex][u];
match[sex][u]=match[!sex][partner]=-1;
nmatch--;
}

if(augment(adj,match)) nmatch++;
}
ans[nmatch]+=tend-tpre;

rep(i,min(nboy,ngirl)+1) printf("%d%c",ans[i],i<min(nboy,ngirl)?' ':'\n');
}

return 0;
}

[ 2011/03/30 追記 ]

問題文が長いけど、つまりは動的な二部マッチング。
Editorials と Problem Setter の解答を見ながら解いた。

人の出入りがあるたびに、一からマッチングを作り直していては TLE になる。
ただし、以下に述べる想定解でも下手な実装をすると間に合わなくなるので注意。

人の出入りで最大マッチングがどう変化するかを考える。
  • 人が入ってきたとき
    最大マッチングのサイズは高々 1 だけ増える。
  • 人が出ていくとき
    出て行った人がマッチングに使われていなかったときは、マッチングは変わらない。
    出て行った人がマッチングに使われていたときは、マッチングのサイズは高々 1 減る。

いずれの場合も、最大マッチングを再構成するには、増加道 (交互道) を 1 回探せば十分だと分かる。
なので、人の出入り 1 回につき O(m+n) 時間で済む。

上の実装では DFS で交互道を探している。
これはとてもうまくできているので、注意深く読む価値のあるコードだと思う。

C.


D. (時間外)
#define rot(x,i)    ( ( ((x)<<(i)) & ((1<<n)-1) ) | ((x)>>(n-(i))) )

int main(){
int T; scanf("%d",&T);
while(T--){
int n,a,b; scanf("%d%d%d",&n,&a,&b);

vi gray(1<<n);
rep(i,1<<n) gray[i]=i^(i>>1);
gray.pb(gray[0]);

bool ok=true;
rep(i,gray.size()-1){
if(gray[i]==b && gray[i+1]==a) swap(a,b);
if(gray[i]==a && gray[i+1]==b){ ok=false; break; }
}
if(ok) goto FOUND;
else{
int p=-1;
rep(i,n){
int rot1=rot(gray[1],i),rot2=rot(gray[(1<<n)-1],i);
if((rot1^a)!=b && (rot2^a)!=b){ p=i; break; }
}
if(~p){
rep(i,gray.size()) gray[i]=rot(gray[i],p)^a;
goto FOUND;
}
else goto NOT_FOUND;
}

FOUND:
rep(i,gray.size()-1) printf("%s%d",i?" ":"",gray[i]);
putchar('\n');
continue;

NOT_FOUND:
puts("-1");
continue;
}

return 0;
}

Gray 符号は高専時代に習った。
とりあえず、Gray 符号で a b の制約がないときの解を作った。
あとは、この解を適当に rotate させれば、a b の制約をみたす解が見つかるんじゃないかと思ったけど、そう都合よくはいかず WA。
あとで解く。

[ 2011/02/24 追記 ]

解いた。
上の方針で大体あってた。多分、n = 2 とかのコーナーケースでひっかかったんだと思う。
Editorials の説明がよくわからなかったので、Problem Tester (David Stolp氏) のコードを読んで理解した。

まず、Gray 符号で作った数列 ( {gn} とする) が a b の制約にひっかからなければその時点で解決。
制約に引っかかった場合は、以下のように考える。

次の 2 つの事実を確認する。
  • 任意の r (0 ≦ r ≦ n-1) に対して、
    g'i := ( gi を r bit rotate した数 )
    で定義される数列 {g'n} もまた gradual になっている。

  • 任意の C (1 ≦ C < 2n) に対して、
    g'i := gi xor C
    で定義される数列 {g'n} もまた gradual になっている。

そこで、この {gn} を適当に rotate した後、すべての要素に対して xor a をとったものを考える。
g0 = 0 なので rotate しても値は 0、そこで xor a とすれば値は a.
あとは、初項と隣接する項が b と異なるように rotate する bit 数を調整すれば、所望の数列が得られる。
解があるときは、この方法で必ず見つかる。

E.
int dis2(int x1,int y1,int x2,int y2){ return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2); }

int main(){
int T; scanf("%d",&T);
while(T--){
int r,x[3],y[3]; scanf("%d",&r);
rep(i,3) scanf("%d%d",x+i,y+i);
int cnt=0;
rep(i,3) if(dis2(x[i],y[i],x[(i+1)%3],y[(i+1)%3])<=r*r) cnt++;
puts(cnt>=2?"yes":"no");
}
return 0;
}

問題文をちゃんと読みましょうという問題。
距離 R 以下のトランシーバ間を辺としてグラフを作って、それが連結しているかを調べればいい。
今回の場合は、距離 R 以下のトランシーバの組が 2 組以上あることが必要十分。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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