提出 #64943874

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
const int INF = (1 << 30);
template <typename T> void chmax(T &a, T b) {if (a < b) a = b;}
int main() {
    int n,k; cin >> n >> k;
    string s; cin >> s;
    int ocount = 0;
    for (int i=0; i<n; i++) if (s[i] == 'o') ocount++;
    if (ocount == k) {
        for (int i=0; i<n; i++) if (s[i] == '?') s[i] = '.';
        cout << s << "\n";
        return 0;
    }

    auto calc_dp = [&] (string s) {
        vector dp(n+1, vector<int>(2, -INF));
        dp[0] = {0, 0};
        for (int i=0; i<n; i++) {
            if (s[i] != 'o') chmax(dp[i+1][0], max(dp[i][0], dp[i][1]));
            if (s[i] != '.') chmax(dp[i+1][1], dp[i][0] + 1);
        }
        return dp;
    };
    auto dpl = calc_dp(s);
    reverse(s.begin(), s.end());
    auto dpr = calc_dp(s);
    reverse(dpr.begin(), dpr.end());
    reverse(s.begin(), s.end());

    for (int i=0; i<n; i++) {
        if (s[i] != '?') continue;
        if (max(dpl[i][0], dpl[i][1]) + max(dpr[i+1][0], dpr[i+1][1]) < k) s[i] = 'o';
        else if (dpl[i][0] +dpr[i+1][0] + 1 < k) s[i] = '.';
    }
    cout << s << '\n';
}

提出情報

ジャッジ結果