スポンサーサイト

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

Codeforces Beta Round #83

2011/08/24 00:00~02:00 (JST)
Codeforces Beta Round #83 の参加記録

コンテスト終了からブログを書くまでのスパンが長すぎて、どんなだったか忘れてしまった。

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

結果

A. AC (00:16)
B. WA
C. -
D. -
E. -
Hacks : +-0 (0/0)
Standing : 286/439
Rating : 18361791


問題

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

A. Dorm Water Supply
n 件の家があって、家の間には合計 p 本のパイプが通っている。
パイプには一方向に水が流れている。
各家は、入ってくるパイプと出て行くパイプをそれぞれ高々 1 本もっている。

出て行くパイプのみをもつ家にはタンクが、入ってくるパイプのみをもつ家にはタップが取り付けられている。
タンク,タップの容量は、タンク-タップ間にあるパイプの直径の最小値である。

すべてのタンク,タップの組とその容量を答えよ。

1 ≦ n ≦ 1000
0 ≦ p ≦ n

B. Basketball Team
m 個の寮があり、寮 i には si 人の学生がいる。
自分は寮 h の学生である。

これらの寮生の中から n 人を選ぶ。
自分は必ず選ばれるが、それ以外の n-1 人は一様ランダムに選ばれる。
(自分以外に) 自分と同じ寮の学生が少なくとも 1 人選ばれる確率を求めよ。

1 ≦ n ≦ 100
1 ≦ m ≦ 1000
1 ≦ si ≦ 100

C.

D.

E.

解答

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

A.
struct Edge{
int u,v,w;
Edge(){}
Edge(int U,int V,int W):u(U),v(V),w(W){}
};

int deg[1000];
Edge next[1000];

pii dfs(int u){
if(deg[u]==-1) return make_pair(u,INF);

int v=next[u].v,w=next[u].w;
pii ans=dfs(v);
return make_pair(ans.first,min(ans.second,w));
}

int main(){
int n,m; scanf("%d%d",&n,&m);
rep(i,m){
int u,v,d; scanf("%d%d%d",&u,&v,&d); u--; v--;
next[u]=Edge(u,v,d);
deg[u]++;
deg[v]--;
}

vector<Edge> ans;
rep(u,n) if(deg[u]==1) {
pii a=dfs(u);
ans.push_back(Edge(u,a.first,a.second));
}

printf("%d\n",ans.size());
rep(i,ans.size()) printf("%d %d %d\n",ans[i].u+1,ans[i].v+1,ans[i].w);

return 0;
}

もちろん、家を頂点、パイプを辺としたグラフと思う。
問題の制約から、グラフは特殊な形になる。
具体的には、グラフの各連結成分は、サイクル or (交差しない) 折れ線になる。

なので、折れ線の先を探して、そこから DFS で終端まで調べるというのを、全部の連結成分についてやればいい。
連結成分が折れ線かサイクルかの判定は、頂点の次数を見ると楽。

B. (時間外)
int main(){
int n,m,h,s[1000],ssum=0; scanf("%d%d%d",&n,&m,&h); h--;
rep(i,m) scanf("%d",s+i), ssum+=s[i];
s[h]--; ssum--; n--;

double pr;
if(ssum<n) pr=-1;
else{
pr=1;
rep(i,n) pr*=(double)(ssum-s[h]-i)/(ssum-i);
pr=1-pr;
}

printf("%.15f\n",pr);

return 0;
}

自分の寮以外にいる学生は区別する必要はない。
なので、問題は次のようになる。

(Σsi) - 1 個のボールの中から n - 1 個を選ぶ。
特別なボールが sh - 1 個あって、それを少なくとも 1 つ選ぶ確率はいくらか?


これは高校数学でよくありそうな確率の問題で、答えは
1 - nCr[(Σsi)-sh][n-1]/nCr[(Σsi)-1][n-1]
になる。
ここで、表記の都合上 aCb = nCr[a][b] と書いた。

nCr をまともに計算していては、double を使ってもオーバーフローする。
計算途中で約分してやればいい。

確保する配列のサイズを間違えて WA を出してしまった。

C.


D.


E.

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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