スポンサーサイト

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

Facebook Hacker Cup 2012 Round 2

2011/02/05 06:00 ~ 09:00 (JST)
Facebook Hacker Cup 2012 Round 2 の参加記録

上位 100 人が通過
ねむい時間帯

結果

A. AC (01:04)
B. AC (02:12)
C. -


124th

けっこういいところまで行けただけに惜しい。実装がもう少し速ければ通過ラインだった。

A, B ともに良問だった。
昨年よりはいい成績が残せたと思うけど、問題が易化していた感があるのでなんともいえない。
( 昨年の問題を今解いても 1 問しか解けないと思う。)

問題

問題セットの原文はここを参照。 ( Facebook でのログイン必須 )

A. Road Removal
頂点数 N, 辺数 M の単純無向グラフが与えられる。
グラフには K 個の特別な頂点 0, 1, .., K-1 がある。
グラフの辺をいくつか削除して、特別な頂点を 1 つ以上含むループが存在しないようにしたい。
最小でいくつの辺を除けばいいか?

1 ≦ N ≦ 10000
1 ≦ M ≦ 50000

B. Monopoly
N 個の会社があり、最初、どの会社にもちょうど一人の社員がいる。
N 人の社員は 1, 2, .., N と番号付けられている。

各会社ごとの社員たちの関係は木であり、その根が社長にあたる。
( すなわち、最初はどの社員も社長である )

2 つの会社を統合する命令が N-1 回与えられる。
命令 (i, j) は
「社員 i を含む会社と社員 j を含む会社を統合する」
ことを表す。
統合方法は
・ "社員 i を含む会社の社長" の直属の部下に "社員 j を含む会社の社長" を加える
・ "社員 j を含む会社の社長" の直属の部下に "社員 i を含む会社の社長" を加える
の 2 通りが考えられる。
どちらの統合が行われるかは指定されない。

また、統合のどの時点においても、どの社員の直属の部下も D 人を超えてはいけない。

N-1 回の統合を終えたとき、会社はちょうど 1 つだけ残る。
最適な統合を行ったとき、最終的にできる木の高さの最小値はいくらか。
問題の条件をみたすような統合方法は少なくとも 1 通りあることが保障されている。

2 ≦ N ≦ 30000
1 ≦ D ≦ 5000

C. Sequence Slicing
数列 S[0..N-1] が与えられる。
これを用いて数列 MS を
MS[k] := S[k mod N] + N*floor(k/N) ( k = 0, 1, 2, ... )
と定義する。

区間 [0, R] に含まれる整数を一様ランダムに 2 つ選ぶ。( a, b とする )
MS[min(a,b)], MS[min(a,b)+1], .., MS[max(a,b)] に含まれる数の種類が K 種類以上になる確率はいくらか?
既約分数で求めよ。

1 ≦ N ≦ 2000
1 ≦ K ≦ R ≦ 10^9
1 ≦ S[i] ≦ 10^5

コンテスト中

思考過程などを簡単に書く。

5:45
起床。ねむい。

6:00
はじまった。
とりあえず問題を全部読もう。

A.
グラフ。ぱっと見では全然わからんけどおもしろそう。

B.
Union-Find みたいだなーと思う。
わからん。

C.
数列。
S[i] = N+S[j]
とかになりうるので難しそう。

この時点ですでに A を解いている人が 3 人くらいいた。
A が一番おもしろそうだというのもあって、それに取り組むことにする。

わからん。
というかサンプルが異様に長い。
とりあえず小さいサンプルを図におこすことから始める。

消す辺は、特別な頂点を端点とする辺だけとしてよさそう。
証明はできないけど。

そうすると、特別な辺につながっていない部分はどうでもいいので、一つに縮約しちゃう。
多重辺は明らかにループを作ってしまうので、あらかじめ取り除いておく。
いい感じのグラフになってきた気がする。
このグラフで全域木 ( 正確には全域森 ) みたいなのを作ればいい。
n 頂点の木の辺数は n-1 なので、グラフの各連結成分の頂点数と辺数がわかれば、いくつの辺を除けばいいかわかる。
頂点数, 辺数は DFS で求められる。スタックがあふれるような大きさではない。

できた。
コードに落とそう。

書けた。
サンプル合った。

テストケースを食わせる。
segmentation falut とかいわれる。
え、やばいやばい。
半ば絶望しながら、いろんなところに return を入れて特定にかかる。
あ、配列サイズが足りてないだけだった。ふぅ。
submit.

提出したのに、この時点で 100 位を越えていた気がする。
みんな速すぎでは?

B に取り掛かる。

まず、高さ平衡 Union-Find の要領で greedy に高い木に低い木をつなげるというのが思いつくけど、これは間違いっぽい。
子の数に上限 D があるというのが利いてる。
DP のにおいがする。

全然わからんので、またサンプルを解読することから始める。

木の情報で重要なのは "子の数 C" と "子の数が C であるときの最小高さ" の 2 つだけっぽい。
ようするに、これらの値が一致する木は同一視できる。
すると
dp[u][c] := 頂点 u を根とする木について、子の数が c のときの最小高さ
というのが思いつくけど、int[30000][5000] くらいを確保しないといけないのでダメっぽい。
( 実際はこれでもいけたらしい。)

じゃあどうしたかというと、どうせ実際に達成される状態はもっと少ないだろうということで、
各頂点ごとに
map : 子の数 -> 最小高さ
という対応をもつことにした。

計算量が怪しいけど、アルゴリズムは正しい気がする。
とりあえず書いてみる。
Union-Find を機能拡張する感じで書く。
ばぐばぐしてコーディングに時間がかかる。

