Hatena::Grouptopcoder

TopCoder戦記

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

2010-03-21

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;
	}
}

2010-03-13

SRM463 DIV1 Medium(500pt.)

| 17:34

http://www.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148

本番ではすべての組み合わせを行うコードを書いてみたものの、5番目のサンプルすら通らず。TopSubmissionを見たところ非常に単純なコードで驚きました。「加算した結果を再度加算することはない」「N個の数値を加算するとき、i番めとN-i-1番めを加算する」というシンプルな規則に気づけなければこのコードには至れないでしょう。

import java.util.Arrays;

public class Nisoku {
	public double theMax(double[] cards) {
		Arrays.sort(cards);
		double answer = 0.0d;
		for (int border = 0; border <= cards.length; border += 2) {
			double total = 1.0d;

			for (int i = 0; i < border; i += 2) {
				total *= cards[i] + cards[border - i - 1];
			}
			for (int i = border; i < cards.length; ++i) {
				total *= cards[i];
			}

			answer = Math.max(answer, total);
		}
		return answer;
	}
}

2010-01-04SRM457

SRM457 DIV2 Level Three(1000pt.)

| 23:52

題意から地図の塗り分け問題*1を連想したため、余りが同じになる数字を「同じ色を持つ」と表現して実装しました。

まず中央を陣取る色を選択することで、残り6マスはそれ以外の色となることが決まります。あとは同じ色が隣り合わないよう配慮しつつ時計回りに配色を施し、組み合わせの合計を6で割ることで解が得られます。

public class TheHexagonsDivTwo {
	public long count(int n, int k) {
		if (n < 7 || k < 3) return 0L;

		final int[] colors = new int[k];
		for (int i = 0; i < n; ++i) colors[i % k]++;

		long total = 0L;
		final int[] choiced = new int[k];
		for (int centered = 0; centered < k; ++centered) {
			total += colors[centered] * choice(colors, choiced, centered, 0, -1, -1);
		}

		return total / 6L;
	}

	private long choice(int[] colors, int[] choiced, int center, int index, int prev, int first) {
		long count = 0L;
		if (index == 5) {
			for (int i = 0; i < colors.length; ++i) {
				if (i == center || i == first || i == prev) continue;
				if (colors[i] > choiced[i])
					count += colors[i] - choiced[i];
			}
		} else if (index == 0) {
			for (int i = 0; i < colors.length; ++i) {
				if (i == center || colors[i] == choiced[i]) continue;
				choiced[i]++;
				long c = choice(colors, choiced, center, 1, i, i);
				choiced[i]--;
				count += (colors[i] - choiced[i]) * c;
			}
		} else {
			for (int i = 0; i < colors.length; ++i) {
				if (i == center || i == prev || colors[i] == choiced[i]) continue;
				choiced[i]++;
				long c = choice(colors, choiced, center, index + 1, i, first);
				choiced[i]--;
				count += (colors[i] - choiced[i]) * c;
			}
		}
		return count;
	}
	
	public static void main(String[] args) {
		System.out.println(new TheHexagonsDivTwo().count(20, 5));
	}
}

*1:どんな地図でも4色で塗り分けられることを証明する問題

2009-12-23

SRM456 DIV2 Level Three(1000pt.)

| 12:42

http://www.topcoder.com/stat?c=problem_statement&pm=10563&rd=13909

未提出です。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CutSticks {
	public double maxKth(int[] sticks, int C, int K) {
		K--;
		List<Double> dSticks = asDouble(sticks);
		Collections.sort(dSticks, new DescComparator());
		for (int i = 0; i < C; ++i) {
			double length = K < dSticks.size() ? dSticks.get(K) : 0;
			double next = next(dSticks);
			if (length < next) {
				double longest = dSticks.remove(0);
				dSticks.add(next);
				dSticks.add(longest - next);
				Collections.sort(dSticks, new DescComparator());
			} else {
				break;
			}
		}
		for (double d : dSticks) {
			System.out.println(d);
		}
		return dSticks.get(K);
	}

	private List<Double> asDouble(int[] sticks) {
		List<Double> result = new ArrayList<Double>();
		for (int stick : sticks)
			result.add((double) stick);
		return result;
	}

	private double next(List<Double> sticks) {
		if (sticks.size() == 1) {
			return sticks.get(0) / 2.0D;
		} else {
			double first = sticks.get(0);
			double second = sticks.get(1);
			return Math.max(first / 2.0D, first - second);
		}
	}

	private static class DescComparator implements Comparator<Double> {
		public int compare(Double o1, Double o2) {
			return -Double.compare(o1, o2);
		}
	}
}

SRM456 DIV2 Level Three(1000pt.)

| 21:08

http://www.topcoder.com/stat?c=problem_statement&pm=10563&rd=13909

TopSubmissionを解読して理解し、独自に書き直し。

仮説を立てた上で2分探索するというコンピュータならではのアルゴリズムです。

public class CutSticks {
	public double maxKth(int[] sticks, int C, int K) {
		double high = 1000000000;
		double low  = 0;

		for (int i = 0; i < 300; ++i) {
			/** K番めまでのstickが一様にこれ以上の長さを持つと仮説 */
			double hypothesis  = (high + low) / 2.0D;
			/** stickを折った回数 */
			int divided = 0;
			/** stickを折るなどして確保した、仮説した長さ以上のstickの総数 */
			int created = 0;

			for (double length : sticks) {
				if (length < hypothesis) continue;

				/** このstickを折ることで、仮説した長さのstickを何本作れるか? */
				int creatable = (int)(length / hypothesis);
				if (divided + (creatable - 1) > C) {
					// 折りすぎを抑制
					creatable = C - divided + 1;
				}
				divided += creatable - 1;
				created += creatable;
			}
			if (created < K) {
				// より多くのスティックを作るため、仮説を短くする
				high = hypothesis;
			} else {
				// スティックの数は足りているため、仮説を長くする
				low = hypothesis;
			}
		}
		return low;
	}
}

2009-12-16SRM415 DIV2

SRM415 DIV2 Level Three(1000pt.)

| 21:37

http://www.topcoder.com/stat?c=problem_statement&pm=9934&rd=13506

『あなたはカードゲームのディーラーで、特定のプレイヤーに意図したカードを配りたい。シャッフルでどのようにカードが入れ替わるかが与えられるとき、必要なシャッフル回数の最小値を求めよ。不可能な場合は-1を返せ。』

レベル3の割に特にひねりなく解答できました。チートが成功するまでシャッフルを続け、デッキの状態が最初と同じになってしまった場合のみ-1を返します。

// 898.50 pt.
import java.util.Arrays;

public class CardsCheating {
	private int[] shuffle;

	public int numberOfShuffles(int[] cards, int[] shuffle) {
		this.shuffle = shuffle;
		int[] initial = cards.clone();

		int count = 0;
		do {
			if (successToCheat(cards)) {
				return count;
			}
			cards = shuffleCards(cards);
			++count;
		} while (!Arrays.equals(cards, initial));
		return -1;
	}
	
	private boolean successToCheat(int[] cards) {
		for (int i = 0; i < cards.length; ++i) {
			if (cards[i] != i % 3) {
				return false;
			}
		}
		return true;
	}

	private int[] shuffleCards(int[] cards) {
		int[] result = new int[cards.length];
		for (int i = 0; i < result.length; ++i) {
			result[shuffle[i]] = cards[i];
		}
		return result;
	}
}