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; } };