D. Suitable Replacement

1500
  • Quiz
  • AC
  • 問題理解
    • 読解に苦労したが、sの上にtを滑らせていき、完全一致する回数を最大化するように?を埋めよという問題
  • 英語
    • largest number of non-intersecting occurrences of string t
    • ｔ同士が重ならないようにしつつ、ｓ上のｔの出現を最大化した値がsuitability
  • 解説
    • sはswap可能なので好きな順序にでき、この問題は各文字の統計だけ見ればいい
    • tを何個完全一致できるかには単調性があるので、個数を固定して二分探索すればいい
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    string s,t;cin>>s>>t;

    map<char,ll> mps,mpt;
    for(char c : s) mps[c]++;
    for(char c : t) mpt[c]++;

    // a個作れる？
    auto f = [&](ll a){
      ll need=0;
      rep(i,26){
        char c = 'a'+i;
        if(mpt[c]*a > mps[c]) need += mpt[c]*a-mps[c];
      }
      if(need<=mps['?']){
        return true;
      }else{
        return false;
      }
    };

    // 1個も作れない
    if(f(1)==false){
      debug("early");
      for(char c : s){
        if(c=='?'){
          cout << 'a';
        }else{
          cout << c;
        }
      } 
      cout << endl; return 0;
    }

    ll left=1; // can
    ll right=1e6+10;//can't
    while(left+1!=right){
      ll center = (left+right)/2;
      if(f(center)){
        left=center;
      }else{
        right=center;
      }
    }
    // left個は作れる
    debug("can",left);
    stringstream ss;
    rep(i,26){
      char c = 'a'+i;
      if(mpt[c]*left > mps[c]){
        ll need = mpt[c]*left - mps[c];
        // cをneed個補充する必要
        mps['?']-=need;
        while(need--)ss<<c;
      }
    }
    // あまりはzにでもしておく
    while(mps['?']--){
      ss<<'z';
    }
    string replace=ss.str();
    debug(replace);
    ll idx=0;
    for(char c : s){
      if(c=='?'){
        cout << replace[idx++];
      }else{
        cout << c;
      }
    }
    cout << endl;

    return 0;
}