Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4859 - Knockout Tournaments (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4859

問題概要

1回のトーナメントに出場したとき,可能性があるのは以下のとおり
 Round kで敗れた : Round kまで進出とみなす : 勝数k-1 負数1 (k=1,2,3,4,5,6,7,8)
 Round 8に勝った : Round 8まで進出とみなす : 勝数8 負数0
合計の勝数と負数が与えられる.
何回戦まで進出したかの値の平均値を知りたいのだけど,何回トーナメントに出たかわからないので,
何回トーナメントに出たかは,ありうる値を等確率で取るとする.
何回戦まで進出したかの平均値を求める問題.
また,そのような勝数,負数になることがないならそれを指摘する.
勝数と負数は2000000000以下.

解法

結局答えは
 (W+L) * ( H[A]-H[B] ) / (A-B)
の形で書ける.
Wが勝数,Lは負数,Aはあり得るトーナメント出場回数の最大値,Bはトーナメント出場回数の最小値-1,Hは調和級数
 H(k) = 1 + 1/2 + 1/3 + … + 1/k
L=0でWが8の倍数じゃないときのみ不可能.
調和級数は大きい時は近似公式を使う.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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