Hatena::Grouptopcoder

人生是睡眠 - 夢の中ではredcoder -

 | 

2010-01-16

SRM458 Div2

14:12

今日は間に合ったよパチョレック!

f:id:wolf125:20100116150326j:image

結果はホームランとはいきませんでしが・・(センター前ゴロぐらいかな)

250pt Desertification

  • 長方形のセルで森と砂漠が配置されている。
  • 1年後には砂漠の上下左右のセルも砂漠になる
  • T年後の砂漠セルの数はいくらか?

普通に1年ずつセルを塗っていって数えるだけ。なぜか時間がかかてしまった・・

500pt BouncingBalls

  • 一直線上に最大12個のボール(大きさは無視できる)が配置されている
  • ボールは右方向か左方向に速度1で動いている(どちら向きに動いているかはランダム)
  • ボールは完全弾性衝突する(ぶつかると反対方向に動く)
  • 衝突回数の期待値を求めよ

ボールが12個という話に惑わされて全探索してしまった。(4096通りしかなくねと思ったYO

速度は向かい合う時は2になるので、0.5秒ずつ時間をトレースしていけばすべての衝突タイミングを補足できるので完全シミュレーションした。最悪ケースでやっぱりTLEくらいました・・

ダメコードを貼っておこう。チャレンジタイムに人のコードをみて、「あ、完全弾性衝突だからすり抜けると同じじゃないか!」と気づいた時はすでに遅し。

import java.util.*;
public class BouncingBalls {
    public static final double ACCURACY = 0.000000001;
    public double expectedBounces(int[] x, int T) {
        double res = 0;
        int n = x.length;
        double[] pos = new double[n];
        boolean[] dir = new boolean[n];
        int cases = (int) Math.pow(2,n);
        long num = 0;
        for(int i = 0;i < cases;i++){
        	for(int j = 0;j < n;j++)
        		pos[j] = x[j];
        	String bin = Integer.toBinaryString(i);
        	while(bin.length() < n)
        		bin = "0" + bin;
        	for(int j = 0; j < n;j++){
        		if(bin.charAt(j) == '0')
        			dir[j] = false;
        		else
        			dir[j] = true;
        	}
        	//System.out.println(Arrays.toString(dir));
        	for(double t = 0; t < T; t += 0.5){
        		//System.out.println(Arrays.toString(pos));
        		for(int j = 0; j < n;j++){
        			if(dir[j])
        				pos[j] += 0.5;
        			else
        				pos[j] -= 0.5;
        		}
        		for(int p = 0; p < n;p++){
        			for(int q = p +1; q < n; q++){
        				if(pos[p] == pos[q]){
        					num++;
        					dir[p] = !dir[p];
        					dir[q] = !dir[q];
        				}
        			}
        		}
        	}
        		
        }
        //System.out.println(num);
        return num / (double)cases;
    }
}

950pt ProductTriplet

  • x , y , z のそれぞれに最小値と最大値が与えられているとき、x * y = z となる組の数を求める

この問題を読んだ時はすでに残り5分だったので、どうしようもなかった・・

すべて数えるアホコードを書いたら当然TLE

(最終結果)

レーティングは964のまま動かずでした・・

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/wolf125/20100116
 |