Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2010-03-21

SRM464 Div2 Easy(250pt.)

| 23:10

http://www.topcoder.com/stat?c=problem_statement&pm=10743&rd=14149

『箱とボールが同数ずつ存在する。これらは赤または青に色分けされており、ボールを同じ色の箱に入れた場合と違う色の箱に入れた場合では得点が異なる。与えられた条件のもとで、最高の得点を求めよ。』

考えられるすべての組み合わせで得点を求め、その最大値を返しました。実際は「できるだけ違う色に入れた場合」と「できるだけ同じ色に入れた場合」の2パターンについてのみ求めれば充分だったようです。

public class ColorfulBoxesAndBalls {
	public int getMaximum(int numRed, int numBlue, int onlyRed, int onlyBlue, int bothColors) {
		int maxScore = Integer.MIN_VALUE;
		final int num = numRed + numBlue;
		for (int different = 0; different <= num && different / 2 <= numRed && different / 2 <= numBlue; different += 2) {
			final int score = onlyRed * (numRed - different / 2) + onlyBlue * (numBlue - different / 2) + bothColors * different;
			maxScore = Math.max(maxScore, score);
		}
		return maxScore;
	}
}

SRM464 Div2 Medium(500pt.)

| 23:10

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

TLE解消せず。

import java.util.HashSet;
import java.util.Set;

public class ColorfulStrings {
	public String getKth(int n, int k) {
		if (n == 1) {
			return k > 10 ? "" : Integer.toString(k - 1);
		}
		if (n > 8 || k > f(8) / f(8 - n)) return "";

		int found = 0, end = endOf(n), i;
		for (i = beginOf(n); found < k && i < end; ++i) {
			if (isColorful(i)) ++found;
		}
		final String result = Integer.toString(i - 1);
		return result.length() == n ? result : "";
	}

	private int endOf(int n) {
		int result = 1;
		for (int i = 0; i < n; ++i) {
			result = result * 10;
		}
		return result + 1;
	}

	private int f(int i) {
		return i > 1 ? i * f(i - 1) : 1;
	}

	private int beginOf(int n) {
		if (n == 1) return 0;

		int result = 0;
		for (int i = 0; i < n; ++i) {
			result = result * 10 + (i + 1);
		}
		return result;
	}

	private boolean isColorful(int num) {
		final String asStr = Integer.toString(num);
		if (asStr.contains("0") || asStr.contains("1")) {
			return false;
		}
		final Set<Integer> products = new HashSet<Integer>();

		for (int start = 0; start < asStr.length(); ++start) {
			for (int end = start + 1; end <= asStr.length(); ++end) {
				if (!products.add(productOf(asStr, start, end))) return false;
			}
		}
		return true;
	}

	private Integer productOf(String string, int start, int end) {
		int answer = 1;
		for (int i = start; i < end; ++i) {
			answer *= string.charAt(i) - '0';//Character.digit(string.charAt(i), 10);
		}
		return Integer.valueOf(answer);
	}
}

SRM464 Div2 Hard(1000pt.)

| 23:10

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

『色つきの床がある迷路の脱出可能性を求めよ。色つきの床には罠が仕掛けられている場合があり、色ごとにその可能性が与えられる。』

"今までに踏んだ色つきの床の種類"をBitSetを使って管理しました。BitSetがImmutableなら、もっとシンプルに書けたはずですが……。

なお探索は幅優先でなく深さ優先で行っています。実装が容易だったことも理由のひとつですが、マスを探索する必要があるかどうかを「前回マス到達時に今と同じ色のマスを踏んでいるかどうか」で判定していることが最大の理由です。幅優先探索では他のマスを経由している探索プロセスによって上書かれることがあり、計算回数が増えるものと思われます。

import java.util.BitSet;

public class ColorfulMazeTwo {
	private BitSet[][] bitSets;
	private double answer;

	public double getProbability(String[] maze, int[] trap) {
		this.bitSets = new BitSet[maze[0].length()][maze.length];
		int start = 0;
		int goal = 0;
		
		for (int y = 0; y < maze.length; ++y) {
			for (int x = 0; x < maze[0].length(); ++x) {
				final char c = maze[y].charAt(x);
				switch (c) {
					case '$': 
						start = y * maze[0].length() + x;
						break;
					case '!':
						goal = y * maze[0].length() + x;
						break;
				}
			}
		}

		this.answer = 0.0d;
		find(maze, trap, start, goal, new BitSet());
		return answer;
	}

	private void find(String[] maze, int[] trap, int start, int goal, BitSet bitSet) {
		final int x = start % maze[0].length();
		final int y = start / maze[0].length();

		final BitSet currentBitSet = (BitSet) bitSet.clone();
		final char floor = maze[y].charAt(x);
		if ('A' <= floor && floor <= 'G') {
			currentBitSet.set(floor - 'A');
		}

		final double currentProb = calcProb(trap, currentBitSet);
		if (floor == '#' || contains(bitSets[x][y], currentBitSet) || Double.compare(this.answer, currentProb) >= 0) {
			return;
		}
		bitSets[x][y] = currentBitSet;

		if (start == goal) {
			this.answer = Math.max(this.answer, currentProb);
		} else {
			if (x > 0) {
				find(maze, trap, start - 1, goal, currentBitSet);
			}
			if (y > 0) {
				find(maze, trap, start - maze[0].length(), goal, currentBitSet);
			}
			if (x + 1 < maze[0].length()) {
				find(maze, trap, start + 1, goal, currentBitSet);
			}
			if (y + 1 < maze.length) {
				find(maze, trap, start + maze[0].length(), goal, currentBitSet);
			}
		}
	}

	// bitSetに含まれるすべてのbitがcurrentにあるならtrue
	private boolean contains(BitSet bitSet, BitSet currentBitSet) {
		if (bitSet == null) return false;

		for (int i = 0; i < bitSet.length(); ++i) {
			if (bitSet.get(i) && !currentBitSet.get(i)) return false;
		}
		return true;
	}

	private double calcProb(int[] trap, BitSet bitSet) {
		double prob = 1.0D;
		for (int i = 0; i < trap.length; ++i) {
			if (bitSet.get(i)) prob = (100 - trap[i]) * prob / 100D;
		}
		return prob;
	}
}