Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-02-19

カスタム版TZTesterの1E-9誤差許容対応をvector<double>にも適用する

22:24 | カスタム版TZTesterの1E-9誤差許容対応をvectorにも適用する - naoya_t@topcoder を含むブックマーク はてなブックマーク - カスタム版TZTesterの1E-9誤差許容対応をvectorにも適用する - naoya_t@topcoder カスタム版TZTesterの1E-9誤差許容対応をvectorにも適用する - naoya_t@topcoder のブックマークコメント

以前、結果がdoubleの場合に±1E-9の誤差を認めるようにTZTesterをカスタマイズしたが、SRM462 Div1Mediumのようにvector<double>の場合には未対応だったので再改造。

以下、前回(cafelier版+naoya_tパッチ)からの差分。

--- tangentz.old/TZTester.java	2010-02-19 21:02:27.000000000 +0900
+++ TZTesters/tangentz/TZTester.java	2010-02-19 22:13:30.000000000 +0900
@@ -32,7 +32,7 @@
     private static final String k_PROBLEM       = "$PROBLEM$";
     private static final String k_RUNTEST       = "$RUNTEST$";
     private static final String k_TESTCODE      = "$TESTCODE$";
-    private static final String k_VERSION       = "\n// Powered by TZTester 1.01 [25-Feb-2003] customized by cafelier, timer support by naoya_t";
+    private static final String k_VERSION       = "\n// Powered by TZTester 1.01 [25-Feb-2003] customized by cafelier, timer and 1e-9 tolerance support by naoya_t";
     
     // Cut tags
     private static final String k_BEGINCUT      = "// BEGIN CUT HERE\n";
@@ -237,6 +237,12 @@
 		if (TypeString.equals("double")) {
 			Code.append("double diff = Expected - Received; if (diff < 0) diff = -diff; ");
 			Code.append("if (diff < 1e-9) cerr << \"PASSED\" << timer() << endl; ");
+        } else if (TypeString.equals("vector <double>")) { // vector<double> support added on Feb 19, 2010 by naoya_t
+          Code.append("bool passed = Received.size()==Expected.size(); ");
+          Code.append("if (passed) for (int i=0,c=Received.size(); i<c; i++) { ");
+          Code.append("double diff = Expected[i] - Received[i]; if (diff < 0) diff = -diff; ");
+          Code.append("if (diff >= 1e-9) { passed = false; break; }} ");
+          Code.append("if (passed) cerr << \"PASSED\" << timer() << endl; ");
 		} else {
 			Code.append("if (Expected == Received) cerr << \"PASSED\" << timer() << endl; ");
 		}

EmKEmK2010/02/25 23:27こんにちは。

その実装では、空のvector<double>に対して常にPASSEDと判定する気がします。

n4_tn4_t2010/02/25 23:38そうですね。vectorのサイズが等しいかチェックしてませんし…もう少しまじめにチェックするよう加筆しました。こんなところで撃墜されるとは。

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

2010-02-18

SRM462

13:34 | SRM462 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM462 - naoya_t@topcoder SRM462 - naoya_t@topcoder のブックマークコメント

wataさんと同じ部屋

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 AgeEncoding o(再提出) - passed - 85.34
1 450 CandyBox o - passed - 235.35
1 1000 WarTransportation 未提出 -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100218

2010-02-17

TLE

17:30 | TLE - naoya_t@topcoder を含むブックマーク はてなブックマーク - TLE - naoya_t@topcoder TLE - naoya_t@topcoder のブックマークコメント

http://felicity.iiit.ac.in/tle/

全問解いて19位はちょっと恥ずかしいので来年に向けて色々頑張りたい

続きを読む

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

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 のブックマークコメント

提出コード晒し。

続きを読む

Member SRM 461

04:07 | Member SRM 461 - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM 461 - naoya_t@topcoder Member SRM 461 - naoya_t@topcoder のブックマークコメント

02.13+.2010

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

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 300 ColoringRectangle o - passed - 115.37
1 500 BuildingCities 開いただけ - - -
1 950 - 開いてない -

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

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

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

2010-02-08

過去問マラソン(#13):SRM154

| 23:23 | 過去問マラソン(#13):SRM154 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#13):SRM154 - naoya_t@topcoder 過去問マラソン(#13):SRM154 - naoya_t@topcoder のブックマークコメント

Easy(350): CheatCode

  • 配点350点て何
  • 文字と必要打鍵数のペア、の配列をchainと仮に呼び
  • 後だけでなく前に余計な文字を打つのもアリだとsample caseで気づき
  • 途中に関係ない文字が入る場合はNG、ということにsample caseで気づき
  • ていうか問題ちゃんと読んだほうが結果的に早いのでは?
  • 149.37pt (50'25'') 時間かかりすぎ
  • passed system test
  • 続きを読む

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

2010-02-07

SRM460 Easy: TheQuestionsAndAnswersDivOne

| 17:10 | SRM460 Easy: TheQuestionsAndAnswersDivOne - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM460 Easy: TheQuestionsAndAnswersDivOne - naoya_t@topcoder SRM460 Easy: TheQuestionsAndAnswersDivOne - naoya_t@topcoder のブックマークコメント

全パターン試すのそんなに難しくないし…

まあ目が覚めてて落ち着いてれば解ける問題でした。

続きを読む

SRM460

04:06 | SRM460 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM460 - naoya_t@topcoder SRM460 - naoya_t@topcoder のブックマークコメント

02.06+.2010

エントリしてうたた寝して起きたら2:11amとか

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 TheQuestionsAndAnswersDivOne submitted - x - failed system test
1 500 TheFansAndMeetingsDivOne 間に合わず - - -
1 1000 - 開いてない -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100207

2010-02-05

過去問マラソン(#12):SRM153(続き)

| 14:22 | 過去問マラソン(#12):SRM153(続き) - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#12):SRM153(続き) - naoya_t@topcoder 過去問マラソン(#12):SRM153(続き) - naoya_t@topcoder のブックマークコメント

ちょっとブランクが空いたが気を取り直して。オフィスの環境テストを兼ねて過去問にトライ。

無刻印のHHKB Professional 2で初めて書くC++。打ちやすい。矢印キーが無い事が不慣れなので指慣らしに時々過去問でも解くか。

Medium(450): Collision

  • 今日も問題が頭に入ってこない...
  • 要は実装するだけ?
  • 211.83 (41'45'') インストール作業の裏でやっているとはいえ時間かけすぎ
  • passed system test
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class Collision {
  vector<int> az; int iz, azn, tz;

  double memory(int i,int used,double nocol){ // have memory.
    if(i==azn) return nocol;
    int a = az[i];
    if (used+a > iz) return 0;
    long double r = 1.0;
    for(int j=0,l=iz,re=iz-used; j<a; j++,l--,re--){
      r = r * re / l;
    }
    return memory(i+1,used+a,nocol*r);
  }
  double no_memory(){
    long double r = 1.0;
    for(int i=0,l=iz;i<tz;i++,l--) {
      r = r * l / iz;
    }
    return (double)r;
  }

 public:
  double probability(vector<int> assignments, int ids) {
    az.assign(all(assignments)); azn=sz(az); iz = ids;

    int total = 0; tr(az,it) total += *it; if (total > iz) return 0.0;
    tz = total;

    double r1 = memory(0,0,1), r2 = no_memory();
    return abs(r1 - r2);
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100205