Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1959-84598ee0
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #69 DIV1 (参加記録) (この記事を編集する[管理者用])

2011年04月20日00時15分から2時間,5問.codeforcesルール
[ LINK ]

Codeforcesでは初めてのDIV1とDIV2で問題セットの異なるコンテスト.
DIV1は配点が500-1000-1500-2000-2000でした.

A. Heroes

7人の勇者と3匹のボスがいる.
勇者達は3つのパーティーを作ってボス退治をする.
各勇者はちょうど1つのパーティーに含まれていなければならない.
各ボスの経験値が与えられる.
n人パーティーで経験値eのボスを退治すると,1人あたりfloor(e/n)の経験値が得られる.
また,各勇者が,自分が好きな勇者のリストが与えられる.
勇者Aが勇者Bのことが好きならば(A,B)と書く.
 1) 得られる経験値が最も多い勇者と少ない勇者の差を最小化,その中で
 2) 好きな勇者とできるだけ同じパーティーにする
   つまり,(A,B)かつAとBは同じパーティー なるペアの数を最大化する
そうしたときの経験値の差と,ペアの数を求める問題.

寝過ごした,というか起きたけど布団の中が気持ちよかったので10分近く遅れで参加.
(ホントはもっと遅れてたけど,Codeforcesの方も15分開始が遅れたので正味10分近く遅れ)
問題文なげぇ.
固有名詞出されるとそこで躓く.
これって勇者だっけ,ボスだっけ….
理解.
3^7パターン全探索するだけ.
書く.がりがり.
サンプル通った.提出.pretest passed.

B. Falling Anvils

非負整数a, bが与えられる.
実数pが[0,a]の一様分布,qが[-b,b]の一様分布に従うとき
 x^2 + sqrt(p) * x + q = 0
が少なくても1つ実数解を持つ確率を求める問題.

問題文読みにくい….
と思ったら,ストーリーはよくわからんけど,問題の意味はすんなりわかった.
えっと,とりあえず判別式だ.
判別式ってどうだっけ,根のルートの中身だから….
 p - 4q
が0以上になる確率を求めれば良い.
えっと,pを固定したら,qと確率は線形であるから….(嘘ですよ!)
p=0の時の確率とp=aの時の確率を足して2で割れば良い.
p=0の時は…,えっと…,b=0とかだったら嫌だな.
例外処理しておこう.
 a=0, b=0なら即座に0
 a=0なら即座に1/2
 b=0なら即座に1
よしよし.
じゃ,p=0の時は,1/2でよし.
p=aのときは,-4qが[a-4b,a+4b]まで動くから….
 (a+4b) / 8b
だな.
合わない.
試行錯誤.
a=0の時,最後で2で割るの忘れてた.サンプル通った.
サブミット.WA.えー.
コーナーケース間違えてるよ!
 a=0, b=0なら即座に1
でも,これはpretestにないはず.
あれ….
 (a+4b) / 8b
って確率なのに1超えないか?

aが4bを超えると,pが小さい時に線形で,そこから確率1で固定.
場合分け.
書いた.サブミット.WA.
あれ….
適当にaが大きいケースを試してみる.
1.2とか返ってきた.なんでやねん.
あ,式間違ってる.修正.
サブミット.pretest passed.
苦戦しすぎ….

C. Mushroom Strife

ノード数N (10^5以下) の木が与えられる.
それぞれのノードにいるビーバーの数が与えられる.(各ノード1以上10^5以下)
出発ノードも与えられる.
あるノードからあるノードに移動すると,移動先のノードにいるビーバーを1匹取り除く.
移動先にビーバーがいないと移動できない.
最終的には出発ノードに戻ってこなければいけない.
取り除けるビーバーの総数の最大値を求める問題.

greedyかDPか,どっちかの気がする.
が,DPだと状態数が死ぬなぁ….
うーん.
取り敢えず,行ったり来たりで消費するのは最終手段で,いける場処はできるだけ色々行ったほうが良いんだな.
で,行ったり来たりで消費するのは,子供の方からgreedyに消費していけば良い.
子供の方から組み立てて行けばいいじゃん.
書く.
ちょっとめんどい.
書いた.サブミット.WA.
あれ.
テストケースつくって試す.
行ったり来たりで消費するのを全くしてない.
変数間違ってた….修正.pretest passed.

D. Domino Carpet

ちゃんと読んでない.

E. Martian Food

ちゃんと読んでない.

Hacks

何もせず.

Results

ABC通る.
pretestがだいぶ強力だった.(のだけど,落ちてる人は時々落ちてる)

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1959-84598ee0
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。