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

SRM 625 Div2 Medium IncrementingSequence

問題

SRM 625 - TopCoder Wiki

N個の要素からなるシーケンスが与えられた時,シーケンスを修正して1..Nのシーケンスを作りたい. 可能な修正は与えられたkを任意の要素に任意の回数を足す. 1..Nのシーケンスを作れるかどうか判定する問題

解答

足すだけなので,1..Nのシーケンスが出来るまでkを足し続け,全ての要素がNを超えたら終了する.

いろいろケアレスミスした・・・

class IncrementingSequence
{
public:
  string canItBeDone(int k, vector <int> A)
    {
      int n = A.size() + 1;
      sort(A.begin(), A.end());
      vector<bool> used(n, false);
      vector<int> rest = A;
      while (A.size() > 0 && *min_element(A.begin(), A.end())<=n) {
        rest.clear();
        for (int i = 0; i < A.size(); i++) {
          if (A[i] <= n && used[A[i]] == false) {
            // cout << "used " << A[i] << endl;
            used[A[i]] = true;
          }else {
            rest.push_back(A[i] + k);
          }
        }
        A = rest;
      }
      // for (int i = 0; i < A.size(); i++) cout << "rest " << A[i] << endl;
      if (*min_element(used.begin()+1, used.end()) > 0) return "POSSIBLE";
      return "IMPOSSIBLE";
    }
};