読者です 読者をやめる 読者になる 読者になる

SRM 636 Div2 Medium SortishDiv2

問題

SRM 636 - TopCoder Wiki

シーケンスSが与えられた時S[i] < S[j] (i < j)となる数をsortednessと呼ぶ. ある,sortednessといくつかの数字が抜けたシーケンスSが与えられる. 本来,Sは1から|S|の要素からなる.今S[i]=0を任意の数字に置き換えれる時, sortednessを満たすシーケンスの種類数を答える問題.

解答

  • 問題制限と,例がミスリーディングを誘うようで余り好みではない.
  • 重要なポイントはシーケンスの要素数は100とそれなりに大きいが,S[i]=0となる個数はたった5個しか無い.
  • つまり,置き換える種類数は5!通りのみ.
  • あとは5!を実際に当てはめ,sortednessを計算し種類数を求めれば良い.
class SortishDiv2
{
public:
  int ways(int sortedness, vector <int> seq)
    {
      int n = seq.size();
      int i, j;
      // int num_zero = count_if(seq.begin(), seq.end(), [](int x){return x == 0;});
      vector<int> wild;
      for (i = 1; i <= n; i++){
        bool found = false;
        for (auto x : seq) {
          if (x == i) found = true;
        }
        if (!found) wild.push_back(i);
        // if (!found) cout << i << endl;
      }
      sort(wild.begin(), wild.end());
      int res = 0;
      do{
        int cur = 0;
        vector<int> new_seq = seq;
        for (auto & x:new_seq) if (x == 0) x = wild[cur++];
        // for (auto & x:new_seq) cout << x << ", ";
        // cout <<endl;
        int count = 0;
        for (i = 0; i < n; i++) {
          for (j = i + 1; j < n; j++) {
            if (new_seq[i] < new_seq[j]) count++;
          }
        }
        if (sortedness == count) res++;
      }while(next_permutation(wild.begin(), wild.end()));
      return res;
    }
};