naoya_t@topcoder

SRM440

22:39 |

05.12.2009

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	IncredibleMachine	135.81	-	passed
1	500	MazeWandering	間に合わず	-	-		-
1	1000		-				-

250点問題: IncredibleMachine

• エネルギー保存の法則
  • 
  • 
  • 
  • 
  • 
• 速度と加速度の関係
  • 
  • 
• 問題文から
  • 
  • 
• 135.81points (32'30'')
• 時間かかりすぎ！

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

class IncredibleMachine {
 public:
  double gravitationalAcceleration(vector <int> x, vector <int> y, int T) {
    int N=sz(x)-1;
	vector<double> dx(N),dy(N),a(N),s(N),l(N),v(N+1),dt(N);
    v[0]=0.0;
    double t=0;
    //geo
    rep(i,N) {
      dx[i] = (double)x[i+1]-x[i];
      dy[i] = -(double)(y[i+1]-y[i]);
      //l[i] = (dx[i]*dx[i] + dy[i]*dy[i]); l[i] *= l[i];
      a[i]=atan2(dy[i],dx[i]);
      s[i]=sin(a[i]);

      v[i+1]=sqrt(v[i]*v[i] + (y[i]-y[i+1])*2); // *√g
      dt[i] = (v[i+1]-v[i])/s[i]; // /g
      t += dt[i];
    }
    // t/T=√g
    return (t/T)*(t/T);
  }
};

• バイナリサーチで解く方法もある（というかみんなバイナリサーチ？）
• 終了条件にεを使うと無限ループに陥ってTLEな場合があるので注意
  • ちゃんとそういうのを落としてくるSystem Testケースが仕込まれているようで
  • 一方chokudaiさんは大きめの定数回ループを使った
• 後で自分でもバイナリサーチ版を書いてみるなどしたい

500点問題: IncredibleMachine

• 2500x2500の行列演算とか考えたけどメモリ足りないかなと
• 単純にシミュレーション
• デバッグ間にあわず時間切れ
• テストケースは通るのが出来た
• 50x50で帰ってこない＞＜

1000点問題:

• 開いてない！

Challenge Time

• 防衛

135.81点で室内8位。Div1全体では279/701位

1450→1500

また黄色くなった！