Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12496 - Fisherman's Dilemma (この記事を編集する[管理者用])

Source

Another Bangladeshi Contest (2012-10-07)
UVa 12496

問題概要

n*m (200*200以下) のグリッドの各セルに20以下の非負整数が書かれている.
そのグリッドに含まれる全ての長方形の領域の中から等確率でランダムに1つ選ぶ.
その長方形の中に書かれている整数の和がK以上になる確率を既約分数の形で答える問題.

解法

累積和を求めておいて,各長方形領域に含まれる数字の和をO(1)で求められるようにしておく.
左上の点はすべて調べるとして,下のラインを固定した時,右のラインの右端を調べていく.
右端は,下に移動すれば徐々に左に移動していくので尺取メソッドっぽく求められる.
O(nm(n+m)).

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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