スポンサーサイト

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

Codeforces Beta Round #69

2011/04/20 00:15 ~ 02:15 (JST)
Codeforces Beta Round #69 (Div.1 Only) の参加記録。

初の Div.1 Only 回。
Div.2 Only と並行して行われた。3 問がオーバーラップしている。

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

結果

A. WA, AC (00:46)
B. WA, Hacked, AC (01:20)
C. -
D. -
E. -
Hacks : +-0 (0/0)
Standing : 219/458
Rating : 18621807


問題

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

A. Heroes
7 人の勇者が 3 人の魔王を倒す。
勇者は 3 つのグループに分かれて、それぞれのグループがそれぞれの魔王を担当する。
各グループは少なくとも 1 人の勇者を含まなければならない。

各魔王には、倒されたときに勇者が得られる経験値が割り当てられている。
K 人の勇者からなるグループが魔王を倒したとき、グループ内の各勇者には経験値が K 等分 (切捨て) して分配される。

また、勇者 A は勇者 B が好きであるという関係がいくつか与えられる。
好きな勇者どうしが同じグループにいるような組の個数をグループの liking と定義する。

勇者が得られる経験値の最大値と最小値の差が最小になるようにグループ分けせよ。
そのようなグループわけが複数考えられるときは、グループの liking の和が最大になるようにせよ。

B. Falling Anvils
実数 p ∈ [0, a], q ∈ [-b, b] が一様ランダムに選ばれるとき、
x2 + (√p) x + q = 0
が少なくとも 1 つの実根をもつ確率を求めよ。

1 ≦ テストケースの数 ≦ 10000
0 ≦ a, b ≦ 106 : 整数

C. Beavermuncher-0xFF
木にビーバーがたくさんいる。
木は n 頂点からなる閉路をもたない連結グラフである。
頂点 u には ku 匹のビーバーがいる。

Beavermuncher-0xFF という名前の何かが、根から出発してビーバーを食べていく。
Beavermuncher-0xFF はビーバーが 1 匹以上いる (隣接する) 頂点にのみ移動できて、移動したときにちょうど 1 匹のビーバーを食べる。
Beavermuncher-0xFF は最終的に根に戻ってこなくてはいけない。
Beavermuncher-0xFF が食べることのできるビーバーの最大数を求めよ。

1 ≦ n ≦ 105
1 ≦ ku ≦ 105

D.

E.

解答

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

A.
map<string,int> f;
bool like[7][7];
int perm[7];

#define EXP first
#define LIKE second
pair<ll,int> solve(int s,int e,ll ex){
int n=e-s,cnt=0;
for(int i=s;i<e;i++)for(int j=s;j<e;j++){
if(i!=j) cnt+=like[perm[i]][perm[j]];
}
return mp(ex/n,cnt);
}

int main(){
f["Anka"]=0;
f["Chapay"]=1;
f["Cleo"]=2;
f["Troll"]=3;
f["Dracul"]=4;
f["Snowy"]=5;
f["Hexadecimal"]=6;

int n; cin>>n;
rep(i,n){
string p,dummy,q; cin>>p>>dummy>>q;
like[f[p]][f[q]]=true;
}
int a,b,c; cin>>a>>b>>c;

pair<ll,int> ans(1LL<<61,1);
rep(i,7) perm[i]=i;
do{
rep(j,7)for(int i=1;i<j;i++){
pair<ll,int> tmp1=solve(0,i,a);
pair<ll,int> tmp2=solve(i,j,b);
pair<ll,int> tmp3=solve(j,7,c);
ll dif=max(max(tmp1.EXP,tmp2.EXP),tmp3.EXP)-min(min(tmp1.EXP,tmp2.EXP),tmp3.EXP);
int likesum=tmp1.LIKE+tmp2.LIKE+tmp3.LIKE;
ans=min(ans,mp(dif,-likesum));
}
}while(next_permutation(perm,perm+7));

cout<<ans.first<<' '<<-ans.second<<endl;

return 0;
}

すべてのグループ分けについて調べる。
next_permutation で全部の順列を生成して、2 箇所に区切りを入れる方法で実装したけど、DFS でやる方が自然で無駄もなかった。

