Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12013 - Entertainment (この記事を編集する[管理者用])

Source

Celebration for the 106th Anniversary of Fudan University (1905-2011) & Warmup for ACM/ICPC 2011 World Finals (2011-05-15) (blog)
UVa 12013

問題概要

テニスをする.
自分のサーブの時の1ポイント取れる確率,自分がサーブでないときの1ポイント取れる確率が与えられる.
3セット取って,勝つ確率を求める問題.
テニスのルールは…,
 4ポイント取ると1ゲーム獲得.ただし2ポイント以上差をつけなければいけない
 6ゲーム取ると1セット獲得.ただし2ゲーム以上差をつけなければいけない
 3セット取ると勝利.
 同じゲームの間はサーブ権は変わらない.ゲームが終わるとサーブ権が変わる.
最初のゲームのサーブ権は自分.

解法

漸化式をたてて.線形方程式を解きまくる.
が,あまりに,愚直にやるとTLEした.
実は,最初のサーブ権がどっちにあっても勝率は変わらないとか,ある程度50%50%より高いと最終的には100%勝てるとかいうのは計算せずに返しちゃうとか,そういうのをやると通った.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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