Hatena::Grouptopcoder

TopCoder戦記

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

2011-05-18SRM 504.5

SRM 504.5 Easy

| 00:30

問題文:http://www.topcoder.com/stat?c=problem_statement&pm=11096&rd=14514

このEasyだけは落とすまいとテストケースを相当書きました。今の自分のRatingでは、Mediumを頑張って通すよりもEasyを確実に通してchallengeで稼ぐ方が確実だと考えるためです。

今回はEasyを落とす人が少なかったのでこれだけ通してもあまり嬉しくなかったのですが、方針として大きく誤ってはいないと思うのでしばらくこのEasy死守戦略を続けてみます。

public class TheNumbersWithLuckyLastDigit {
	public int find(int n) {
		if (n < 4 || n == 6 || n == 10)
			return -1;

		switch (n % 10) {
		case 4:
		case 7:
			return 1;
		case 0:
			return 5;
		case 2:
			return 3;
		case 6:
			return 4;
		case 8:
			return 2;
		default:
			if (n % 2 == 1) {
				int k = find(n - 7);
				return k == -1 ? -1 : k + 1;
			}
			return -1;
		}
	}

	// BEGIN CUT HERE
	public static void main(String[] args) {
		TheNumbersWithLuckyLastDigit temp = new TheNumbersWithLuckyLastDigit();
		System.out.println(temp.find(1) == -1);
		System.out.println(temp.find(2) == -1);
		System.out.println(temp.find(3) == -1);
		System.out.println(temp.find(4) == 1);
		System.out.println(temp.find(5) == -1);
		System.out.println(temp.find(6) == -1);
		System.out.println(temp.find(7) == 1);
		System.out.println(temp.find(8) == 2);
		System.out.println(temp.find(9) == -1);
		System.out.println(temp.find(10) == -1);
		System.out.println("===");

		System.out.println(temp.find(11) == 2);
		System.out.println(temp.find(12) == 3);
		System.out.println(temp.find(13) == -1);
		System.out.println(temp.find(14) == 1);
		System.out.println(temp.find(15) == 3);
		System.out.println(temp.find(16) == 4);
		System.out.println(temp.find(17) == 1);
		System.out.println(temp.find(18) == 2);
		System.out.println(temp.find(19) == 4);
		System.out.println(temp.find(20) == 5);
		System.out.println("===");

		System.out.println(temp.find(21) == 2);
		System.out.println(temp.find(23) == 5);
		System.out.println("===");

		System.out.println(temp.find(99) == 4);
		System.out.println(temp.find(11) == 2);
		System.out.println(temp.find(13) == -1);
		System.out.println(temp.find(1234567) == 1);
	}
	// END CUT HERE
}

今回は二重ループで解を求める形が最もシンプルで好ましかったのではと思います。ただループの回数が足りずに撃墜されているケースもあったので、最低でも何回ループするかをきちんと考えることが重要です。下1桁だけ考えればいいことに着目すると、4で終わる数は少なくとも6個以上にならないこと・7で終わる数は少なくとも10個以上にならないことが言えそう*1ですので、以下のような二重ループにすべきだったのでしょう。

	public int find(int n) {
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < 6; ++i) {
			for (int j = 0; j < 10; ++j) {
				if ((i * 4 + j * 7) % 10 == n % 10 && i * 4 + j * 7 <= n && i + j > 0) {
					result = Math.min(result, i + j);
				}
			}
		}
		return result == Integer.MAX_VALUE ? -1 : result;
	}

*1:もっときちっと考えると削れそうですが、計算量的には大差ないのでこれでOKとする

2010-09-27SRM382 DIV1

SRM382 DIV1 easy

| 09:05

http://www.topcoder.com/stat?c=problem_statement&pm=8319&rd=10805

import java.util.Arrays;

// 84.58 pt.
public class CollectingRiders {
	private int[][] powers;

	public int minimalMoves(String[] board) {
		powers = new int[board.length][board[0].length()];
		int[][] turns = new int[board.length][board[0].length()];

		int y = 0;
		for (String line : board) {
			int x = 0;
			for (char cell : line.toCharArray()) {
				if (Character.isDigit(cell)) {
					int[][] turnsFromCell = createArray(turns, Integer.MAX_VALUE);
					turnsFromCell[y][x] = 0;
					markNext(turnsFromCell, x, y, cell - '0', 1, cell - '0');
					add(turns, turnsFromCell);
				}
				++x;
			}
			++y;
		}

		return minOf(turns);
	}
	
