Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4637 - Repeated Substitution with Sed (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4637
PKU 3803 (2011-01-21 04:19追加)
Aizu 1296

問題概要

初期値の文字列と,目標の10文字以下の文字列が与えられる.
10個以下の変換規則が与えられたとき,目標の文字列を得るためにかかるターン数の最小値を求める問題.
変換規則は,
 X → Y
という形で,現在の文字列の(オーバーラップしてない)部分文字列としてXの部分を前から順番にYに置き換えていくというもの.
XよりYの方が長い.

解法

全探索.
少し計算時間が怪しいように思うのだけど,毎ターン適応できる規則の数がそんなに多くなかったりで間に合う.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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