Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-02-11SRM460(DIV2)

SRM460 div2 第一問(250点)

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

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

「Yes」「No」で答えられる質問が複数あり、考えられる答えの組み合わせの数を求める問題。

質問には同じものが含まれることがあり、それらはひとつの質問として考える。

つまり、(組み合わせの数) = 2 ^ (質問の種類) を求める問題である。


楽勝。

import java.util.HashMap;

public class TheQuestionsAndAnswersDivTwo {
	public int find(String[] questions) {
		int questionsnum = 1, length = questions.length;
		HashMap<String, Integer> questionmap = new HashMap<String, Integer>();
		for (int i = 0 ; i < length ; i++) {
			if (!questionmap.containsKey(questions[i])) {
				questionmap.put(questions[i], 1);
				questionsnum *= 2;
			}
		}
		return questionsnum;
	}
}

Challengeの時に気づいたのですが、HashSetなるものがあったんですね。

さらに、addAllとArrays.asListで配列をコレクションに変換すれば

もっと短くできることが判明。

import java.util.HashSet;

public class TheQuestionsAndAnswersDivTwo {
	public int find(String[] questions) {
		HashSet<String> questionSet = new HashSet<String>();
		questionSet.addAll(java.util.Arrays.asList(questions));
		return (int) Math.pow(2, questionSet.size());
	}
}

SRM460 div2 第二問(500点)

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

JさんとBさんが複数の都市から一つを選んで訪問する。

都市で待ち受けている同じファンに出会う確率を求める問題。

これができなかったのが痛かった。簡単な問題だったのに。


一部のテストケースが通らなくてウンウンしてたのがこちら。

public class TheFansAndMeetingsDivTwo {
	public double find(int[] minJ, int[] maxJ, int[] minB, int[] maxB) {
		int citiesnum = minJ.length;
		int prob = 0, probmax = 0;
		for (int j = 0 ; j < citiesnum ; j++) {
			for (int b = 0 ; b < citiesnum ; b++) {
				if (minJ[j] <= minB[b] && minB[b] <= maxJ[j]) {
					prob += maxB[b] - Math.max(minJ[j], minB[b]) + 1;
				} else if (minB[b] <= minJ[j] && minJ[j] <= maxB[b]) {
					prob += maxJ[j] - Math.max(minB[b], minJ[j]) + 1;
				}
				probmax += (maxJ[j] - minJ[j] + 1) * (maxB[b] - minB[b] + 1);
			}
		}
		return (double) prob / probmax;
	}
}

確率、だから、おなじファンに会う場合の数を全体の場合の数で割ればよくね?

というのが当時考えた発想。

実はこれは間違い。なぜなら、ある条件に合致する場合の数を、全体で割って確率を求めるときは

ある条件に合致する場合が、それぞれ等しい確率で起こらなければならない、からです。

この問題の場合、例えば都市Aに1~5、都市Bに1~4のファンがいた場合、

JさんとBさんが都市Aでおなじファン1に出会う確率は 1 / 2 / 2 / 5 / 5 = 1 / 100 ですが、

Jさんが都市Aでファン1、Bさんが都市Bでファン1に出会う確率は 1 / 2 / 2 / 5 / 4 = 1 / 80 と異なります。


なので、確率を求める部分を改造して、probに個別の確率を足していくイメージで作ればよかったのではないかと。

その方針で作り直したのがこちら。

public class TheFansAndMeetingsDivTwo {
	public double find(int[] minJ, int[] maxJ, int[] minB, int[] maxB) {
		int citiesnum = minJ.length;
		double prob = 0;
		for (int j = 0 ; j < citiesnum ; j++) {
			for (int b = 0 ; b < citiesnum ; b++) {
				if (minJ[j] <= minB[b] && minB[b] <= maxJ[j]) {
					prob += (double) (Math.min(maxJ[j], maxB[b]) - minB[b] + 1)
					  / (citiesnum * citiesnum * (maxJ[j] - minJ[j] + 1) * (maxB[b] - minB[b] + 1));
				} else if (minB[b] <= minJ[j] && minJ[j] <= maxB[b]) {
					prob += (double) (Math.min(maxJ[j], maxB[b]) - minJ[j] + 1)
					  / (citiesnum * citiesnum * (maxJ[j] - minJ[j] + 1) * (maxB[b] - minB[b] + 1));
				}
			}
		}
		return prob;
	}
}

これで難なくテストに通った。

さらに重複部分を除いたのが以下。

public class TheFansAndMeetingsDivTwo {
	public double find(int[] minJ, int[] maxJ, int[] minB, int[] maxB) {
		int citiesnum = minJ.length;
		int c2 = citiesnum * citiesnum;
		double prob = 0;
		for (int j = 0 ; j < citiesnum ; j++) {
		    int jmeets = maxJ[j] - minJ[j] + 1;
			for (int b = 0 ; b < citiesnum ; b++) {
			    int bmeets = maxB[b] - minB[b] + 1;
				if (minJ[j] <= minB[b] && minB[b] <= maxJ[j]) {
					prob += (double) (Math.min(maxJ[j], maxB[b]) - minB[b] + 1)
					  / (c2 * jmeets * bmeets);
				} else if (minB[b] <= minJ[j] && minJ[j] <= maxB[b]) {
					prob += (double) (Math.min(maxJ[j], maxB[b]) - minJ[j] + 1)
					  / (c2 * jmeets * bmeets);
				}
			}
		}
		return prob;
	}
}

やれやれだぜ。