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

2010-03-27

MemberSRM465 Medium(500pt.)

| 13:37

http://www.topcoder.com/stat?c=problem_statement&pm=10840&rd=14182

『2つの塔を設置したい。塔の中心となる候補地のリストが与えられるので、設置可能な位置と大きさの組み合わせを求めよ。塔は上方から見ると正方形であり、1辺の長さは1の倍数でなければならない。』

図には様々な角度で描かれていますが、塔が2つしかない以上複雑に考える必要はありません。塔を結んだ線分と塔の1辺が水平である場合のみを考えます。まず塔の距離を求め、重複組合せを使うことで「可能な大きさの組み合わせ」を求めました。

塔が3つ以上の場合もあると勘違いしたことが、スコアを低めた主因です。要所を抜き出す読み方に挑戦したものの、two gun towersと書かれていた部分を読み飛ばしてしまいました。努力の方向性として「要所を抜き出す」よりも「解読スピードを上げる」を目指すべきだったようです。

// 291.71 pt.
public class TurretPlacement {
	public long count(int[] x, int[] y) {
		long result = 0;
		for (int i = 0; i < x.length; ++i) {
			for (int j = i + 1; j < x.length; ++j) {
				result += calc(x[i], y[i], x[j], y[j]);
			}
		}
		return result;
	}

	private long calc(int x1, int y1, int x2, int y2) {
		final int dx = (x1 - x2) * (x1 - x2);
		final int dy = (y1 - y2) * (y1 - y2);
		final long distance = (long)((Math.sqrt(dx + dy) - 1) * 2); // 塔は最低でも0.5の距離を消費するので、1(=0.5*2)を引いておく

		return (distance + 2L) * (distance + 1L) / 2;
	}
}