- 与えられた長さNの文字列の連続部分文字列 [s,e], (s, e in [0, N) ) １コを反転させる。どこを反転させると辞書順最小になるか。
- 解が複数あるときは s*10000+e が最小のものを返す.
- 1≦|文字列|≦2500
- 全探索だと N^3 でだめ
- 真ん中くらいに a があるときは最初から a の位置まで反転させればだいたい最小
- abdc は dc を反転させないといけない。これはどうする？
- たぶん ab の部分はすでに解（辞書順最小）の一部だから反転させなくてよいのだ
- 仮説→反転の始点は、文字列をソートしたものと文字列が一致しない最初の位置 B であるとしていい
- （証明）Bより左のB'では、B'の文字より小さい文字は右側にないので反転してもいいことない。
- Bより右側のB'ではBより小さい文字が右側にあるのにBとその文字を交換することができない。なのでBじゃないとだめ
- というわけで B〜E in [B, N) を反転した文字列を全て列挙して (文字列, E) が最小のものの B, E を返せばいい
- 写経 challenge 1 コ成功.
- 証明済みのコードを提出したので、結果だけじゃなく質的にも良かったと思う。
class SubstringReversal {
public:
vector <int> solve(string S) {
vector<int>ans(2);
int N=S.size();
string ref=S;
sort(ALL(ref));
if(S==ref) {
return ans;
}
int B=N-1;
REP(i, N) if(S[i]!=ref[i]) {B=i;break;}
ans[0]=ans[1]=B;
if(B<N-1) {
vector<pair<string, int> > w;
RANGE(i, B, N) {
string s = S.substr(B, i-B+1);
reverse(ALL(s));
w.PB(MP(s+S.substr(i+1), i));
}
sort(ALL(w));
ans[1]=w[0].second;
}
return ans;
}
};
