Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Timus 1882 - Old Nokia (この記事を編集する[管理者用])

Source

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

問題概要

携帯に登録された,アルファベット順にN人の友人の名前が与えられる.文字数の合計は100000以下.
1つのキーを押すのに1秒かかるとして,N人それぞれの名前を選択するまでに必要な最小時間を求める問題.
最初はアルファベット順で最小の人を選択している.
上キー,下キーを押すと,リストに表示されてるうちで,次の人,前の人に選択を移せる.
リストはサイクリックで,最初の人の前は最後の人,という感じ.
また,文字を入力することができる.
aを入力するのには1秒,bを入力するには2秒,cは3秒,dは1秒,eは2秒,…,zは4秒かかる.問題文の表参照.
文字を追加したら,今まで入力した文字列をプレフィックスとする名前のみ表示される.
その際,選択は,表示されてるうちの辞書順最小の人が選択される.
文字を削除 (最後に入力した文字を1秒で削除できる) すると,リストはもの文字を入力する前の状態に戻るが,選択されている人は変化しない.
文字を入力したときに,表示される人が0人になるような入力は,ボタンを押しても入力できない.そして不快な音がなる.

解法

削除は高々1回しか行う必要はない.
まず,削除せずに上下キーのみで移動する場合,一文字入力して削除して上下キーで移動する場合を全部試す.
後は,一文字入力して,表示される範囲を区切って,同じ操作を再帰的に行う.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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