SRM545 Div1 Easy - StrIIRec

ちょっと面白かった
540台はなかなか解き応えのある問題が多い

問題

以下の条件を満たす文字列を作れ
1) 長さnで、アルファベット26文字の最初のn文字を1文字ずつ使っている
2) 転倒数がk以上
3) 辞書順でs以上
4) これらの条件を満たす中で辞書順最小

解法

辞書順最小ってことで手前から1文字ずつ決めていく
i文字目の候補は、今まで決めた文字列が既にsより大きければa〜zで、そうでなければs[i]〜zだけになる
i文字目をcにすると、n文字のうちまだ使っていない & cより小さい文字の個数(=incとする)だけ転倒数が増えることが確定する
更に、c以外でまだ使っていない文字の個数をtとすると、最終的な転倒数が最大になるのは明らかに今後のt文字を降順に並べた場合で、
そのとき転倒数は t-1 + t-2 + ... + 1 = (t-1)t/2 (=mxとする)だけ増える
i-1文字目までで確定している転倒数の和がinvであるとき、inv+inc+mxがk以上であればi文字目はcにしても問題なく、そうでなければ無理
これを繰り返せば答えが求められる

class StrIIRec {
public:
	string recovstr(int n, int k, string s) {
		string res;
		int r[20] = {}, bg = 0, inv = 0;
		rep(i,n) r[i] = 1;
		rep(i,n) reps(j,(bg ? 0 : s[i]-'a'),n) {
			if (!r[j]) continue;
			int inc = accumulate(r, r+j, 0),
				t = accumulate(r, r+20, -1), mx = t*(t-1)/2;
			if (inv+inc+mx<k) continue;
			res.push_back('a'+j);
			inv += inc;
			r[j] = 0;
			if (i>=s.size()-1 || j>s[i]-'a') bg = 1;
			break;
		}
		return res;
	}
};