Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12681 - Decoding the Hallway (この記事を編集する[管理者用])

Source

An european regional / ACM ICPC, Southwestern Europe Regional Contest (2013-11-23)
UVa 12681

問題概要

最初線分が $1$ 個あって,方向は左から右に進むことを考える.
時間 $t=1$ で,$1$ 回線分を左方向に折り曲げる.($2$ つの線分に別れる)
時間 $t=n+1$ では,時間 $t=n$ の各線分に対して,進行方向にそって,左,右,左,右,・・・と折曲げていく.
問題文の図を参照.
時間 $t=n$ の線分を移動するときに,曲がる方向の列を文字列として $S_n$ と書く.
$n$ と文字列 $T$ が与えられるので,$T$ が $S_n$ の部分文字列かどうかを判定する問題.
$n \leq 1000$
$|T| \leq 100$

解法

$S_1 = {\rm L}$ で
 $S_{n+1} = S_n + {\rm L} + f(S_n)$
で求められる.ただし,$f(x)$ は $x$ の文字列の順番を反転させた上に,LとRを反転させたもの.
この規則から,十分大きな $n$ 以降は,$100$ 文字以上の部分文字列が新しく増えることはないので,$n$ が大きい時は,$n=10$ ぐらいに落とす.
後は愚直に判定すれば良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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