Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11671 - Sign of Matrix (この記事を編集する[管理者用])

Source

Regional Warmup 1 (2009-09-13)
UVa 11671

問題概要

N*Nの行列が与えられる.最初は全部の要素が0.
ある行,または列を選んで,その全ての要素を+1または-1することができる.
最終状態として,各マスが,正か0か負か,という状態が与えられるので,それを満たすために必要な最小の変形回数を求める問題.
Nは100以下.

解法

それぞれの行を+1した回数,それぞれの列を-1した回数に関する関係式を考える.
(ある行を-1するというのは,+1を-1回やったと考える)
すると,各マスによって,どっちが大きい,小さいという関係がN*N個与えられ,それを満たせば良い.
後は,適当にその関係式を満たすようにgreedyに番号を振ってやって,適当にシフトすれば良い.
ジャッジデータがアップロードの際に壊れてたらしく,最近rejudgeされた.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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