Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-12

SRM440

22:39 | SRM440 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM440 - naoya_t@topcoder SRM440 - naoya_t@topcoder のブックマークコメント

05.12.2009

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

250点問題: IncredibleMachine

  • エネルギー保存の法則
    • \frac12mv_{i+1}^2+mgh_{i+1}=\frac12mv_i^2+mgh_i
    • \frac12m(v_{i+1}^2-v_i^2)=mg(h_i-h_{i+1})
    • v_{i+1}^2-v_i^2=2g(h_i-h_{i+1})
    • v_{i+1}^2=v_i^2+2g(h_i-h_{i+1})
    • v_{i+1}=\sqrt{v_i^2+2g(h_i-h_{i+1})}
  • 速度と加速度の関係
    • v_{i+1}=v_i+g sin\theta_it_i
    • t_i=\frac{v_{i+1}-v_i}{g sin\theta_i}
  • 問題文から
    • v_0=0
    • \sum_{i=1}^N{t_i}=T
  • 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

http://gyazo.com/55cf6bb6568d43850eb6802a04572314.png

また黄色くなった!

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