Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12348 - Fun Coloring (この記事を編集する[管理者用])

Source

ACM-ICPC Asia Phuket Regional Semilive (2011-11-06)
UVa 12348

問題概要

m個 (111以下) の集合が与えられる.
それぞれの集合はサイズ3以下で,各要素は数字1~nのどれか.(nは22以下)
1~nの数字を白か黒かに塗り分けて,以下の条件を満たすことが出来るかどうかを判定する問題.
 全ての集合は白い数字も黒い数字も含む

解法

塗り分け方は2^22しかないので枝刈り探索.
制限時間が10秒のところ,0.02秒とかで通ったので,枝刈りはそんなにやらなくても良いのかも.やった枝刈りは以下のとおり.
 最初数字1はどっちかの色に塗ってしまう.
 各集合は要素の最小値でソートして,最小値が一致するなら2番目の値が小さい順にソートする.
 後は,最初の集合から,全パターン塗り分け方を試して,ダメなら枝刈り.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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