Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4858 - Digital Matrix (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Dhaka (Bangladesh) - 2010/2011
UVa: Dhaka Regional Semilive (2010-11-06) (blog)
LiveArchive 4858

問題概要

1~Kまでの数字が書かれた正方行列A,Bがそれぞれ与えられる.
1回の操作でAの1つの要素を選び,自由に1~Kの数字に書き換えることができる.
ただし,その操作の後,Aが対称行列になるような操作は認められない.
最小で何回の操作で行列Bと一致させることができるかを求める問題.できないならそれを指摘する.
行列のサイズは100以下.

解法

超adhoc.
まず,A=Bなら0.
Bが対称行列なら不可能.
基本的には,答えは,異なってる要素数だけど,
(i,j)要素と(j,i)要素を入れ替える操作のみ必要で,どれを先にやっても一時的に対称行列になっちゃうなら答えに+1.
また,1個しか入れ替えるものがなく,K=2なら,別のところで対称性を崩して戻さないといけないから+2.
また,サイズが2*2とかで,K=2なら,対称性を崩せないので不可能.
とか色々場合分けする.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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