Hatena::Grouptopcoder

TopCoder戦記

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

2009-10-05SRM426 DIV2

SRM426 DIV2 Level Two(500pt.) リベンジ

| 21:35

デッキの取りうる全ての組み合わせを考える必要はなく、期待値が最大となる場合のみを考慮することで計算量を削減。非常にシンプルなコードになりました。テストケースも全てクリアしています。

// 150.00 pt.

import java.util.Arrays;

public class ShufflingMachine {
	// TLE TestCase
	public static void main(String[] args) {
		int[] shuffle = { 29, 7, 25, 0, 47, 17, 41, 13, 14, 10, 39, 16, 43, 49,
				8, 11, 9, 35, 38, 5, 18, 45, 30, 22, 28, 15, 2, 19, 37, 36, 34,
				27, 4, 40, 46, 6, 3, 48, 23, 31, 20, 42, 12, 33, 26, 1, 24, 21,
				44, 32 };
		int[] cardsReceived = { 10, 16, 0, 24 };

		long time = System.currentTimeMillis();
		double value = new ShufflingMachine().stackDeck(shuffle, 98, cardsReceived, 38);
		System.out.println(System.currentTimeMillis() - time);
		assert Math.abs(value - 3.9285714285714284) < 1e-9;
	}

	public double stackDeck(int[] shuffle, int maxShuffles,
			int[] cardsReceived, int K) {
		int[] cardIdx = new int[shuffle.length];
		for (int i = 0; i < cardIdx.length; ++i) {
			cardIdx[i] = i;
		}
		int[] drawed = new int[shuffle.length];
		for (int i = 0; i < maxShuffles; ++i) {
			execShuffule(cardIdx, shuffle);
			for (int idx : cardsReceived) {
				++drawed[cardIdx[idx]];
			}
		}
		Arrays.sort(drawed);

		int sum = 0;
		for (int i = 1; i <= K; ++i) {
			sum += drawed[shuffle.length - i];
		}
		return sum / (double) maxShuffles;
	}

	private void execShuffule(int[] cardIdx, int[] shuffle) {
		int[] clone = cardIdx.clone();
		for (int i = 0; i < cardIdx.length; ++i) {
			cardIdx[i] = clone[shuffle[i]];
		}
	}
}