Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-02-14

SRM461 Easy(300): ColoringRectangle

11:29 | SRM461 Easy(300): ColoringRectangle - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM461 Easy(300): ColoringRectangle - naoya_t@topcoder SRM461 Easy(300): ColoringRectangle - naoya_t@topcoder のブックマークコメント

提出コード晒し。

最初に書いたコード

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class ColoringRectangle {
  double hh, ww;
  double w(double r) { return sqrt(r*r - hh*hh); }
  vector<double> r,b,rw,bw,ro,bo;
  int rn, bn;

  int redfirst() {
    if (rn == 0) return -1;
    int cnt=0;
    double cur = 0;
    rep(i,rn) {
      cur += rw[i]*2; cnt++;
      if (cur >= ww) return cnt;

      if (bn<=i) return -1;

      cur += bw[i]*2; cnt++;
      if (cur >= ww) return cnt;

      if (rn<=i+1) return -1;
    }
    return -1;
  }
  int bluefirst() {
    if (bn == 0) return -1;
    int cnt=0;
    double cur = 0;
    rep(i,bn) {
      cur += bw[i]*2; cnt++;
      if (cur >= ww) return cnt;

      if (rn<=i) return -1;

      cur += rw[i]*2; cnt++;
      if (cur >= ww) return cnt;

      if (bn<=i+1) return -1;
    }
    return -1;
  }
 public:
  int chooseDisks(int width, int height, vector <int> red, vector <int> blue) {
    hh = 0.5 * height; ww = (double)width;
    r.clear(); b.clear(); rw.clear(); bw.clear(); ro.clear(); bo.clear();
    
    rn = sz(red), bn = sz(blue);
    sort(all(red)); reverse(all(red));
    sort(all(blue)); reverse(all(blue));

    rep(i,rn) {
      if (red[i]<height) continue;
      double y = (double)0.5*red[i];
      r.pb(y); rw.pb( w(y) ); ro.pb( y - w(y) );
    }
    rn = sz(r);
    rep(i,bn) {
      if (blue[i]<height) continue;
      double y = (double)0.5*blue[i];
      b.pb(y); bw.pb( w(y) ); bo.pb( y - w(y) );
    }
    bn = sz(b);

    int r1 = redfirst(), b1 = bluefirst();
    if (r1 < 0) return b1;
    if (b1 < 0) return r1;
    return min(b1,r1);
  }
};

1問は必ず取る、と思って入念にわけのわからん問題文を読み返す・・・1e-5がどうたらこうたらの箇所がよくわからない。

提出版(±1e-5の誤差条項の自分の解釈)

  • X枚 で height x width が行けるっていうなら同じセットで height x (width + 1e-5) でも行けるんでしょうね
  • その場合 height x (width - 1e-5) がX-1枚以下で行けるってのもなしね

と読んで、悩んだ挙句こんな感じのを最終的にsubmitした。コピペで冗長になってるのはご愛敬。

class ColoringRectangle {
  double hh, ww;
  double w(double r) { return sqrt(r*r - hh*hh); }
  vector<double> r,b,rw,bw,ro,bo;
  int rn, bn;

