naoya_t@topcoder

SRM461 Easy(300): ColoringRectangle

11:29 |

提出コード晒し。

最初に書いたコード

#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);
  }
};

１問は必ず取る、と思って入念にわけのわからん問題文を読み返す・・・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の長方形は１枚で収まってしまう）

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