TopCode SRM 336 Div1 Medium LikelyWord

問題

文字列が辞書順に並んだ辞書dictionary[]が与えられる。
k文字からなる単語を一つ、ランダムに生成する。

ただし、dictionaryの要素に一致するような単語は生成されない。
一致しない単語はすべて等確率で生成される。
生成した単語を辞書に入れるとき、辞書の何番目に入る確率が一番高いか、求めよ。

一番確率が高いインデックスが存在しなかったり、複数存在する場合は-1を返せ。

制約条件

辞書の要素≦50
辞書の各単語の長さ≦50
辞書の各単語は英小文字からなる
k≦10

方針

簡単に言えば、dic[i+1]-dic[i]の間隔が最も長いところが最も確率の高いところ。
なので、文字列を数字と見て引き算をすればよい。

辞書の単語がk文字ぴったりか、k文字より長いか、k文字より短いかで境界条件が微妙に変わるのがやっかい。

• dic[i+1]がk文字ぴったりだったら、その文字は間に入れないので-1
• dic[i+1]がk文字より短かったら、dic[i+1]には'a'をk文字になるまでつめて、更にその文字列自身は間に入れないので-1
• dic[i]がk文字より短かったら、dic[i]には'a'をk文字になるまでつめて、その文字列は入れるので+1

ソースコード

string f(string a,string b,int c){
	for(int i=a.size()-1;i>=0;i--){
		int d=(int)a[i]-b[i]-c;
		if(d>=26){
			d-=26;
			c=-1;
		}
		else if(d<0){
			d+=26;
			c=1;
		}
		else c=0;
		a[i]='a'+d;
	}
	if(c)a[0]-=26;
	return a;
}

class LikelyWord {
	public:
	int likely(vector <string> dic, int k) 
	{
		dic.insert(dic.begin(),string(k,'a'));
		dic.pb(string(k,'z'));
		
		int n=dic.size();
		int sml[52]={}, just[52]={};
		rep(i,n){
			if(dic[i].size()==k)just[i]=1;
			if(dic[i].size()<k){
				sml[i]=1;
				while(dic[i].size()<k)dic[i].pb('a');
			}
			dic[i]=dic[i].substr(0,k);
		}
		sml[0]=1; just[n-1]=0;
		string mx;
		int ans=-2;
		
		rep(i,n-1){
			string d=f(dic[i+1],dic[i],just[i+1]+sml[i+1]-sml[i]);
			if(ans==-2||d>mx)ans=i, mx=d;
			else if(d==mx)ans=-1;
		}
		return ans;
	}
};