Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-16

SRM384 div2 (過去問)

22:32

Easy - Prank

整数 apparentGain が与えられるので, a^2 - b^2 = apparentGain となるような整数aを求める.

アルゴリズムは1から順に二乗を計算し, apparentGainを足し, そのルートを取り, その結果が整数ならば (小数点以下がなければ) 解に追加するというもので, これはすぐに思いついたのですが, 探索範囲を1からどこまでにすべきなのかに悩みました. とりあえず勘で[1, 100000]にしたらシステムテストまで通ったんですが, 確証がないままです.

探索範囲の上限についてはeditorialをみて納得できました. ある整数xとそれより小さい整数x-kとの間で上記の計算をすると仮定します. x^2 - (x-k)^2 が一番小さくなるのはk=1のときです. よって x^2 - (x-1)^2 が100000を超えた時のxの値を上限とすれば良いことになります. x^2 - (x-1)^2 = 2*x - 1 となるので 2*x - 1 <= 100000, x <= 50000. よって上限は50000となります.

class Prank {
   public:
   vector <int> realWeight(int apparentGain) {
      vector <int> ret;

      for (int i=1; i<=100000; i++) {
        long long ll = (long long)i * i;
        ll += apparentGain;
        double sqrt_ll = sqrt(ll);
        if (sqrt_ll == (int)sqrt_ll)
          ret.push_back((int)sqrt_ll);
      }

      return ret;
  }
};

Medium - Library

図書館にはいくつかの部屋があり, それぞれの部屋に書類がある. 部屋ごと, 書類ごとにアクセス権限が設定されている. 各ドキュメントにアクセスできる権限の情報と, ある人物の権限が与えられるので, この人物がどの書類にアクセスできるかを求める.

これはただやるだけの問題でした. 250より簡単でした.

class Library {
public:
  vector <string> split(const string _s, const string del) {
    vector <string> ret;
    string s = _s;

    while (!s.empty())
      {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
          pos += del.size();
        s.erase(0, pos);
      }

    return ret;
  }

  int documentAccess(vector <string> records, vector <string> userGroups, vector <string> roomRights) {
    int ret = 0;
    set <string> docs;

    for (int i=0; i<records.size(); i++) {
      vector <string> tmp = split(records[i], " ");
      if (find(userGroups.begin(), userGroups.end(), tmp[2]) != userGroups.end() &&
          find(roomRights.begin(), roomRights.end(), tmp[1]) != roomRights.end())
        docs.insert(tmp[0]);
    }

    ret = docs.size();

    return ret;
  }
};