Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11735 - Corner the Queens (この記事を編集する[管理者用])

Source

A Bangladeshi Contest (2009-12-19) (blog)
UVa 11735

問題概要

Wythoff's gameしたとき,2つの山の石の数がx,yとして,
 xがx1以上,x2以下
 yがy1以上,y2以下
のところに,どれぐらいの割合で先手必勝パターンかを求める問題.
x1,x2,y1,y2は1000000以下ぐらいで,テストケースは15000個ぐらい.

解法

(1, 2), (3, 5), (4, 7), (6, 10)…が含まれている数と(2, 1), (5, 3), (7, 4), (10, 6)…が含まれている数とを別々に数える.
xもyも単調増加なので,2分探索で含まれている数は求めれる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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