Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-03-20[過去問]SRM464(DIV2)

本番で解けなかった問題をじっくり考えてやってみた。

SRM464 div2 第二問(500点)

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

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

本番では、同じ数を含むものはColorfulには成り得ないことに気付かなかった。

そこで・・・


import java.util.ArrayList;

public class ColorfulStrings {

	public static int found = 0;
	public static int colorful_to_found;
	public static String answer = "";

	// 数値nのproductを求める。位ごとの数値をかけるだけ
	public int getProduct(String n) {
		int size = n.length();
		int ret = 1;
		for (int i = 0 ; i < size ; i++) {
			ret *= (n.charAt(i) - '0');
		}
		return ret;
	}


	// 数値xがColorfulであるかどうかを返す。
	public boolean isColorful(int x) {
		return isColorful(String.valueOf(x));
	}
	public boolean isColorful(String str) {
		ArrayList list = new ArrayList();
		int size = str.length();
		for (int i = 0 ; i < size ; i++) {
			for (int j = size ; j >= i + 1 ; j--) {
				int product = getProduct(str.substring(i, j));
				if (list.contains(product)) {
					return false;
				} else {
					list.add(product);
				}
			}
		}
		return true;
	}

	// 検索文字列を生成する。numsetは使える数、numsは現段階での文字列、kは残り使える数字の数
	public void generate(ArrayList<Integer> numset, String nums, int k) throws Exception  {
		// これ以上数字が使えない場合(求めるべき桁数に達したら)
		if (k == 0) {
			// Colorfulであるかどうかを調べて、
			if (isColorful(nums)) {
				// 見つけた数を1つ増やす。
				found++;
				// 発見数が目的の数に達したら、
				if (found == colorful_to_found) {
					// 答え用の変数answerに代入し、例外を投げて強制終了
					answer = nums;
					throw new Exception();
				}
			}
			return;
		}

		// 使用可能な数値を取り出す。このとき、numset中の数値は昇順になっているので
		// 数の小さい順に検索が可能
		for (Integer n : numset) {
			ArrayList<Integer> numset_copy_for_iterate = new ArrayList<Integer>(numset);

			// 数値nは次の桁では使えないので取り除き、再度ソートする
			numset_copy_for_iterate.remove(n);
			java.util.Collections.sort(numset_copy_for_iterate);
			generate(numset_copy_for_iterate, nums + String.valueOf(n), k - 1);
		}
	}

	public String getKth(int n, int k) {
		int ct = 0;

		// 9桁以上のColorfulな数は存在しない(同じ数、または1が桁に混じる)
		if (n >= 9) {
			return "";
		}

		// 1桁の数はすべてColorfulなので、特別扱いする
		if (n == 1) {
			if (k <= 10) {
				return String.valueOf(k - 1);
			} else {
				return "";
			}
		}
		ArrayList<Integer> numset = new ArrayList<Integer>();
		numset.add(2);
		numset.add(3);
		numset.add(4);
		numset.add(5);
		numset.add(6);
		numset.add(7);
		numset.add(8);
		numset.add(9);
		colorful_to_found = k;
		found = 0;
		try {
			generate(numset, "", n);
		} catch (Exception e) {
			// 例外が来たら、答えが出たので
			return answer;
		}

		// 見つからなかった
		return "";
	}

}

2桁以上で「0」「1」を含む数はColorfulにはなれないのであらかじめ除外。

文字列の生成に再帰を使ったので、もとめる数値が見つかった場合は例外を投げて

無理やり終了させるようにしてみました。そしてgetKthで結果をキャッチすると。

こういう書き方ってアリなんですかね。


SRM464 div2 第三問(1000点)

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

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

再帰で迷路を解く問題は割と得意なのですが、今回の場合は枝刈りのやり方が間違っておりました。


前回は、一マスに対して「罠に引っかからない確率」の最大値を記憶しておき、

再度マスに到達した際、上回っていなければ探索を打ち切っていたのですが。

次のようなケースが有るわけで・・・

 (ゴール)
  ↑
  B
 →●←
 ↑ ↑
 A B
 ↑ ↑
 ↑⇔↑
  ↑
(スタート)

⇔の地点で左右に分岐し、●で合流。Bの罠をくぐり抜けた先にゴールがあるとします。

ここで、Aが罠である確率を0.5、Bが罠である確率を0.7とすると、

●の地点では、無事に到達できる最大の確率は、Aを通った場合で0.5となりますが、

ゴールまでにBがあるため、結局⇔ではBを通った方がおトクになってしまい、

矛盾が生じることがわかります。


そこで、一マスに対しては「これまでにくぐった罠の組み合わせ」を保存することにします。

こういうプログラムを組んでみました。

import java.util.ArrayList;
import java.util.HashSet;

public class ColorfulMazeTwo {

	public static int start_x;
	public static int start_y;
	public static int goal_x;
	public static int goal_y;
	public static int h;
	public static int w;
	public static ArrayList[][] setmap;
	public static int[][] outmap;
	public static ArrayList setgoal;
	public static double max_to_goal;

	// setに含まれる罠をくぐり抜けたとき、無事である確率を求める
	// setはくぐり抜けた罠の組み合わせ。'A'、'C'などが入っている
	public double calc(HashSet set, int[] trap) {
		double prob = 1;
		if (set.isEmpty()) {
			return 1;
		}
		for(Object ch : set) {
			char c = (Character) ch;
			prob *= (double)(100 - trap[c - 'A']) / 100f;
		}
		return prob;
	}

