Hatena::Grouptopcoder

TopCoder戦記

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

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-02-18SRM462 Div2

SRM462 Div2 Level Two(500pt.)

| 18:00

http://www.topcoder.com/stat?c=problem_statement&pm=10589&rd=14147

『1と0によって構成された文字列が与えられる。この文字列が与えられた数値を表すように、何進数表記であるかを求めよ。』

解答の範囲が(0,100]であることと文字列のパース処理(parseメソッド)が基数に対する増加関数であることに目をつけて、基数について2分探索を行いました。残念ながら本番では基数がstrictly positive=ゼロが許されないことを見落としており、数多くのテストを行ったものの解くことができませんでした。確かに0進数があるはずもなく、よく考えれば気づけたはずの失敗です。

public class AgeEncoding {
	public double getRadix(int age, String candlesLine) {
		if (age == 1 && parse(candlesLine, 2) == 1) {
			return -2;
		}
		if (candlesLine.indexOf('1') < 0) {
			return -1;
		}

		double max = 100;
		double min = 0;
		for (int i = 0; i < 300; ++i) {
			final double value = parse(candlesLine, (max + min) / 2);
			if (Double.compare(value, age) < 0) {
				min = (max + min) / 2;
			} else {
				max = (max + min) / 2;
			}
		}

		final double finish = parse(candlesLine, max);
		if (Math.abs(finish - age) < 0.0001 && min > 0) {	// min must be strictly positive
			return min;
		} else {
			return -1;
		}
	}

	private double parse(String candlesLine, double d) {
		double result = 0;
		double dd = 1;

		for (int i = candlesLine.length() - 1; i >= 0; --i) {
			if (candlesLine.charAt(i) == '1') {
				result += dd;
			}
			dd *= d;
		}
		return result;
	}
}

2010-01-20SRM459 DIV2

SRM459 DIV2 Level Two(500pt.)

| 22:02

http://www.topcoder.com/stat?c=problem_statement&pm=10682&rd=14145

『"X > 0","X <= 6"などの条件がいくつか与えられる。条件を最も多く同時に満たせる数を探し、その条件の数を求めよ。』

配列を用意して0.5刻みで調べる手法が多かったようですが、私は配列を利用せずに“条件の境界で、条件を満たす数の変化を求める”アプローチで解答しました。しかし今回のようにXがとりうる値が小さい場合は、配列を使う方がコードが単純になり好ましいでしょう。

import java.util.SortedSet;
import java.util.TreeSet;

public class Inequalities {
	public int maximumSubset(String[] inequalities) {
		final SortedSet<C> list = new TreeSet<C>();
		int max = 0;
		int current = 0;
		for (String command : inequalities) {
			String[] tokens = command.split(" ", 3);
			list.add(new C(Integer.parseInt(tokens[2]), tokens[1]));
			if (tokens[1].equals("<") || tokens[1].equals("<=")) {
				++max; ++current;
			}
		}

		int lastValue = 0;
		int delta = 0;
		boolean willDec = false;
		boolean willInc = false;
		for (C c : list) {
//			System.out.println(c);
			if (lastValue != c.value) {
				max = Math.max(max, current + delta);
				lastValue = c.value;
				delta = 0;
				if (willDec) {
					willDec = false;
					current--;
				}
				if (willInc) {
					willInc = false;
					current++;
				}
				max = Math.max(max, current);
			}

			if (c.type.equals("<")) {
				current--;
			} else if (c.type.equals(">=")) {
				current++;
			} else if(c.type.equals("=")) {
				delta = 1;
			}
			if (c.type.equals(">")) {
				willInc = true;
			} else if (c.type.equals("<=")) {
				willDec = true;
			}
		}

		max = Math.max(max, current + delta);
		delta = 0;
		if (willDec) {
			willDec = false;
			current--;
		}
		if (willInc) {
			willInc = false;
			current++;
		}
		max = Math.max(max, current);

		return max;
	}

	private static class C implements Comparable<C> {
		String type;
		int value;
		C(int v, String s) { this.value = v; this.type = s; }
		public int compareTo(C o) {
			if (this.value != o.value)
				return this.value - o.value; 
			else
				return this.type.compareTo(o.type);
		}
		public String toString() {
			return "x " + type + ' ' + value;
		}
	}
}

