Hatena::Grouptopcoder

TopCoder戦記

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

2010-07-10

SRM475 DIV1 Easy(300pt.)

| 17:07

http://www.topcoder.com/stat?c=problem_statement&pm=10878&rd=14156

『r羽のウサギがNマスの列に入っている。ウサギが今いるマスの色と前ターンの移動方向に応じて移動するとき、最終的に何羽のウサギが残ることが期待されるか。列は毎ターン1マスずつ短くなる。』

「マスの色」「前ターンの移動方向」の記録方法だけきちんと考えておけば素早く解けそうな印象です。私は移動方向への配慮が遅れ、大きく減点を食らいました。

注意点すべきなのはBigDecimal#divideを使うところ。1÷3など循環小数になる(ArithmeticExceptionが発生する)可能性を考慮する必要があります。

import java.math.BigDecimal;
import java.util.Iterator;

public class RabbitStepping {
	static final int NOT_MOVED = 1;
	static final int MOVE_FROM_L = 2;
	static final int MOVE_FROM_R = 4;

	public double getExpected(String field, int r) {
		BigDecimal value = BigDecimal.ZERO;
		int many = 0;
		for (Long flag : new Combination(field.length(), r)) {
			final int[] rabbits = createRabbits(field, flag);
			value = value.add(BigDecimal.valueOf(calc(field, rabbits)));
			++many;
		}
		return value.divide(BigDecimal.valueOf(many), 9, BigDecimal.ROUND_HALF_UP).doubleValue();
	}

	private int[] createRabbits(String field, Long flag) {
		final int[] rabbits = new int[field.length()];
		for (int i = 0; i < field.length(); ++i) {
			if (((flag >>> i) & 1) == 1) {
				rabbits[field.length() - 1 - i] = NOT_MOVED;
			}
		}
		return rabbits;
	}

	private int calc(String field, int[] rabbits) {
		int count = sum(rabbits);
		for (int length = field.length(); length > 2 && count != 0; --length) {
			final int[] next = new int[rabbits.length];

			for (int i = 0; i < rabbits.length; ++i) {
				if (rabbits[i] == 0) continue;
				
				if (i == 0) {
					next[1] |= MOVE_FROM_L;
				} else if (i >= rabbits.length - 2) {
					next[i - 1] |= MOVE_FROM_R;
				} else {
					switch (field.charAt(i)) {
					case 'W': next[i - 1] |= MOVE_FROM_R; break;
					case 'B': next[i + 1] |= MOVE_FROM_L; break;
					case 'R': 
						if (rabbits[i] == MOVE_FROM_R) {
							next[i + 1] |= MOVE_FROM_L;
						} else {
							next[i - 1] |= MOVE_FROM_R;
						}
					}
				}
			}

			rabbits = new int[rabbits.length - 1];
			for (int i = 0; i < next.length - 1; ++i) {
				if (next[i] == MOVE_FROM_R || next[i] == MOVE_FROM_L) {
					rabbits[i] = next[i];
					++count;
				} else {
					rabbits[i] = 0;
				}
			}
			count = sum(rabbits);
		}
		return count;
	}

	private int sum(int[] rabbits) {
		int count = 0;
		for (int i : rabbits) {
			if (i != 0) ++count;
		}
		return count;
	}

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