naoya_t@topcoder

SRM443

12:24 |

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

06.23+.2009

DIV	level	問題名	競技中	後で	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) ...もう一声。