	private int minOf(int[][] turns) {
		int result = Integer.MAX_VALUE;
		for (int[] a : turns) {
			for (int b : a) {
				result = Math.min(result, b);
			}
		}

		return result == Integer.MAX_VALUE ? -1 : result;
	}

	private void add(int[][] turns, int[][] turnsFromCell) {
		for (int i = 0; i < turns.length; ++i) {
			for (int j = 0; j < turns[0].length; ++j) {
				if (turnsFromCell[i][j] == Integer.MAX_VALUE) {
					turns[i][j] = Integer.MAX_VALUE;
				} else if (turns[i][j] != Integer.MAX_VALUE) {
					turns[i][j] += turnsFromCell[i][j];
				}
			}
		}
	}

	private static final int[] JUMP_X = new int[] {-1, 1, 2, 2, 1,-1,-2,-2};
	private static final int[] JUMP_Y = new int[] {-2,-2,-1, 1, 2, 2, 1,-1};

	private void markNext(int[][] a, int x, int y, int power, int turn, int maxPower) {
		if (turn == 10) return;

		for (int i = 0; i < JUMP_X.length; ++i) {
			int jumpX = x + JUMP_X[i];
			int jumpY = y + JUMP_Y[i];

			if (jumpX < 0 || jumpY < 0 || a.length <= jumpY || a[0].length <= jumpX) {
				continue;
			} else if (a[jumpY][jumpX] == turn) {
				if (power > 1 && powers[jumpY][jumpX] < power) {
					powers[jumpY][jumpX] = power;
					markNext(a, jumpX, jumpY, power - 1, turn, maxPower);
				}
			} else if (a[jumpY][jumpX] >= turn) {
				a[jumpY][jumpX] = turn;
				powers[jumpY][jumpX] = power;
				if (power > 1) {
					markNext(a, jumpX, jumpY, power - 1, turn, maxPower);
				}
				markNext(a, jumpX, jumpY, maxPower, turn + 1, maxPower);
			}
		}
	}

	private int[][] createArray(int[][] source, int defaultValue) {
		int[][] result = new int[source.length][source[0].length];
		for (int[] a : result) {
			Arrays.fill(a, defaultValue);
		}
		return result;
	}

// BEGIN CUT HERE
	public static void main(String[] args) {
		CollectingRiders temp = new CollectingRiders();
		System.out.println(temp.minimalMoves(new String[] {"1.", "..", "..", "..", "..", "1."}));
	}
// END CUT HERE
}

2010-09-26SRM483 DIV1

SRM483 DIV1 easy(250pt.)

| 09:06

残念ながら、本番ではyuyarin氏と同じ理由で落ちてしまいました。

やらしい... Test Case: 138 Args: {1000, "0.812983"} Expected: "313/385 has 6 exact digits" Received: "526/647 has 7 exact digits"less than a minute ago via YoruFukurou

修正したコードは以下。

import java.text.DecimalFormat;
import java.text.NumberFormat;

public class BestApproximationDiv1 {
	public String findFraction(int maxDen, String number) {
		NumberFormat format = new DecimalFormat("0.000000000");	// ゼロが足りずに落ちた
		int exact = 0, resultA = 0, resultB = 0;
		double numberF = Double.valueOf(number);

		for (int b = 1; b <= maxDen && exact != 7; ++b) {
			int firstA = Math.min(10 + (int)(b * numberF), b - 1);	// 枝刈り。10という数値には特に根拠なし
			for (int a = firstA; a >= 0; --a) {
				double f = a / (double) b;
				int same = sameOf(number, format.format(f));
				if (same > exact) {
					exact = same;
					resultA = a;
					resultB = b;
				} else if (same == exact && a < resultA) {
					resultA = a;
					resultB = b;
				}

				if (f < numberF) break;	// 枝刈り。
			}
		}
	
		return String.format("%d/%d has %d exact digits", resultA, resultB, exact);
	}

	private int sameOf(String number, String format) {
		for (int i = 0; i < number.length(); ++i) {
			if (number.charAt(i) != format.charAt(i)) return i - 1;
		}

		return 7;
	}

// BEGIN CUT HERE
	public static void main(String[] args) {
		BestApproximationDiv1 temp = new BestApproximationDiv1();
		System.out.println(temp.findFraction(1000, "0.000007"));
	}
// END CUT HERE
}

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