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さんから頂いたコメントの通りなんだと思う。英語わけわかんない。

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

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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100214