あ、マージしたときに子にした方のメモリは解放してもいいから、メモリ使用量はもっと減らせるっぽい。
( 実際には O(N) くらいになる? )

書けた。
サンプルも合う。
サンプル弱そうだから不安だけど、ゆっくりテストして順位が下がるのはよくないので出してしまう。
やたら時間がかかるテストケースがある。
それでも、一番時間がかかったので 15 秒くらいだった。

submit.

あと 45 分くらい。
C を考える。

sample output を見て一瞬いやな予感がしたけど、long long でおさまるので多倍長はいらない。
分母は自明に (R+1)^2 なので、確率とはいっても結局は分子を数え上げる問題。

むむむ。
よくわからん。
あまり進展せずに終了。

解答

言語は C++。

A.
#include<map>
#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class union_find{
vector<int> a;
public:
union_find(int n):a(n,-1){}
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; }
}
};

struct edge{ int u,v; };

// 連結成分の頂点数を求める
int dfs_v(int u,const vector<int> *G,bool *vis){
vis[u]=true;
int res=1;
rep(i,G[u].size()){
int v=G[u][i];
if(!vis[v]) res+=dfs_v(v,G,vis);
}
return res;
}

// 連結成分の辺数を求める
int dfs_e(int u,const vector<int> *G,bool *vis){
if(vis[u]) return 0;
vis[u]=true;
int res=0;
rep(i,G[u].size()){
int v=G[u][i];
res+=dfs_e(v,G,vis)+1;
}
return res;
}

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n,m,k; scanf("%d%d%d",&n,&m,&k);
edge E[50000];
union_find U(n);
rep(i,m){
int u,v; scanf("%d%d",&u,&v);
E[i].u=u;
E[i].v=v;
if(u>=k && v>=k) U.unite(u,v);
}

// 縮約グラフの頂点番号を正規化
int nf=0;
map<int,int> f;
rep(u,n) if(f.count(U.find(u))==0) f[U.find(u)]=nf++;

int dup=0;
vector<int> G[10000];
rep(i,m){
int uu=f[U.find(E[i].u)];
int vv=f[U.find(E[i].v)];
if(uu==vv) continue;
if(count(G[uu].begin(),G[uu].end(),vv)>0) dup++;
else{
G[uu].push_back(vv);
G[vv].push_back(uu);
}
}

int ans=dup;
bool vis_v[10000]={},vis_e[10000]={};
rep(u,k){ // 重要な頂点を 1 つ以上含む連結成分を調べる
int uu=f[U.find(u)];
if(!vis_v[uu]){
int nn=dfs_v(uu,G,vis_v);
int mm=dfs_e(uu,G,vis_e)/2;
ans+=mm-(nn-1);
}
}
printf("Case #%d: %d\n",T,ans);
}

return 0;
}

ようするにどういうことかを図で説明してみる。
最初のサンプルを使う。

N=5, M=7, K=2
緑が特別な頂点、赤がふつうの頂点

多重辺があるところには必ずループができてしまうので、それは絶対に取り除かないといけない。
あとはどれを取り除いてもいい。

頂点数を求めるのと辺数を求めるのは別々に書いたけど、1 回の DFS でできるような気もする。

B.
#include<map>
#include<cstdio>
#include<vector>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

class union_find{
vector<int> a;
vector< map<int,int> > f; // 子の数 -> 最小高さ
public:
union_find(int n):a(n,-1),f(n){
rep(x,n) f[x][0]=1;
}
int find(int x){
if(a[x]<0) return x;
return a[x]=find(a[x]);
}
int height(int x){
map<int,int>::iterator it;
int h=INF;
for(it=f[x].begin();it!=f[x].end();++it) h=min(h,it->second);
return h;
}

void solve(int x,int y,int d){
x=find(x);
y=find(y);
map<int,int>::iterator it;

int hxmin=INF,hymin=INF;
for(it=f[x].begin();it!=f[x].end();++it) hxmin=min(hxmin,it->second);
for(it=f[y].begin();it!=f[y].end();++it) hymin=min(hymin,it->second);

map<int,int> g;
// x の下に y をつなげるとき
for(it=f[x].begin();it!=f[x].end();++it){
if(it->first<d){
int h_new=max(it->second,hymin+1); // マージしてできる木の高さ
if(g.count(it->first+1)==0){
g[it->first+1]=h_new;
}
else{
g[it->first+1]=min(g[it->first+1],h_new);
}
}
}

// y の下に x をつなげるとき
for(it=f[y].begin();it!=f[y].end();++it){
if(it->first<d){
int h_new=max(it->second,hxmin+1);
if(g.count(it->first+1)==0){
g[it->first+1]=h_new;
}
else{
g[it->first+1]=min(g[it->first+1],h_new);
}
}
}

// 本当につなげる
f[x]=g;
f[y].clear();
a[x]+=a[y]; a[y]=x;
}
};

int main(){
int T0; scanf("%d",&T0);
for(int T=1;T<=T0;T++){
int n,d; scanf("%d%d",&n,&d);
union_find U(n);
rep(i,n-1){
int a,b; scanf("%d%d",&a,&b); a--; b--;
U.solve(a,b,d);
}
printf("Case #%d: %d\n",T,U.height(U.find(0)));
}

return 0;
}

結局やってることは dp[30000][5000] 解法と同じだと思う。

C.

Twitter で 10^9 の尺取とかいう噂が聞こえてきてなんだそれはという感じ。
よさそうな問題なので解説がきたら復習する。

[ 2013/02/09 追記 ]
解いた。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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