TopCoder SRM 572 Div2 Medium NextOrPrev

Div2 MediumはDiv1 Hardを簡単にした問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12454

問題

２つの文字列が与えられる。各文字列内の文字は互いに一致しない。
文字列中の１文字を１つ進めるまたは１つ戻す場合のコストが与えらているので、１つ目の文字列を２つ目の文字列にするときのコストを最小化する問題。
なお、そのような変形ができない場合は-1を返す。

解法

まず、変形が可能かどうかを判定する。
元の文字列から、どの文字がどの文字に変形されるべきかをまず求める。
変形前の文字列の辞書順順序と、変形後の順序が反転していたら変形できないので-1を返せばよい。

それ以外は、各文字を進めながらor戻しながら目的の文字にするだけで、その際のコストの総和を求めればよい。

この問題はDiv1 Hardより以下の点で簡単だね。

• 文字の変形で"z"と"a"がループしなくてよい
• 各文字の変形先が重複しない

class NextOrPrev {
	public:
	int getMinimum(int nextCost, int prevCost, string start, string goal) {
		int i,L,x,y;
		int to[60];
		
		MINUS(to);
		L=start.size();
		FOR(i,L) to[start[i]-'a']=goal[i]-'a';
		
		FOR(x,26) for(y=x+1;y<=25;y++) {
			if(to[x]==-1 || to[y]==-1) continue;
			if(to[x]>to[y]) return -1;
		}
		int num=0;
		FOR(x,26) {
			if(to[x]==-1) continue;
			if(to[x]>x) num += (to[x]-x)*nextCost;
			if(to[x]<x) num += (x-to[x])*prevCost;
		}
		return num;
	}
};
||

*まとめ