Submission #64781596

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#include <numeric>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#include <numeric>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const ll INF = 1e18;

struct SegmentInfo {
    int startPos;          // 元文字列でのセグメント開始位置
    int length;            // セグメントの長さ
    vector<int> pref;      // pref[i] = [0..i-1] で置ける最大'o'数
    vector<int> suff;      // suff[i] = [i..L-1]  で置ける最大'o'数
    int maxWithoutForce;   // セグメント全体[0..L-1] で置ける'o'の最大数
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;  // K が大きい場合もあるので long long
    cin >> N >> K;
    string S;
    cin >> S;

    // まず、強制'o'の個数を数えつつ、隣に'?'があれば'.'に変換
    vector<char> T(N);
    for(int i=0; i<N; i++){
        T[i] = S[i];
    }

    long long forced_o_count = 0;
    for(int i=0; i<N; i++){
        if(T[i] == 'o'){
            forced_o_count++;
            // 左右の'?'を'.'に変える
            if(i > 0 && T[i-1] == '?'){
                T[i-1] = '.';
            }
            if(i < N-1 && T[i+1] == '?'){
                T[i+1] = '.';
            }
        }
    }
    long long needed = K - forced_o_count;  // "残り"必要な'o'の数

    vector<SegmentInfo> segments;
    vector<int> segIndexOf(N, -1);  // i番目がどのセグメントに属するか(なければ-1)
    {
        int i = 0;
        int segId = 0;
        while(i < N){
            if(T[i] == '?'){
                int st = i;
                while(i < N && T[i] == '?'){
                    i++;
                }
                int en = i - 1;
                int length = en - st + 1;

                SegmentInfo seg;
                seg.startPos = st;
                seg.length = length;
                seg.pref.resize(length+1);
                seg.suff.resize(length+1);


                seg.pref[0] = 0; 
                if(length >= 1) seg.pref[1] = 1; 
                for(int x=2; x<=length; x++){
                    seg.pref[x] = max(seg.pref[x-1], seg.pref[x-2] + 1);
                }

                seg.suff[length] = 0;
                if(length >= 1) seg.suff[length-1] = 1;
                for(int x=length-2; x>=0; x--){
                    seg.suff[x] = max(seg.suff[x+1], 1 + ((x+2 <= length)? seg.suff[x+2]:0));
                }

                // セグメント全体の最大'o'数(強制なし) = pref[length]
                seg.maxWithoutForce = seg.pref[length];

                // segIndexOf を設定
                for(int pos = st; pos <= en; pos++){
                    segIndexOf[pos] = segId;
                }
                segments.push_back(seg);
                segId++;
            }
            else {
                i++;
            }
        }
    }

    long long sum_max = 0;
    for(auto &seg : segments){
        sum_max += seg.maxWithoutForce;
    }


    auto getMaxIfDot = [&](const SegmentInfo &seg, int j){
        int L = seg.length;
        int leftVal = seg.pref[j];       // [0..j-1]
        int rightVal = (j+1 <= L)? seg.suff[j+1] : 0;  // [j+1..L-1]
        return leftVal + rightVal;
    };
    auto getMaxIfO = [&](const SegmentInfo &seg, int j){
        // j番目を'o'固定 => +1 しつつ j-1, j+1 は使えない
        // => 左[0..j-2], 右[j+2..L-1] の最大 'o'数 +1
        int L = seg.length;
        int leftVal = 0;
        if(j-1 >= 0){
            leftVal = seg.pref[j-1]; // [0..(j-1)-1] => [0..j-2]
        }
        int rightVal = 0;
        if(j+2 <= L){
            rightVal = seg.suff[j+2];  // [j+2..L-1]
        }
        return 1 + leftVal + rightVal;
    };

    // 実際に各文字を決めていく
    for(int i=0; i<N; i++){
        if(T[i] == 'o' || T[i] == '.'){
            // 既に決まっているので変更なし
            continue;
        }
        // ここに来るのは T[i] == '?'
        int segId = segIndexOf[i];
        auto &seg = segments[segId];
        int j = i - seg.startPos;  // セグメント内での位置

        long long segMax0 = seg.maxWithoutForce;  // そのセグメントを強制なしで置いたときの最大個数
        long long sumOthers = sum_max - segMax0;  // 他セグメントの最大合計

        // '.' にする場合
        // 範囲 [0.. getMaxIfDot(j)]
        long long maxIfDot = getMaxIfDot(seg, j); 
        bool can_be_dot = false;
        if(0 <= needed && needed <= sumOthers + maxIfDot){
            // 下限は0なので needed>=0 でOK
            can_be_dot = true;
        }


        long long maxIfO = getMaxIfO(seg, j);
        bool can_be_o = false;
        if(1 <= needed && needed <= sumOthers + maxIfO){
            can_be_o = true;
        }

        // 両方判定
        if(can_be_o && !can_be_dot){
            T[i] = 'o';
        }
        else if(!can_be_o && can_be_dot){
            T[i] = '.';
        }
        else if(can_be_o && can_be_dot){
            // 両方アリ
            T[i] = '?';
        }
    }
    cout << string(T.begin(), T.end()) << "\n";
    return 0;
}

Submission Info

Judge Result