2.8.4 Crypt Kicker

uva

http://acm.uva.es/p/v8/843.html

カエサル暗号の対応表を作れっていう問題．

とりあえず，アルファベットからアルファベットの写像は全単写でなくてはならないので，

  • あるアルファベットaにどの文字に割り当てられたかを示すM[a]
  • あるアルファベットaにどの文字に割り当てられたかを示すN[a]

とかっていう2つの変数を用意しとく．

後は探索領域を減らすことを考える．入力の文字列は単語単位で割合てなければならないので，まず文字数でデータを格納する部分を分ける．後は，オレの場合だけど，文字列のパターンでも分けることにしてみた．パターンは，文字列の各文字がその文字列中に何回出現するかっていうので作成．このパターン照合に時間がかかるので危険だったけど，9秒くらいでaccept．programming challengeのヒントを見ると，たぶん最大出現回数くらいでも上手く行きそうですね．失敗失敗．