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
}

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-25

SRM411 DIV1 Level Two(500pt.)

| 20:46

http://www.topcoder.com/stat?c=problem_statement&pm=9752&rd=12183

『中央に四角い穴が開いた四角いケーキがある。これをX軸・Y軸それぞれに平行な線で切るとき、いくつのケーキ片ができるか求めよ。』

穴の存在によってパターンがやや複雑になっています。穴にかかる2本の平行線を引くと、その線と穴によって2つのケーキ片ができるためです(穴がなければ1つ)。はじめに実行している配列変数の初期化がややこしく見えますが、渡された配列にケーキの端を表す座標を追加した上でソートしているだけです。

import java.util.Arrays;

public class HoleCakeCuts {
	public int cutTheCake(int cakeLength, int holeLength,
			int[] _horizontalCuts, int[] _verticalCuts) {
		final int[] verticalCuts = new int[_verticalCuts.length + 2];
		final int[] horizontalCuts = new int[_horizontalCuts.length + 2];
		System.arraycopy(_verticalCuts, 0, verticalCuts, 1, _verticalCuts.length);
		System.arraycopy(_horizontalCuts, 0, horizontalCuts, 1, _horizontalCuts.length);
		verticalCuts[0] = -cakeLength;
		horizontalCuts[0] = -cakeLength;
		verticalCuts[verticalCuts.length - 1] = cakeLength;
		horizontalCuts[horizontalCuts.length - 1] = cakeLength;
		Arrays.sort(verticalCuts);
		Arrays.sort(horizontalCuts);

		int count = 0;
		for (int xIndex = 0; xIndex < verticalCuts.length - 1; ++xIndex) {
			for (int yIndex = 0; yIndex < horizontalCuts.length - 1; ++yIndex) {
				final int x1 = verticalCuts[xIndex];
				final int x2 = verticalCuts[xIndex + 1];
				final int y1 = horizontalCuts[yIndex];
				final int y2 = horizontalCuts[yIndex + 1];

				if (Math.abs(x1) > holeLength ||  Math.abs(x2) > holeLength ||
						 Math.abs(y1) > holeLength ||  Math.abs(y2) > holeLength) {
					// 穴によって2つ以上に分割されているか?
					if (Math.abs(x1) <= holeLength && Math.abs(x2) <= holeLength &&
							Math.abs(y1) > holeLength && Math.abs(y2) > holeLength && y1 * y2 < 0) {
						count += 2;
					} else if (Math.abs(y1) <= holeLength && Math.abs(y2) <= holeLength && 
							Math.abs(x1) > holeLength && Math.abs(x2) > holeLength && x1 * x2 < 0) {
						count += 2;
					} else { 
						++count;
					}
				}
			}
		}

		return count;
	}
}

2010-01-10

SRM413 Div1 Level Two(500pt.)

| 09:43

http://www.topcoder.com/stat?c=problem_statement&pm=9922&rd=13504

『特定の法則にしたがった無限長の数列が存在する。この数列のn番めの要素を求めよ。』

アルゴリズム自体は非常に簡単ですが、Mapを使ったメモ化を書いてしまい2秒に収まらないコードとなりました。long[]を利用したシンプルなものに置き換えて解決。

import java.util.Arrays;

public class InfiniteSequence2 {
	private final long[] memo = new long[5000000];
	private int q;
	private int p;
	private int x;
	private int y;

	public long calc(long n, int p, int q, int x, int y) {
		this.p = p;
		this.q = q;
		this.x = x;
		this.y = y;
		Arrays.fill(memo, -1L);
		return calc(n);
	}

	private long calc(long n) {
		if (n <= 0) return 1L;

		long stored = -1L;
		if (n < memo.length)
			stored = memo[(int) n];

		if (stored == -1L) {
			stored = calc(indexOf(n, p, x)) + calc(indexOf(n, q, y));

			if (n < memo.length)
				memo[(int) n] = stored;
		}
		return stored;
	}

	private long indexOf(long now, int div, int sub) {
		return now / div - sub;
	}
}

2009-12-31

SRM414 DIV1 Level Two(500pt.)

| 10:00

http://www.topcoder.com/stat?c=problem_statement&pm=8772&rd=13505

『与えられた複数の文字列から頭文字を取り出して連結させ、ひとつの文字列を作る。作りうる文字列のうち辞書順に最も小さなものを示せ。』

同じ頭文字を持つ文字列がある場合について難しく考えすぎたため、時間切れになってしまいました。

JavaのTopSubmissionを書き直したのが以下のコードです。これは文字列の比較に「基本的に文字をつき合わせて比較するが、長さが足りない場合は長い方を小さいとみなす」Comparatorを利用しています。C++のTopSubmissionのように、あらかじめZよりも大きい文字で埋めることによって文字列長を揃えることも有効なようです。

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

public class StringInterspersal {
	public String minimum(String[] W) {
		final List<String> list = createListFrom(W);
		final StringBuilder result = new StringBuilder();
		final Comparator<String> comparator = new Comparator<String>() {
			public int compare(String o1, String o2) {
				for (int i = 0; i < o1.length() && i < o2.length(); i++) {
					if (o1.charAt(i) != o2.charAt(i)) return o1.charAt(i) - o2.charAt(i);
				}
				// 長い方を優先的に選ぶ必要がある。例: "ZA" & "Z"
				return o2.length() - o1.length();
			}
		};

		while (!list.isEmpty()) {
			Collections.sort(list, comparator);
			String target = list.get(0);
			result.append(target.charAt(0));
			if (target.length() == 1) {
				list.remove(0);
			} else {
				list.set(0, target.substring(1));
			}
		}

		return result.toString();
	}

	private List<String> createListFrom(String[] w) {
		List<String> result = new ArrayList<String>(w.length);
		for (String word : w) {
			result.add(word);
		}
		return result;
	}
}