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

Member SRM 461

04:07 |

02.13+.2010

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

DIV	level	問題名	競技中	後で	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) 微増

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.

と言われる。これは何？