Hatena::Grouptopcoder

tochukasoの日記

 | 

2014-06-29

SRM626

| 22:52

・Easy

 数値型の配列が与えられる。

 配列のサブ配列の総和を求める。

 例.[1,2,3]の場合、1, 2, 3, 1 + 2, 2 + 3, 1 + 2 + 3の合計 = 20となる

 選択する文字の長さ、開始位置、N文字分で3重ループして計算する

	public int findSum(int[] array)
	{
	    int sum = 0;
	    int N = array.length;
	    for (int i = 1; i <= N; i++) {
	        for (int j = 0; j + i<= N; j++) {
	            for(int k = 0; k < i; k++) {
	                sum += array[j+k];
	            }
	        }
	    }
	    return sum;
	}

 データの制約が緩い(配列の要素数は50)にも関わらず、

 時間がかかると思って効率的な解法を探して小一時間使った。

 結局3重ループの解法でいいと気付いた。

 なんという時間の無駄。

Medium

 2人が互いにサイコロを振りあう。

 サイコロはN面体。

 Aが勝つことは決まっている。

 Aの目の期待値を答える。

 Bの目を上から順番に見ていって、AがBの目を越える事がある場合に、

 総和と回数を足していく。(Bの目に対してAが勝つ場合にカウントする)

 最後に総和/回数を行う

	public double getExpectation(int a, int b)
	{
		double res = 0;
		
	    int sumCount = 0;
	    int sum = 0;
	    for (int i = b; i > 0; i --) {
	        if (a > i) {
	            int tmp = a - i;
	            sumCount += tmp;
	            for (int j = 0; j < tmp; j++) {
	                sum += a - j;
	            }
	        }
	    }
		
		
		return (double) sum /  sumCount;
	}

C問題。

時間なくて解けなかった。

時間あっても、解けないかな。

課題として、easy問題とmedium問題を確実に素早く解く力が必要

毎日必ず、Div2のeasyとmediumを解こう。

1072 ⇒ 1016

 |