原問題はこちら

言語の文字列を認識する問題.つまり,長さ 100 までの文字列が与えられ,以上の表に従い,最終的に目標に帰納できるかどうかを判定する問題.

例1: 文字列 aaabbbba および,目標 a が与えられると,
   aaabbbba ⇒ babbbba ⇒ cbbbba ⇒ cbbba ⇒ cbba
      ⇒ cba ⇒ ca ⇒ a
   になるので,帰納できる.

例2: 文字列 bccbbbbb および目標 c が与えられると,どう組み合わせても,文字 c に帰納(収束)できない.つまり,
   bccbbbbb ⇒ c はありえない.

本問題で取り扱う文字は a, b, c の3種類のみ.ただし,与えられる入力文字列が最長 100文字のものもありうる.

1文字を2ビットで表現し,100文字を64ビット整数4つで表現しようと試みたが,シフト演算等がめんどくさくて,途中で諦めてしまった.最終的に,文字列を単に char s[101] で表現する.

また,解答アルゴリズムとして,掲示板ではDP(ダイナミックプログラミング)法が盛んに議論されているが,ここでは単に深さ優先探索+カット技法を用いる.計算結果からみて,DPよりも速いようで,自分では不思議に感じる.

つまり,解答プログラムでは,与えられた文字列に対し,その先頭から末尾まで,2文字ずつ結合させ,トライ(試みる)していく.最終的に目標となる文字に帰納できたら,そこで終了.帰納できなければ,バックトラックして再トライ.

同じ文字列を繰り返しトライしたら,時間的コストがかかりすぎ,所定の10秒以内ではプログラムは終了しない.それを防ぐため,ごく簡単なハッシュ表を利用する.トライするすべての文字列をハッシュ表に登録し,同じトライはやらないことにしている.

以下はここで使うハッシュ表関連の部分.

入力データごとにハッシュ表をクリアすると時間がかかるので,入力データシーケンスに対応する変数 cno もハッシュ表に登録する.

ハッシュ表以外に特筆することはないので,他のことは省略する.

C言語解答プログラム: Solution for UVa 10981 String Morphing (C program)
計算時間: 0.012秒

DPよりも速く計算できて,なんとも不思議.入力データが甘く作られただけかもしれないな.

Comments are closed.

Post Navigation