Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-08-07

新しい環境でSRMに参戦する時の自分向けメモ

| 18:28 | 新しい環境でSRMに参戦する時の自分向けメモ - naoya_t@topcoder を含むブックマーク はてなブックマーク - 新しい環境でSRMに参戦する時の自分向けメモ - naoya_t@topcoder 新しい環境でSRMに参戦する時の自分向けメモ - naoya_t@topcoder のブックマークコメント

先日のSRM478でテンプレートが効かず、ヘッダもテストケースもなくて時間をロスした原因は、テンプレート設定をC++ではなくJavaの所に貼っていたからだと判明なう

テストの為にSRM 478のDiv II Easy問題を解いてみた。

  • 245.26ポイントだったので所要時間は 3'57''
  • やるだけ問題だけど、最後の1分ぐらいは使われていないコードが多いから30%ペナルティかけますよと言われて余分なマクロを削除してサブミットしなおすのに使っているのでもったいない
  • あと、キー入力が思考のアウトプットのボトルネックになるのはもったいない
#line 2 "KiwiJuiceEasy.cpp"
#include <string>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <algorithm>
// BEGIN CUT HERE
#include <iostream>
#include "cout.h"
// END CUT HERE
#include <sstream>
#include <cmath>
using namespace std;

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)

class KiwiJuiceEasy {
 public:
  vector <int> thePouring(vector <int> capacities, vector <int> bottles,
                          vector <int> fromId, vector <int> toId) {
    int n=sz(fromId);
    rep(i,n){
      int f=fromId[i],t=toId[i];
      int c=capacities[t];
      int a=bottles[f]+bottles[t];
      if(a>=c)
        bottles[t]=c, bottles[f]=a-c;
      else
        bottles[t]=a, bottles[f]=0;
    }
    return bottles;
  }
};

// BEGIN CUT HERE
#include <time.h>
clock_t start_time;
void timer_clear() { start_time = clock(); }
string timer() { clock_t end_time = clock(); double interval = (double)(end_time - start_time)/CLOCKS_PER_SEC; ostringstream os; os << " (" << interval*1000 << " msec)"; return os.str(); }

template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const vector <int> &Expected, const vector <int> &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } return 0;}

template<int N> struct Case_ {};
char Test_(...);
int Test_(Case_<0>) {
	timer_clear();
	int capacities_[] = {20, 20};
	  vector <int> capacities(capacities_, capacities_+sizeof(capacities_)/sizeof(*capacities_)); 
	int bottles_[] = {5, 8};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int fromId_[] = {0};
	  vector <int> fromId(fromId_, fromId_+sizeof(fromId_)/sizeof(*fromId_)); 
	int toId_[] = {1};
	  vector <int> toId(toId_, toId_+sizeof(toId_)/sizeof(*toId_)); 
	int RetVal_[] = {0, 13 };
	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_)); 
	return verify_case(RetVal, KiwiJuiceEasy().thePouring(capacities, bottles, fromId, toId)); }
int Test_(Case_<1>) {
	timer_clear();
	int capacities_[] = {10, 10};
	  vector <int> capacities(capacities_, capacities_+sizeof(capacities_)/sizeof(*capacities_)); 
	int bottles_[] = {5, 8};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int fromId_[] = {0};
	  vector <int> fromId(fromId_, fromId_+sizeof(fromId_)/sizeof(*fromId_)); 
	int toId_[] = {1};
	  vector <int> toId(toId_, toId_+sizeof(toId_)/sizeof(*toId_)); 
	int RetVal_[] = {3, 10 };
	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_)); 
	return verify_case(RetVal, KiwiJuiceEasy().thePouring(capacities, bottles, fromId, toId)); }
int Test_(Case_<2>) {
	timer_clear();
	int capacities_[] = {30, 20, 10};
	  vector <int> capacities(capacities_, capacities_+sizeof(capacities_)/sizeof(*capacities_)); 
	int bottles_[] = {10, 5, 5};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int fromId_[] = {0, 1, 2};
	  vector <int> fromId(fromId_, fromId_+sizeof(fromId_)/sizeof(*fromId_)); 
	int toId_[] = {1, 2, 0};
	  vector <int> toId(toId_, toId_+sizeof(toId_)/sizeof(*toId_)); 
	int RetVal_[] = {10, 10, 0 };
	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_)); 
	return verify_case(RetVal, KiwiJuiceEasy().thePouring(capacities, bottles, fromId, toId)); }
int Test_(Case_<3>) {
	timer_clear();
	int capacities_[] = {14, 35, 86, 58, 25, 62};
	  vector <int> capacities(capacities_, capacities_+sizeof(capacities_)/sizeof(*capacities_)); 
	int bottles_[] = {6, 34, 27, 38, 9, 60};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int fromId_[] = {1, 2, 4, 5, 3, 3, 1, 0};
	  vector <int> fromId(fromId_, fromId_+sizeof(fromId_)/sizeof(*fromId_)); 
	int toId_[] = {0, 1, 2, 4, 2, 5, 3, 1};
	  vector <int> toId(toId_, toId_+sizeof(toId_)/sizeof(*toId_)); 
	int RetVal_[] = {0, 14, 65, 35, 25, 35 };
	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_)); 
	return verify_case(RetVal, KiwiJuiceEasy().thePouring(capacities, bottles, fromId, toId)); }
int Test_(Case_<4>) {
	timer_clear();
	int capacities_[] = {700000, 800000, 900000, 1000000};
	  vector <int> capacities(capacities_, capacities_+sizeof(capacities_)/sizeof(*capacities_)); 
	int bottles_[] = {478478, 478478, 478478, 478478};
	  vector <int> bottles(bottles_, bottles_+sizeof(bottles_)/sizeof(*bottles_)); 
	int fromId_[] = {2, 3, 2, 0, 1};
	  vector <int> fromId(fromId_, fromId_+sizeof(fromId_)/sizeof(*fromId_)); 
	int toId_[] = {0, 1, 1, 3, 2};
	  vector <int> toId(toId_, toId_+sizeof(toId_)/sizeof(*toId_)); 
	int RetVal_[] = {0, 156956, 900000, 856956 };
	  vector <int> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_)); 
	return verify_case(RetVal, KiwiJuiceEasy().thePouring(capacities, bottles, fromId, toId)); }

template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<>      void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE


// BEGIN CUT HERE
/*
// PROBLEM STATEMENT
// Taro has prepared (...)c
*/
// END CUT HERE


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003\ customized by cafelier, timer support by naoya_t
// Powered by CodeProcessor
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100807