Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12521

問題概要

N人(5000以下)の人をTチーム(100以下)に以下の条件をみたすように分けたい.
 1) 各チーム,リーダー1人は決まっていて,与えられる.
 2) 各チーム,メンバーの数はちょうどM=N/Tでなくてはいけない.1人は1チームのみに属すことができる.
 3) チームメンバーは,互いに友達でなければいけない.
 4) すべての友達に対して,チームメンバーではない友達は,たかだかfloor(M/2)人でなくてはいけない.
N人の人のTシャツのサイズが与えられる.
各チームはTシャツは,どのサイズが何人分必要かを求める問題.
条件を満たすチーム分けは一意に定まることが保証されている.

解法

チームを組める条件も,チームを組めない条件もやたらきついのに,解が一意に定まることが重要.
適当にやっても求まりそうで,適当に探せば良い.
条件3)より友達でなければ違うチームであることを利用して,
各メンバーに対して,属すことが可能なチームを調べて,一意に定まるならそのチームに入れる,というのを繰り返すだけで通った.
ちゃんと証明してないけど,多分4)から言えそうな気がした.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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