Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12515 - Movie Police (この記事を編集する[管理者用])

Source

XXVI Colombian Programming Contest (2012-10-21)
UVa 12515

問題概要

M個の0,1のみからなる文字列X[i]が与えられる.(Mは1000以下,文字列の長さはそれぞれ100以下)
Q個 (500以下) の文字列Y[i]が与えられるので,それぞれについて,M個の文字列の中で最も似ているものを求める問題.
似ているというのは,以下で定義される距離が最も小さいもの.
 X[i]の部分文字列でY[i]と同じ長さの中で,ハミング距離の最小値
答えが複数存在するなら,その中で最も最初に登場した文字列を返す.

解法

20個ぐらいをひとまとめに見てあげて,ひとまとめの中のi文字目が1なら2^iを足すという風に1つの整数として扱う.
何個ビットが立っているか,2^20まで計算しておけば,20文字までハミング距離がO(1)で計算できるようになるので,だいたい愚直にやるより20倍ぐらい早くなって通る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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