Pの競プロ記

競技プログラミングに関することを書きます。

StrIIRec (SRM545 div2 medium)

解法・感想など


この問題は全然解法が分からなかったので、いろいろな方の記事を参考にして解きました。

【問題概要】
文字列(abcdef...)(n文字ある)を並び替えてある条件に合うような文字列を求める問題。
ある条件は以下の通り。
・minStrよりも辞書順で大きい
・minInvよりもinversionの数が大きい

※inversionとは?
(例)文字列 cdba が与えられる。それぞれの文字に注目し、それ以降の文字と比較する。
cに注目すると、 c < d, c > b, c > a よりinversion += 2
dに注目すると、 d > b, d > a よりinversion += 2
bに注目すると、 b > a よりinversion += 1
よって cdba のinversionは5である。


【解法】
まずnext_permutationなどで全通り試そうとすると確実にTLEです。
ですからGreedyにやる必要があります。

辞書順最小を求めるので、できるだけ小さいものから埋めていきます。
i番目(1 <= i <= n)にどの文字を使うかを決めます。
そのときの判別法はこんな感じです。

・i番目に使う文字Cを決める。
・i+1文字目以降に残った文字のなかで一番辞書順で最大になるような文字列を付け加える。
・もしそれでもminStrより辞書順で小さいならその文字Cはダメ。 →continue
・inversionの数を数える。
・もしその数がminInvより小さいならその文字Cはダメ →continue
☆文字Cを使うことができる、i文字目はCで決定。 i+1文字目の探索に入る。

これをn回繰り返せば辞書順最小の文字列を作ることができます。


【感想】
文字列に関する問題は苦手なので、訓練が必要だと思いました。
いろいろな記事を参考にさせていただきましたが、その中で印象に残った文章を引用させていただきます。

antaさんのブログより、
「辞書順最小greedyの定石として、
「条件を満たすことが確定してる中で一番小さいもの、を先頭埋めていく」
「その時の条件の判断として、できるだけ条件を満たす可能性が大きいものを後ろに埋める」

は覚えておくべき」

感謝です。


ソースコード

class StrIIRec {
public:
  string recovstr(int n, int minInv, string minStr) {
    string ans = "";
    bool used[20];
    memset(used,false,sizeof(used));
    
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(used[j]) continue;
     
        string tmp = ans;
        tmp += (char)('a' + j);
        used[j] = true;
        for(int k = n - 1; k >= 0; k--){
          if(!used[k]) tmp += (char)('a' + k);
        }
        used[j] = false;
        
        if(minStr > tmp) continue;
        
        int count = 0;
        for(int k = 0; k < n; k++){
          for(int l = k + 1; l < n; l++){
            if(tmp[k] > tmp[l]) count++;
          }
        }
        
        if(minInv > count) continue;
        
        used[j] = true;
        ans += (char)('a' + j);
        break;
      }
    }
    return ans;
  }
};