POJ 3359 Wordfish

問題

文字列が与えられる。
文字列の順列のうち、与えられた文字列の次の10個および前の10個に対して、
隣り合う文字間の距離の最小値が最大のもの、およびその値を求めよ。

ただし文字aと文字b間の距離とはabs((int)a-(int)b)を意味する。

方針

問題文が凄くあいまいだが、
文字間の距離は単に文字を数字とみて引き算して、絶対値を取ればいいらしい。
しかも、zの次がaだったりもしない。意味不明。

next_permutationおよびprev_permutationで前後の10順列を取り、
それぞれについて隣り合う文字の距離を計算してやればよい。

ナイーブに実装しておｋ

ソースコード

int n,md;
string in;

int main()
{
	while(cin>>in){
		n=in.size();
		string tmp=in, ans;
		
		md=-1;
		rep(it,10){
			next_permutation(all(tmp));
			int mn=inf;
			rep(i,n-1)mn=min(mn,abs(tmp[i]-tmp[i+1]));
			if(md<mn||md==mn&&ans>tmp)ans=tmp, md=mn;
		}
		tmp=in;
		rep(it,10){
			prev_permutation(all(tmp));
			int mn=inf;
			rep(i,n-1)mn=min(mn,abs(tmp[i]-tmp[i+1]));
			if(md<mn||md==mn&&ans>tmp)ans=tmp, md=mn;
		}
		cout<<ans<<md<<endl;
	}
	return 0;
}