Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-11-23SRM488(DIV1)

SRM488 第一問(250pt) TheBoredomDivOne

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

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

  • 期待値をメモ化すればおk。
  • 時間はかかったが解けた。120点ぐらい

public class TheBoredomDivOne {
	public double[][] ex;

	public double calc(int n, int m) {
		if (m <= 0) {
			return 0;
		}
		if (ex[n][m] > 0) {
			return ex[n][m];
		}
		double all = (n + m) * (n + m - 1) / 2;
		double zero = n * (n - 1) / 2 / all;
		double two = m * (m - 1) / 2 / all;
		double one = 1 - (zero + two);

		double ans = (zero + one * (1 + calc(n+1, m-1)) + two * (1 + calc(n+2, m-2))) / (one + two);
		ex[n][m] = ans;
		return ans;
	}

	public double find(int n, int m) {
		ex = new double[100][100];
		ex[1][1] = 1.0;
		ex[2][1] = 1.5;
		ex[1][2] = 2.0;
		return calc(n, m);
	}
}

SRM488 第二問(500pt) TheBoringStoreDivOne

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

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

  • J、Bそれぞれ、2回以上出現する部分文字列をメモ。
  • その部分文字列をいくつか右(Bの場合は左)に伸ばしたパターンを全列挙。
    • substringやindexOf周りでバグったりした。
  • 全パターンゴリ押し。O(N^4)
  • 数時間かかって、他人のコードも参考にしながらやっと解けた。
    • systestで1.8sかかったケースもありかなりギリギリだった。(2秒以上だとタイムアップ)
    • div1の第2問を時間内に解くのは今の実力では難しい。方針はつかめるようになってきたけどね。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

public class TheBoringStoreDivOne {
	public HashMap<String, HashSet<String>> jpattern = new HashMap<String, HashSet<String>>();
	public HashMap<String, HashSet<String>> bpattern = new HashMap<String, HashSet<String>>();

	public boolean isGreater(String a, String b) {
		if (a.length() > b.length() || (a.length() == b.length() && a.compareTo(b) < 0)) {
			return true;
		}
		return false;
	}

	public void addAllJ(HashMap<String, HashSet<String>> w, String pattern, String sub, int idx) {
		HashSet<String> list = null;
		if (!w.containsKey(pattern)) {
			list = new HashSet<String>();
		} else {
			list = w.get(pattern);
		}
		list.add("");

		String a = "";
		int from = idx + pattern.length();
		int to = sub.length();
		for (int i = from ; i < to ; i++) {
			a += sub.substring(i, i + 1);
			list.add(a);
		}
		w.put(pattern, list);
	}

	public void addAllB(HashMap<String, HashSet<String>> w, String pattern, String sub, int idx) {
		HashSet<String> list = null;
		if (!w.containsKey(pattern)) {
			list = new HashSet<String>();
		} else {
			list = w.get(pattern);
		}
		list.add("");

		String a = "";
		int from = idx - 1;
		int to = 0;
		for (int i = from ; i >= to ; i--) {
			a = sub.substring(i, i + 1) + a;
			list.add(a);
		}
		w.put(pattern, list);
	}

	public void jyunbi(String J, String B) {
		int j = J.length();
		int b = B.length();
		for (int x = 0 ; x < j ; x++) {
			for (int y = x + 1 ; y <= j ; y++) {
				String pattern = J.substring(x, y);
				String prefix = J.substring(0, x);
				String suffix = J.substring(y, j);


				int pre = prefix.indexOf(pattern);
				if (pre != -1) {
					do {
						addAllJ(jpattern, pattern, prefix, pre);
						pre = prefix.indexOf(pattern, pre+1);
					} while(pre != -1);
				}

				int suf = suffix.indexOf(pattern);
				if (suf != -1) {
					do {
						addAllJ(jpattern, pattern, suffix, suf);
						suf = suffix.indexOf(pattern, suf+1);
					} while(suf != -1);
				}
			}
		}

		for (int x = 0 ; x < b ; x++) {
			for (int y = x + 1 ; y <= b ; y++) {
				String pattern = B.substring(x, y);
				String prefix = B.substring(0, x);
				String suffix = B.substring(y, b);

				int pre = prefix.lastIndexOf(pattern);
				if (pre != -1) {
					do {
						addAllB(bpattern, pattern, prefix, pre);
						pre = prefix.lastIndexOf(pattern, pre-1);
					} while(pre != -1);
				}

				int suf = suffix.lastIndexOf(pattern);
				if (suf != -1) {
					do {
						addAllB(bpattern, pattern, suffix, suf);
						suf = suffix.lastIndexOf(pattern, suf-1);
					} while(suf != -1);
				}
			}
		}
	}

	public String find(String J, String B) {
		jyunbi(J, B);
		String answer = "";

		for (Entry<String, HashSet<String>> jp : jpattern.entrySet()) {
			for (String amarinJ : jp.getValue()) {
				for (Entry<String, HashSet<String>> bp : bpattern.entrySet()) {
					for (String amarinB : bp.getValue()) {
						if (amarinJ.equals(amarinB)) {
							String result = jp.getKey() + amarinJ + bp.getKey();
							if (isGreater(result, answer)) {
								answer = result;
							}
						}
					}
				}
			}
		}

		return answer;
	}
}