最近SRMの記事しか書いていない。
勉強してないってことか。

Easy TheQuestionsAndAnswersDivTwo

YesNo問題の解答は何通りありますか？って問題。
ただ、重複するYesNo問題があって、その時解答は同じでなければならない。

HashSet使って、2^hash.size()するだけ。
こういう時Javaは便利だよね。

222.15

Midium TheFansAndMeetingsDivTwo

ここらへんで気づく、今日はボリビアがテーマだということを(笑

２人の人気者がいて、ファンがいる都市を訪問する。
ただ、多忙だから各々１都市ずつしか行けない。
各都市にはファンがいて、会えるファンの人数の最小と最大が決まっている。
同じ人数になるときの確率は？って問題。

別々にファンに会える人数の確率を求める。
ファンの人数は1~50だから全部計算して大丈夫。
で、それを突き合わせて、掛けて足すだけ。

public class TheFansAndMeetingsDivTwo {
    public double find(int[] minJ, int[] maxJ, int[] minB, int[] maxB) {
    	final int cities = minB.length;
    	double[] probabilityJ = new double[51];
    	double[] probabilityB = new double[51];
    	double result = 0.0;

    	/* John */
    	for (int i = 0; i < cities; i++) {
    		int w = maxJ[i] - minJ[i] + 1;
    		double p = (1.0 / (double)cities) * (1.0 / (double)w);
			for (int j = minJ[i]; j <= maxJ[i]; j++) {
				probabilityJ[j] += p;
			}
		}

    	/* Brus */
    	for (int i = 0; i < cities; i++) {
    		int w = maxB[i] - minB[i] + 1;
    		double p = (1.0 / (double)cities) * (1.0 / (double)w);
			for (int j = minB[i]; j <= maxB[i]; j++) {
				probabilityB[j] += p;
			}
		}

    	for (int i = 0; i <= 50; i++) {
			if (probabilityB[i] > 0 && probabilityJ[i] > 0) {
				result += probabilityB[i] * probabilityJ[i];
			}
		}

    	return result;
    }
}

334.21

Hard TheCitiesAndRoadsDivTwo

古い地図に道路足す問題。
書いてそれなりに自信があったから送ったんだけど、落とされてしまった。
なんでだろう？

public class TheCitiesAndRoadsDivTwo {
	boolean[][] path;
	int N;
	int[] group;

    public int find(String[] map) {
    	N = map.length;
    	path = new boolean[N][N];
    	group = new int[N];
    	int groupIndex = 0;

    	/* make path*/
    	for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				char c = map[i].charAt(j);
				if (c == 'Y') {
					path[i][j] = true;
					path[j][i] = true;
				}
			}
		}

    	/* make group */
    	for (int i = 0; i < group.length; i++) {
    		if (group[i] == 0) {
    			group[i] = ++groupIndex;
    			go(i, groupIndex);
    		}
		}

//    	System.out.println(Arrays.toString(group));

    	/* count path */
    	int count = 0;
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++) {
				if (group[i] != group[j] && !path[i][j]) {
					count++;
					path[i][j] = true;
					path[j][i] = true;
				}
			}
		}

    	return (count > 0) ? count : 1;
    }

    void go(int from, int groupIndex){
    	for (int i = 0; i < N; i++) {
			if (path[from][i] && group[i] == 0) {
				group[i] = groupIndex;
				go(i, groupIndex);
			}
		}
    }
}

0.0

Challenge Phase

速攻Hardが落とされて凹む。
ちょろちょろ見るが集中力が限界。風呂に入る。

Result

Hardが通れば初の1000点代だったので、かなり悔しい。

Total 556.36
Rating 990(+49)

それもレートがあまり上がらずショックorz
後でHardは復習しよー

じゃ、おやすみなさい。
JPの皆様、深夜なのにお疲れ様でした。