Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12338 - Anti-Rhyme Pairs (この記事を編集する[管理者用])

Source

ACM ICPC Regional Warmup 2011 (2011-10-29)
UVa 12338

問題概要

N個 (10^5以下) の文字列が与えられる.含まれるのはアルファベット小文字のみ.
文字数の合計は10^6以下ぐらい.
10^6個以下のクエリが与えられる.
各クエリに対して,iとjが与えられるので,i番目の文字列と,j番目の文字列で,最初の何文字が一致しているか,一致している文字数の最大値求める問題.

解法

文字列をソートしておいて,自分と自分の次の文字列と,最初の何文字が一致しているかを最初に計算して配列に記憶しておく.
すると,各クエリに対して,その配列のある範囲の最小値を求める問題に帰着できるのでRMQ (Range Minimum Query) する.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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