Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4740 - Land Division (この記事を編集する[管理者用])

Source

ACM/ICPC Africa and the Middle East - Africa and Arab (Alexandria, Egypt) - 2009/2010
LiveArchive 4740
SPOJ 7778 [ANARC09H] (2010-11-09 03:59追加)

問題概要

2次元平面上にN個の点がある.
真横にK-1回切るか,縦にK-1回切るかして,K個の領域に分ける.
 ∑ |それぞれの領域の点の数 - N/K|
の最小値を求める問題.
Nは100000以下,Kは10以下.

解法

縦に切るか横に切るか両方試して良い方を採用すれば良い.
切り方は,左から見て行って,その領域に含まれる点がN/Kを超える場所の前後の2パターンのみ試せば良いので,2^Kぐらいしか切り方を試さなくて良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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