Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Timus 1879 - GOV-internship 2 (この記事を編集する[管理者用])

Source

Ural Regional School Programming Contest 2011 (2011-10-22)
Timus 1879

問題概要

整数列s1とs2が与えられる.各要素0以上100000以下.
s1の要素数をn1,s2の要素数をn2とする.n1, n2は100000以下.
最初に,s1の各0要素と,s2の各0要素を好きな数字に変更することができる.
s1はサイクリックと考え,各場所から長さn2の連続する部分列をn1個考える.
その部分列と,s2との差を,異なっている文字数とする.(ハミング距離)
その差の和の最小値を求める問題.

解法

すべての要素がすべての要素と当たるので,答えは
 n1*n2 - マッチする文字数の最大値.
マッチする文字数は,
 Σ s1に含まれるkの個数 * s2に含まれるkの個数 (kについての和)
なので,各文字列にある0は全て同じ数字に変えるのが最適で,
 s1に含まれる0は,s2に含まれる最も多い数字に変更.s2に含まれる0は,s1に含まれる最も多い数字に変更.
 s1,s2に含まれる0はすべて同じ数字に変更
だけを試せば良いことがわかる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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