Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12001 - UVa Panel Discussion (この記事を編集する[管理者用])

Source

World Finals Warmup II (2011-05-07) (blog)
UVa 12001

問題概要

N人 (200以下) の人と,M個 (50以下) の国がある.それぞれの人がどの国出身かが与えられる.
3人の人を,
 3人全てが違う国出身となるように, または
 3人全てが同じ国出身となるように
選ぶ選び方を求め,さらに,
4人の人を
 少なくても3人が全てが違う国出身となるように, または
 少なくても3人が全てが同じ国出身となるように
選ぶ選び方を求める問題.

解法

どの国から何人選ぶか,というのを全探索する.O(M^4)程度だが通る.
ある国以降の国にいる人の人数の和を覚えればO(M^3)になるし,もうちょっと色々計算しておくとO(M^2)にもできる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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