Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-06-24

SRM443

12:24 | SRM443 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM443 - naoya_t@topcoder SRM443 - naoya_t@topcoder のブックマークコメント

外付けHHKBのUS配列にも少しは慣れてきた。が

06.23+.2009

DIVlevel問題名競技中後でSystem Test通過率備考
1 300 CirclesCountry o - - 277.47
1 600 BinaryFlips 間に合わず - - -
1 1000 - -

300点問題: CirclesCountry

  • 簡単な問題だと思うが
  • 不使用コード30%ルールにひっかかるので再編集とか
using namespace std;
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

class CirclesCountry {
  bool insidep(int cx,int cy,int cr, int x,int y) {
    int r2 = (x-cx)*(x-cx) + (y-cy)*(y-cy);
    return (r2 - cr*cr) < 0 ? true : false;
  }
 public:
  int leastBorders(vector<int> X, vector<int> Y, vector<int> R, int x1, int y1, int x2, int y2) {
    int n=sz(R),cnt=0;
    rep(i,n) if (insidep(X[i],Y[i],R[i],x1,y1) != insidep(X[i],Y[i],R[i],x2,y2)) cnt++;
    return cnt;
  }
};
  • hypot()を使ってないのは、整数で、かつ二乗がintに収まる範囲なため、二乗で比較したほうが精度を落とさずに比較できるかなと思ったから。(別にそこまでシビアでなくてもよかったか?)
  • 277.47points = 8'13''...もっと速く打てるだろ自分><

600点問題: BinaryFlips

  • 普通に書いたら100000,100000,65537程度でも7秒TLE
  • あと10分ちょいのところでTLEしない探索を思いつき
  • 実装するもfailed caseがある
  • 残り1分30秒あたりで最後の鍵がひらめいたが
  • 9分オーバーでようやくTLEしないのが書けた
  • practice roomに投げたらテストケース#15 (A=1,B=9128,K=5)で落ちる!><

1000点問題:

  • 開いてない!

Challenge Time

  • 落とせない
  • 単に度胸がない!

277.47点で室内7位。Div1全体では139/557位

1332→1459 (+127) ...もう一声。

http://gyazo.com/90e9fa95f3993b080961cf4e8cea9fe4.png

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