2003/Contest/世界大会

Problem D : Insecure in Prague †

問題概要 †

文字列 p をある方法にしたがって暗号化した文字列 c が与えられる。暗号文 c を復号してもとの文字列 p を出力する。ただし p の長さが最大となるように復号する。一意に復号できないときは「Codeword not unique」を出力する。

解法 †

基本的には brute-force。

n を大きいほうからループ。その内部で s，i，t，j の順にループする。s，i が決まればもとの文字列 p は決まるので，あとは対応する t，j の存在を確認すればよい。

詳しくはソースファイル参照。

議論・その他 †

• brute-force＋適当な枝狩りという方針はすぐに気づくと思うが，枝狩りの方針を誤ると大変なことになるので注意すること。（泉，2004/04/18）

ファイルを添付する †

izumi_D.cpp