Hatena::Grouptopcoder

TopCoder戦記

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

2009-10-05SRM426 DIV2

SRM426 DIV2 Level Two(500pt.)

| 20:52

http://www.topcoder.com/stat?c=problem_statement&pm=10196&rd=13517

『一定の法則にしたがってデッキをシャッフルする機械がある。機械に入れるデッキの並び順が操作可能なとき、K枚の欲しいカードのうち手元に配られる枚数の期待値を求めよ。』

先日作成したnext_combinationを利用した解答。Kが小さいときは問題なく解答できますが、1〜2個のテストケースで時間切れになってしまいます。引数が比較的大きくなるため、組み合わせを使うケースとしては不適でした。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ShufflingMachine {
	// 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;
		}
		List<Long> drawPattern = createDrawPattern(shuffle, maxShuffles,
				cardsReceived, cardIdx);

		double result = 0D;
		for (long comb : new Combination(shuffle.length, K)) {
			int get = 0;
			for (Long flag : drawPattern) {
				get += Long.bitCount(flag & comb);
			}
			result = Math.max(result, (double) get / drawPattern.size());
		}
		return result;
	}

	private List<Long> createDrawPattern(int[] shuffle, int maxShuffles,
			int[] cardsReceived, int[] cardIdx) {
		List<Long> drawPattern = new ArrayList<Long>();
		for (int i = 0; i < maxShuffles; ++i) {
			execShuffule(cardIdx, shuffle);
			BigInteger flag = BigInteger.ZERO;
			for (int idx : cardsReceived) {
				flag = flag.setBit(cardIdx[idx]);
			}
			drawPattern.add(flag.longValue());
		}
		return drawPattern;
	}

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

	private static class Combination implements Iterable<Long> {
		private final int max;
		private final int select;

		public Combination(int max, int select) {
			if (max < 1 || 62 < max) {
				throw new IllegalArgumentException();
			}
			this.max = max;
			this.select = select;
		}

		public Iterator<Long> iterator() {
			return new CombinationIterator(max, select);
		}
	}

	private static class CombinationIterator implements Iterator<Long> {
		private long value;
		private final long max;

		public CombinationIterator(int max, int select) {
			this.value = (1L << select) - 1L;
			this.max = 1L << max;
		}

		public boolean hasNext() {
			return value < max;
		}

		public Long next() {
			long stock = value;
			value = next(value);
			return stock;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

		private long next(long source) {
			long param1 = smallestBitOf(source);
			long param2 = param1 + source;
			long param3 = smallestBitOf(param2);
			long param5 = (param3 / param1) >>> 1;
			return param5 - 1 + param2;
		}

		private long smallestBitOf(long source) {
			long result = 1L;
			while (source % 2 == 0) {
				source >>>= 1;
				result <<= 1;
			}
			return result;
		}
	}
}