	// 再帰的に探索して、ゴールまでにくぐり抜ける可能性のある罠の組み合わせを求める
	public int getMax(String[] maze, int x, int y, HashSet through, int[] trap) {
		if (x < 0 || x >= w || y < 0 || y >= h) return -1;
		char pt = maze[y].charAt(x);
		if (pt == '#') return -1;
		if (outmap[y][x] == 1) {
			return -1;
		}
		HashSet through_b = new HashSet(through);
		if (pt >= 'A' && pt <= 'G') {
			if (!through_b.contains(pt)) {
				through_b.add(pt);
			}
		} else if (pt == '!') {
			// ゴールまでに潜った罠の組み合わせを保存する
			if (!setgoal.contains(through_b)) {
				setgoal.add(through_b);
			}
			return 1;
		}

		// このマスに到達した罠の組み合わせを調べる。組み合わせを1つずつ取り出してsetと置く
		for (Object rs : setmap[y][x]) {
			HashSet set = (HashSet) rs;
			// set ⊆ through_bなるsetがあれば、探索打ち切り
			// setに1つ以上の罠を追加してthrough_bになるならば、
			// ゴールでの生存確率は低下するしか無いので
			if (through_b.containsAll(set)) {
				return 0;
			}
		}
		// 新しい罠の組み合わせでした
		setmap[y][x].add(through_b);

		int a = getMax(maze, x - 1, y, through_b, trap);
		int b = getMax(maze, x + 1, y, through_b, trap);
		int c = getMax(maze, x, y + 1, through_b, trap);
		int d = getMax(maze, x, y - 1, through_b, trap);
		if (a == -1 && b == -1 && c == -1 && d == -1) {
			outmap[y][x] = 1;
			return -1;
		}
		return 0;
	}


	public double getProbability(String[] maze, int[] trap) {
		h = maze.length;
		w = maze[0].length();
		setmap = new ArrayList[h][w];
		outmap = new int[h][w];
		setgoal = new ArrayList();

		// スタートとゴールの位置を求める
		for (int y = 0 ; y < h ; y++) {
			for (int x = 0 ; x < w ; x++) {
				if (maze[y].charAt(x) == '$') {
					start_x = x;
					start_y = y;
				} else if (maze[y].charAt(x) == '!') {
					goal_x = x;
					goal_y = y;
				}
				setmap[y][x] = new ArrayList();
				outmap[y][x] = 0;
			}
		}
		max_to_goal = 0;

		// 通る可能性のある罠の組み合わせを求める
		getMax(maze, start_x, start_y, new HashSet(), trap);

		// 罠の組み合わせの中から、最大の生存確率を求める
		for(Object rs : setgoal) {
			double prob = 1;
			HashSet set = (HashSet) rs;
			prob = calc(set, trap);
			if (max_to_goal < prob) {
				max_to_goal = prob;
			}
		}
		return max_to_goal;
	}
}

これで行けるのかなと思ったのですが、残念ながらTLE

最悪の場合、罠の組み合わせの分だけ迷路を全部舐めなければならないのできついのでしょう。

そこで、一度ゴールまで到達したら、そのときの生存確率を求めて、

途中で生存確率がそれより小さくなったら探索を打ち切る処理を加えてみました。

import java.util.ArrayList;
import java.util.HashSet;

public class ColorfulMazeTwo {

	// 再帰的に探索して、ゴールまでにくぐり抜ける可能性のある罠の組み合わせを求める
	public int getMax(String[] maze, int x, int y, HashSet through, int[] trap) {
		if (x < 0 || x >= w || y < 0 || y >= h) return -1;
		char pt = maze[y].charAt(x);
		if (pt == '#') return -1;
		if (outmap[y][x] == 1) {
			return -1;
		}
		HashSet through_b = new HashSet(through);
		if (pt >= 'A' && pt <= 'G') {
			if (!through_b.contains(pt)) {
				through_b.add(pt);
			}
		} else if (pt == '!') {
			// ゴールまでに潜った罠の組み合わせを保存する
			if (!setgoal.contains(through_b)) {
				setgoal.add(through_b);
			}

			// これを追加
			double tog = calc(through_b, trap);
			if (max_to_goal < tog) {
				max_to_goal = tog;
			}
			return 1;
		}

		// これも追加
		double tog = calc(through_b, trap);
		if (tog < max_to_goal) {
			return -1;
		}

		// このマスに到達した罠の組み合わせを調べる。組み合わせを1つずつ取り出してsetと置く
		for (Object rs : setmap[y][x]) {
			HashSet set = (HashSet) rs;
			// set ⊆ through_bなるsetがあれば、探索打ち切り
			// setに1つ以上の罠を追加してthrough_bになるならば、
			// ゴールでの生存確率は低下するしか無いので
			if (through_b.containsAll(set)) {
				return 0;
			}
		}
		// 新しい罠の組み合わせでした
		setmap[y][x].add(through_b);

		int a = getMax(maze, x - 1, y, through_b, trap);
		int b = getMax(maze, x + 1, y, through_b, trap);
		int c = getMax(maze, x, y + 1, through_b, trap);
		int d = getMax(maze, x, y - 1, through_b, trap);
		if (a == -1 && b == -1 && c == -1 && d == -1) {
			outmap[y][x] = 1;
			return -1;
		}
		return 0;
	}
}

これでなんとかSysTest通りました。やったー