Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12526 - Cellphone Typing (この記事を編集する[管理者用])

Source

Latin America Regional (2012-11-11)
UVa 12526

問題概要

アルファベット小文字のみからなる単語の辞書が与えられる.同じ単語はない.
各単語の長さは80以下で,単語の数は100000以下.(単語長の総和は10^6以下)
単語を入力するとき,以下のように行われる.
 一文字アルファベットを打った時(x文字目),今まで入力された文字列をprefixとなるような単語の集合を考えて,x+1文字目が全部等しいならx+1文字目が自動的に入力される.
 自動的に入力された文字に対しても上の処理が行われる.
それぞれの単語を入力するのに必要なキーの数の平均値を求める問題.

解法

まず,入力をソートする.
後は,愚直に,各キーを押した時,それをprefixとする単語の範囲を求めながら計算していく.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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