L. Lexicography

• Quiz
  • https://codeforces.com/problemset/problem/1267/L
• AC
  • https://codeforces.com/contest/1267/submission/92214492
• 問題理解
  • 部分文字列で切り取るわけではなく、与えられる文字列sの文字を好きな順番で使っていいことに注意
  • なのですべての文字列は辞書順にできる
  • 作られた文字列n個のうち、k番目の文字列を辞書順最小にせよ
• 解説
  • editorialの補足。t (index) というは文字列内のindexではなく、k番目の文字列と今の所一致している文字列の最小位置 (t番目) (下図参照)

code (editorialに合わせています)

int main(){
    // input
    ll n,l,k;cin>>n>>l>>k;
    k--;
    string s;cin>>s;

    // character count
    VI C(26);
    for(char c : s){
      ll v = c-'a';
      C[v]++;
    }

    VS S(n); // n本の文字列
    ll t = 0; // same prefix index
    
    // phase 1
    ll idx=0;
    while(S[k].size()<l){
      if(C[idx]==0){
        idx++;
        continue;
      }
      ll Cp = C[idx];
      char c = 'a'+idx;
      if(Cp>k-t){
        // enough
        FOR(i,t,k+1) S[i] += c;
        C[idx] -= k-t+1;
      }
      else{
        FOR(i,t,t+Cp) S[i] += c;
        t += Cp;
        C[idx] = 0;
      }
    }

    // phase 2
    idx=0;
    rep(i,n){
      if(S[i].size()==l) continue;
      
      while(S[i].size()<l){
        while(C[idx]==0)idx++;
        char c = 'a'+idx;
        S[i] += c;
        C[idx]--;
        if(C[idx]==0)idx++;
      }
    }

    sort(ALL(S));
    for(string s : S){
      p(s);
    }

    return 0;
}