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

SRM 577 Div2 Medium EllysRoomAssignmentsDiv2

問題

SRM 577 - TopCoder Wiki

TopCoderのコンテストのように参加者を部屋に割り当てる.割り当て方は一部屋20名の部屋にスコアの高いものから排他的にそれらの部屋にランダムに割り振る.今入力の先頭がEllyのスコアだった時に,Ellyが一番ハイスコアの人と同室となる確率を答える問題.

解答

  • ハイスコアの人を固定すると,Ellyがその人と同じ部屋になる確率は部屋の数をRとした時1/R
  • ただし,排他的に割り振るのでEllyがトップ20名に入った時は確率は0
  • ただし,Ellyがハイスコアになったときは確率は1

最後の条件を見落としていたorz SuccessRateを見ると,同じように解いたけれども条件をミスした人が多数のようだ.

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}

class EllysRoomAssignmentsDiv2
{
public:
  double getProbability(vector <string> ratings)
    {
      vector<int> rates;
      int n = ratings.size();
      vector<bool> rs(1200, false);
      string rstr = "";
      int i;
      for(i = 0; i < n; i++)rstr += ratings[i];
      size_t prev = 0;
      size_t pos = 0;
      while (pos != string::npos){
        pos = rstr.find(" ", prev);
        int v = -1;
        if (pos == string::npos){
          v = toInt(rstr.substr(prev));
        }else{
          v = toInt(rstr.substr(prev, pos-prev));
          prev = pos+1;
        }
        rates.push_back(v);
        // if (0 < v && v < 1200){
        //   rs[rates.back()] = true;
        //   cout << "[" << rates.back() << "], ";
        // }
      }
      n = rates.size();
      int elly = rates[0];
      sort(rates.rbegin(), rates.rend());
      int ellyidx;
      for(ellyidx = 0; ellyidx < rates.size(); ellyidx++)
        if (rates[ellyidx] == elly) break;
      int r = n/20 + ((n % 20) > 0);
      cout << "n=" << n << " r=" << r
           << " ellyidx=" << ellyidx << endl;
      if (n <= 20) return 1;
      if (ellyidx == 0) return 1;
      if (ellyidx < r) return 0;
      return 1.0/r;
      // if (r == 0 || (n-ellyidx) < n/20) return 0;
      // return 1.0/r;
    }
};