  int redfirst() {
    if (rn == 0) return -1;
    int cnt=0;
    double cur = 0;
    rep(i,rn) {
      cur += rw[i]*2; cnt++;
      if (cur >= ww) return cnt;

      if (bn<=i) return -1;

      cur += bw[i]*2; cnt++;
      if (cur >= ww) return cnt;

      if (rn<=i+1) return -1;
    }
    return -1;
  }
  int bluefirst() {
    if (bn == 0) return -1;
    int cnt=0;
    double cur = 0;
    rep(i,bn) {
      cur += bw[i]*2; cnt++;
      if (cur >= ww) return cnt;

      if (rn<=i) return -1;

      cur += rw[i]*2; cnt++;
      if (cur >= ww) return cnt;

      if (bn<=i+1) return -1;
    }
    return -1;
  }
 public:
  int chooseDisks(int width, int height, vector <int> red, vector <int> blue) {
    hh = 0.5 * height;

    // plus
    ww = (double)width + 1e-5;
    r.clear(); b.clear(); rw.clear(); bw.clear(); ro.clear(); bo.clear();
    
    rn = sz(red), bn = sz(blue);
    sort(all(red)); reverse(all(red));
    sort(all(blue)); reverse(all(blue));

    rep(i,rn) {
      if (red[i]<height) continue;
      double y = (double)0.5*red[i];
      r.pb(y); rw.pb( w(y) ); ro.pb( y - w(y) );
    }
    rn = sz(r);
    rep(i,bn) {
      if (blue[i]<height) continue;
      double y = (double)0.5*blue[i];
      b.pb(y); bw.pb( w(y) ); bo.pb( y - w(y) );
    }
    bn = sz(b);

    int r1 = redfirst(), b1 = bluefirst();
    int ans = -1;
    if (r1 < 0) ans = b1;
    else if (b1 < 0) ans = r1;
    else ans = min(b1,r1);
    if (ans < 0) return -1;
    
    // minus
    ww = (double)width - 1e-5;
    r.clear(); b.clear(); rw.clear(); bw.clear(); ro.clear(); bo.clear();
    
    rn = sz(red), bn = sz(blue);
    sort(all(red)); reverse(all(red));
    sort(all(blue)); reverse(all(blue));

    rep(i,rn) {
      if (red[i]<height) continue;
      double y = (double)0.5*red[i];
      r.pb(y); rw.pb( w(y) ); ro.pb( y - w(y) );
    }
    rn = sz(r);
    rep(i,bn) {
      if (blue[i]<height) continue;
      double y = (double)0.5*blue[i];
      b.pb(y); bw.pb( w(y) ); bo.pb( y - w(y) );
    }
    bn = sz(b);

    int r0 = redfirst(), b0 = bluefirst();
    int ans0 = -1;
    if (r0 < 0) ans0 = b0;
    else if (b0 < 0) ans0 = r0;
    else ans0 = min(b0,r0);

    if (ans0 < ans) return -1;
    return ans;
  }
};

上のコードとの違いは、例えばheight=6, width=8 なときにぴたっと収まる直径10のやつが来た場合の振舞い。(6 x 8.00001 の長方形は直径10の円には入りきらないので2とか3とか-1とかになるけど、6 x 7.99999の長方形は1枚で収まってしまう)

結果的にはシステムテストも通ったけど、どうも腑に落ちなかった。tomerunさんから頂いたコメントの通りなんだと思う。英語わけわかんない。

Member SRM 461

04:07 | Member SRM 461 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM 461 - naoya_t@topcoder Member SRM 461 - naoya_t@topcoder のブックマークコメント

02.13+.2010

エントリしてうたた寝してちゃんと3分前に起きて参加

DIVlevel問題名競技中後でSystem Test通過率備考
1 300 ColoringRectangle o - passed - 115.37
1 500 BuildingCities 開いただけ - - -
1 950 - 開いてない -

Easy (300 points): ColoringRectangle

  • 1e-5の誤差の意味が理解できないまま
    • width=8, height=6, red={10,10}, blue={6} みたいなのが来たらどうなる?
  • じっくり考えた(63'58'')けどわからない
  • じっくり考えすぎて次の問題に進めず

Medium (500 points): BuildingCities

  • 開いただけ

Hard (950 points):

  • 開いてない

Challenge Phase

  • 腑に落ちない
  • 問題文の意味が腑に落ちてなくてchallengeする気になれず

System Test

  • Passed
  • 腑に落ちない

結果

115.37points

部屋:12/20位

Div1:381/747位

1336→1371(+35) 微増

http://gyazo.com/32883bf049befeb19be31a977b3a841f.png

Practice Room

width=8, height=6, red={10,10}, blue={6} を試すと

Your challenge was invalid.

The system failed to process your request: If the answer for an input is X >= 1, then it must be possible to cover a rectangle with height = height and width = width + 1e-5 with X disks, given the same set of disks.

と言われる。これは何?

tomeruntomerun2010/02/14 04:49誤差落ちする人がいないように、
・被覆できる場合は常にすこし余裕を持って覆える
・被覆できない場合は超ギリギリのところで覆えなかったということはない
となるようテストケースを作ってるよ、ということだと理解してました。

n4_tn4_t2010/02/14 04:56あ、なるほど・・・これでものすごい時間悩んでロストしました>< どうもありがとうございます。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100214