2010-01-16

SRM412 DIV1 Level One(250pt.)

| 15:03

条件に合う文字列を動的に組み立てる手法で再実装したもの。Aを0,Bを1,Cを2として扱っています。

public class ForbiddenStrings {
	private long[][][] memo = new long[31][4][4];

	public long countNotForbidden(int n) {
		return count(n, -1, -1);
	}

	private long count(int left, int prevprev, int prev) { // prevprevは2文字前、prevは1文字前の文字を表す
		if (left == 0) {
			return 1;
		}

		if (memo[left][prevprev + 1][prev + 1] == 0) {
			long count = 0L;
			for (int i = 0; i < 3; ++i) {
				if (prevprev >= 0 && prev >= 0 && i != prev && i != prevprev && prev != prevprev) {
					continue;
				}
				count += count(left - 1, prev, i);
			}
			memo[left][prevprev + 1][prev + 1] = count;
		}

		return memo[left][prevprev + 1][prev + 1];
	}

	public static void main(String args[]) {
		long count = new ForbiddenStrings().countNotForbidden(30);
		System.out.println(count);
	}
}

2010-01-04SRM457

SRM457 DIV2 Level Two(500pt.)

| 23:52

テストが甘く、ArrayIndexOutOfBoundsExceptionが出る段階で提出してしまいました。以下は該当個所を修正したコードであり、システムテストを通過します。

分が?になっている場合は無条件でゼロに置換できますが、時間が?になっている場合はGMTの値と照らしあわせなければなりません。このためとりうる値をすべて列挙し、もっとも小さいものを選択するアルゴリズムを作成しました。計算量は最大でも19*24で済みますので問題ありません。

import java.util.ArrayList;
import java.util.List;

public class TheTriangleBothDivs {
	public String fix(String time) {
		final int minute = Integer.parseInt(time.substring(3, 5).replace('?', '0'));

		int[] hours;
		if (time.startsWith("?")) {
			hours = new int[] { 0, 1, 2 };
		} else {
			hours = new int[] { time.charAt(0) - '0' };
		}
		if (time.charAt(1) == '?') {
			List<Integer> list = new ArrayList<Integer>();
			for (int hour : hours) {
				for (int i = 0; i < 10; ++i) {
					int newHour = hour * 10 + i;
					if (newHour < 24) {
						list.add(Integer.valueOf(newHour));
					}
				}
			}
			hours = new int[list.size()];
			for (int i = 0; i < hours.length; ++i) {
				hours[i] = list.get(i).intValue();
			}
		} else {
			List<Integer> list = new ArrayList<Integer>();
			for (int hour : hours) {
				int newHour = hour * 10 + (time.charAt(1) - '0');
				if (newHour < 24) {
					list.add(Integer.valueOf(newHour));
				}
			}
			hours = new int[list.size()];
			for (int i = 0; i < hours.length; ++i) {
				hours[i] = list.get(i).intValue();
			}
		}

		int[] gmts = null;
		if (time.endsWith("?")) {
			switch (time.charAt(9)) {
			case '+':
				gmts = new int[10];
				for (int i = 0; i < 10; ++i) { gmts[i] = i; }
				break;
			case '-':
				gmts = new int[9];
				for (int i = 1; i < 10; ++i) { gmts[i - 1] = -i; }	// ここがgmts[i]になっていた
				break;
			case '?':
				gmts = new int[19];
				for (int i = 0; i < 19; ++i) { gmts[i] = i - 9; }
				break;
			}
		} else {
			int gmtDigit = time.charAt(10) - '0';
			switch (time.charAt(9)) {
			case '+': gmts = new int[]{gmtDigit}; break;
			case '-': gmts = new int[]{-gmtDigit}; break;
			case '?': gmts = new int[]{gmtDigit, -gmtDigit}; break;
			}
		}

		int hour = 24;
		for (int gmt : gmts) {
			for (int h : hours) {
				h -= gmt;
				while (h < 0) h += 24;
				hour = Math.min(h % 24, hour);
			}
		}

		return String.format("%02d:%02d", hour, minute);
	}
}