Submission #1454080

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))

#define MOD 1000000007
#define INF 1000000000
#define MAX_N 105

int N, K;
string S;
int alph[256];      // 各アルファベットがどれだけあるか

int main()
{
    ZERO(alph);
    cin >> N >> K >> S;
    vector<char> sorted;
    REP(i, S.length()) {
        sorted.push_back(S[i]);
        alph[S[i]]++;
    }
    SORT(sorted);
    string ans = S;
    REP(changed, S.length()+1) {
        int tmp_alph[256];
        REP(i, 256) { tmp_alph[i] = alph[i]; }
        string tmp = "";
        // changed 文字数ぶん辞書順にする
        REP(i, changed) {
            tmp += sorted[i];
            tmp_alph[sorted[i]]--;
        }
        // 残りは（なるべく）そのまま
        for(int i = changed; i < S.length(); ++i) {
            if(tmp_alph[S[i]] <= 0) {
                // もうないなら別の文字が入る
                tmp += "?";
            } else {
                tmp += S[i];
                tmp_alph[S[i]]--;
            }
        }
        // ? の部分に辞書順で文字を入れる
        // この部分はどっちにしろ元の位置から変わるので、辞書順で入れてしまって OK
        REP(i, tmp.length()) {
            if(tmp[i] == '?') {
                REP(j, 256) {
                    if(tmp_alph[j] > 0) {
                        tmp[i] = (char)j;
                        tmp_alph[j]--;
                        break;
                    }
                }
            }
        }
        // どれだけ変わっているか
        int diff_s = 0;
        REP(i, S.length()) {
            if(S[i] != tmp[i]) { diff_s++; }
        }
        //if(diff_s > K) { break; }
        if(diff_s <= K) { ans = tmp; }
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result