Hatena::Grouptopcoder

TopCoder戦記

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

2010-07-11

SRM475 DIV1 Medium(600pt.)

| 18:00

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

『ねずみ算的に増えていくウサギの国がある。指定された年にカップルの数が半減するとき、k年後のカップルはいくつあるか。半減するときは年配者から優先して国を出るものとする。』

残念ながらTLEにて終わりました。1年ずつ計算する方法をとっていましたが、次に半減する年までを1度に算出するアルゴリズムでないと間に合わないようです。詳しくはTopSubmissionを参照。

import java.math.BigDecimal;
import java.util.Arrays;

public class RabbitIncreasing {
	private static final BigDecimal TWO = BigDecimal.ONE.add(BigDecimal.ONE);
	private static final BigDecimal MODULO = BigDecimal.valueOf(1000000009);

	public int getNumber(int[] leaving, int k) {
		BigDecimal elderCouples = BigDecimal.ZERO;
		BigDecimal newCouples = BigDecimal.ZERO;
		Arrays.sort(leaving);
		int cursor = 0;

		for (int i = 1; i <= k; ++i) {
			// Marth & April
			BigDecimal bornCouples = elderCouples;

			// July
			if (i == 1) {
				bornCouples = BigDecimal.ONE;
			}

			// November
			if (cursor < leaving.length && leaving[cursor] == i) {
				++cursor;
				BigDecimal leaveCouples = elderCouples.add(newCouples).add(bornCouples).divide(TWO, 0, BigDecimal.ROUND_UP);
//				System.out.printf("In November of year %d, %d out of %d couples will leave.%n", i, leaveCouples.longValue(), elderCouples.add(newCouples).add(bornCouples).longValue());

				elderCouples = elderCouples.subtract(leaveCouples);
				if (elderCouples.compareTo(BigDecimal.ZERO) < 0) {
					leaveCouples = elderCouples.abs();
					elderCouples = BigDecimal.ZERO;
					
					newCouples = newCouples.subtract(leaveCouples);
					if (newCouples.compareTo(BigDecimal.ZERO) < 0) {
						leaveCouples = newCouples.abs();
						newCouples = BigDecimal.ZERO;
						bornCouples = bornCouples.subtract(leaveCouples);
					}
				}
			}

			elderCouples = elderCouples.add(newCouples);
			newCouples = bornCouples;
		}

		return elderCouples.add(newCouples).remainder(MODULO).intValue();
	}

// BEGIN CUT HERE
	public static void main(String[] args) {
		RabbitIncreasing temp = new RabbitIncreasing();
//		System.out.println(temp.getNumber(new int[]{3}, 3));
//		System.out.println(temp.getNumber(new int[]{5, 9}, 10));
		System.out.println(temp.getNumber(new int[]{9999853, 9999856, 9999859, 9999862, 9999865, 9999868, 9999871, 9999874, 9999877, 9999880, 9999883, 9999886, 9999889, 9999892, 9999895, 9999898, 9999901, 9999904, 9999907, 9999910, 9999913, 9999916, 9999919, 9999922, 9999925, 9999928, 9999931, 9999934, 9999937, 9999940, 9999943, 9999946, 9999949, 9999952, 9999955, 9999958, 9999961, 9999964, 9999967, 9999970, 9999973, 9999976, 9999979, 9999982, 9999985, 9999988, 9999991, 9999994, 9999997, 10000000}, 10000000));
	}
// END CUT HERE
}