mayoko’s diary

プロコンとかいろいろ。

すぬけのお誕生日コンテスト B - Snuke

問題(というかトップページ)

snuke21.contest.atcoder.jp

解法

's' を消せるので, 's' が連続した部分文字列の直後の文字 c が c < 's' を満たすなら, なるべくその 's' は消したほうが得になります。逆に, c > 's' を満たすなら, なるべく消したくないですが, 消さないといけないとしたら, 辞書順に影響を与えにくい後ろから消していくのが良いです。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    string t, ans;
    cin >> t;
    int n = t.size();
    int cur = 0;
    while (cur < n) {
        if (t[cur] == 's') {
            int i = cur;
            while (i < n && t[i] == 's') i++;
            if (t[i] < 's') {
                if (i-cur > k) {
                    for (int j = 0; j < i-cur-k; j++) ans += 's';
                    k = 0;
                } else {
                    k -= i-cur;
                }
            } else {
                ans += t.substr(cur, i-cur);
            }
            cur = i;
        } else {
            ans += t[cur++];
        }
    }
    string ret;
    reverse(ans.begin(), ans.end());
    for (char c : ans) {
        if (c == 's' && k > 0) {
            k--;
        } else {
            ret += c;
        }
    }
    reverse(ret.begin(), ret.end());
    cout << ret << endl;
    return 0;
}