問題
http://community.topcoder.com/stat?c=problem_statement&pm=12516&rd=16016
・ある文字列が与えられる。
・この文字列の2つの場所を選んで、その間の文字列を順番を逆にすることができる。
・順番を入れ替えた後最も辞書順に小さくすることのできる、入れ替える場所(x、y)を
求める。
・ただし同じ文字列が得られるときはyが小さい方、さらにyが小さい時はxが小さい方の場所を
求める。
解き方
・単純に入れ替えるxを小さい方から見ていき、より小さくできる場所があればそこが
最適になりそう。
・入れ替える先に同じアルファベットが複数存在するときは、一番手前にあれば一番手前の
場所になるので最適。
→System Failed.
・選んだところの文字列をすべて逆順、という一番基本のところを軽くスルーしてしまった。
・入れ替える先に同じアルファベットが存在するときは、
入れ替えた後の文字列が小さいものを選ばなければいけない。
・入れ替えたアルファベットすべてに対して探索しても計算量は
2.5*10^3*(1250+2500)=2.5*10^3*3.7*10^3=10^7まではいかないので十分に間に合う。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class SubstringReversal {
public: vector<int> solve(string S) {
int n=S.size();
vector<int> ans(2,0);
FORE(i,0,n){
char ch='z';
FORE(j,i+1,n)if(ch>S[j])ch=S[j];
string str=S;
FORE(j,i+1,n)if(ch==S[j] &&S[i]>S[j]){
string tmp=S;
FORE(k,0,(j-i+2)/2)swap(tmp[i+k],tmp[j-k]);
if(str>tmp){
ans[0]=i,ans[1]=j;
str=tmp;
}
}
if(str<S)return ans;
}
return ans;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class SubstringReversal {
public: vector<int> solve(string S) {
int n=S.size();
vector<int> ans(2,0);
FORE(i,0,n){
char ch='z';
FORE(j,i+1,n)if(ch>S[j])ch=S[j];
string str=S;
FORE(j,i+1,n)if(ch==S[j] &&S[i]>S[j]){
string tmp=S;
FORE(k,0,(j-i+2)/2)swap(tmp[i+k],tmp[j-k]);
if(str>tmp){
ans[0]=i,ans[1]=j;
str=tmp;
}
}
if(str<S)return ans;
}
return ans;
}
};