B.
int main(){
int T; scanf("%d",&T);
while(T--){
double a,b,p; scanf("%lf%lf",&a,&b);
if (b==0) p=1;
else if(a==0) p=0.5;
else{
if(a<4*b) p=a*b+a*(a/4)/2;
else p=a*b+((a-4*b)+a)*b/2;
p/=a*(2*b);
}
printf("%.9f\n",p);
}
return 0;
}

p, q は一様分布に従うから、確率を 2 次元平面上の面積で考えると分かりやすい。

考えられる全体は、
0 ≦ p ≦ a, -b ≦ q ≦ b.
これは、軸に平行な長方形。

少なくとも 1 つの実根をもつ確率は、2 次方程式の判別式が非負であればいいので、
0 ≦ p ≦ a, -b ≦ q ≦ b, q ≦ 4p.
これは、a, b の値によって、四角形 (台形) になるか五角形になるかが決まる。

以上は、a ≠ 0, b ≠ 0 の場合で、0 がある場合は図形が縮退してしまうことに注意。
そのケースは別個に考えないといけない。

C. (時間外)
int a[100000];
vector<int> tree[100000];

ll dfs(int u,int prev){
vector<ll> tmp;
rep(i,tree[u].size()){
int v=tree[u][i];
if(v!=prev && a[v]>=1){
a[v]--;
tmp.push_back(1+dfs(v,u)+1);
}
}
sort(tmp.begin(),tmp.end(),greater<ll>());

int lim=min(a[u],(int)tmp.size());
ll res=accumulate(tmp.begin(),tmp.begin()+lim,0LL);
a[u]-=lim;

rep(i,tree[u].size()){
int v=tree[u][i];
if(v!=prev){
ll m=min(a[u],a[v]);
res+=2*m;
a[u]-=m;
a[v]-=m;
}
}

return res;
}

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

rep(i,n-1){
int u,v; scanf("%d%d",&u,&v); u--; v--;
tree[u].push_back(v);
tree[v].push_back(u);
}

int s; scanf("%d",&s); s--;
printf("%I64d\n",dfs(s,-1));

return 0;
}

[ 2011/09/05 追記 ]

頂点 u に対して
f (u) := u を根とする部分木について、食べられるビーバーの最大数
と定める。
f (root) が答えになる。

任意の頂点 u に注目する。
f (u) をどうやって求めるか?

まず、同じ子に u から 2 回以上訪れるとすれば、2 回目以降はすぐに u に戻る (*) としていい。
( (*) をみたさない経路は、食べられるビーバーの数を変えずに (*) をみたす経路に変換できる (と思う) )

u の子を childi (i = 1, 2, ...m) とする。
f (childi) をすべて求めておく。
f (child1) ≧ f (child2) ≧ ... ≧ f (childm) とする。

ku ≦ m のとき
性質 (*) より
f (u) = Σi = 1 to ku f (childi)
となる。
つまり、食べられるビーバーの数の大きい部分木の方へ Greedy に進めばよい。

ku > m のとき
同様に
Σi = 1 to m f (childi)
だけのビーバーを食べることができるが、これだけでは頂点 u のビーバーがいくらか余ってしまう。
なので、childi に余っているビーバーがいれば、どちらかのビーバーがいなくなるまで uchildi を往復すればいい。

グラフは木なので、同じ状態が何度も呼び出されることはなく、メモ化する必要などはない。
計算量は、DFS 中にソートするので O(n log n) くらい。

ところで、作問者はビーバーに何のうらみがあるんだろう?

D.



E.



感想

次もこの調子だと紫に戻ってしまう。
C. のレベルの問題が解けるようになれば、安定してオレンジに残れるはず。
練習するしかない。

A.
問題文は複雑だが、やることは簡単。
読解問題。
グループの liking を経験値の差とは別に最大化すればいいのかと思ってしまい、1WA.
このことについては、随分たってから Clar が来た。自分でも送ればよかった。

B.
a = 0 はないと勘違いして、1 回 Hack された。
コーナーケースにさえ注意すれば、難しくないはず。
余談だけど、『オイラーの贈物』 の巻末に、これとほぼ同じ問題が載っている。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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