TCO2010 OR1

TCOのR1が今夜開かれるということで、裏でプラクティスルームやろうかと思ったら…

TCO過去問のみしか残っていなかったのでやりました。
コーディングミスで大幅タイムロス。痛い。

Easy

二つの文字列のアルファベットをずらすことで同じ文字列を生成しようとしたとき、辞書順で一番早く、かつずらす数をなるべく少なくした結果の文字列を求めよ。

方針

とりあえず文字列が50文字以下なのですべての文字にa〜zを検証してもTLEにはなりません。よってa〜zまでの文字でそのアドレスで一番いいものを選んでいきつなげます。
分かりにくいと思うのでもうちょっと噛み砕いていうと…

string1="s1s2...sn"、string2="t1t2...tn"としたときに
a〜zまでを書く文字ごとに検証する。移動数はmin(abs(sx-c),26-abs(sx-c))+min(abs(tx-c),26-abs(tx-c))と定義できる。(sx,txはそれぞれstring1,string2のx番目の文字、cはa〜zの文字)

まぁこれはコードで見たほうが早いと思います。あんまり上手い言い回し方もないので。

コード

class EqualizeStrings {
public:
   string getEq( string s, string t ) {
     string res="";
     for (int i=0; i<s.length(); i++) {
       char tmp='z'; int div=100;
       for (char c='a'; c<='z'; c++) {
	 int sdiv = min(abs(s[i]-c),26-abs(s[i]-c));
	 int tdiv = min(abs(t[i]-c),26-abs(t[i]-c));
	 if (sdiv+tdiv<div) {
	     //   printf("%d %d\n",sdiv,tdiv);
	     tmp=c;
	   div = sdiv+tdiv;
	 }
       }
       res+=tmp;
     }
     return res;
   }
};

反省

最初にもちょっと書きましたが、tdivの最初のt[i]のところをs[i]としてしまっていて、最後まで苦しみましたorz
その間にTLEコードも検証することに。残ってはいませんが、26進数的に文字列を生成していってそれについて色々検証。というかたちを取りましたが、その場合O(26n*n*n)、つまりO(n^3)となってさすがにTLE。もとのコードに戻ってみたらこの有様です。悔しい…