Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-02-13[過去問]Member SRM458(DIV2)

SRM458 div2 第二問(500点)

| SRM458 div2 第二問(500点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM458 div2 第二問(500点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10726

直線上に並んだボールの衝突回数の期待値を求める問題。

統計によるとこちらの方が正解率が高いのが不思議!


public class BouncingBalls {

	public double expectedBounces(int[] x, int T) {
		double exp = 0;
		int ballsNum = x.length;

		for (int i = 0 ; i < ballsNum ; i++) {
			for (int j = i + 1 ; j < ballsNum ; j++) {
				int distance = x[j] - x[i];
				if (distance <= 2 * T) {
					exp += 0.25;
				}
			}
		}
		return exp;
	}
}

はじめはボールがぶつかるケースが出たらかかった時間を引いて

再帰でゴニョゴニョしようかな、と考えましたが。

絵を描いてたらボール1つ1つとの衝突が何回おこえりえるかを

数えればいいだけのことに気づきました。(等速度なため)