Hatena::Grouptopcoder

TopCoder戦記

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

2010-05-04SRM469 DIV2

SRM469 DIV2 Medium

| 23:21

http://www.topcoder.com/stat?c=problem_statement&pm=10901&rd=14152

『怖い映画を何本か観ようと考える。それぞれの映画には1つずつ怖い瞬間があり観ることで緊張感が増す。緊張感は時間とともに低下し、-0.5になると眠ってしまう。最も多くの映画を観るためには、どの順番で映画を選択すべきか。同じ本数を観られる組み合わせが複数ある場合、辞書順に最も小さいものを返せ。』

映画は最大でも7本なので、全探索で問題ないと判断。以前実装したJava版next_permutationを流用し、愚直な実装を目指しました。

問題文ではscare level(仮に緊張感と翻訳)が小数だとされていますが、これは単に「緊張感が上昇する瞬間」と「睡眠に陥る瞬間」をずらしたいからであると思われます。もしこれらが同時に発生すると「ゼロになると同時に怖い瞬間が来る」場合の振る舞いを問題文に定義する必要があり、説明が面倒なのでしょう。コード上では整数として扱って問題ありません。

import java.util.Iterator;

public class TheMoviesLevelTwoDivTwo {
	public int[] find(int[] length, int[] scary) {
		int[] result = null;
		int movies = -1;
		for (int[] order : new Permutation(length.length)) {
			final int nextMovies = count(order, length, scary);
			if (nextMovies > movies || (nextMovies == movies && compare(result, order))) {
				result = order.clone();
				movies = nextMovies;
			}
		}

		return result;
	}

	private boolean compare(int[] result, int[] order) {
		for (int i = 0; i < result.length; ++i) {
			if (result[i] > order[i]) {
				return true;
			} else if (result[i] < order[i]) {
				return false;
			}
		}
		return false;
	}

	private int count(int[] order, int[] length, int[] scary) {
		int power = 74;
		int result = 0;
		for (int movie : order) {
			power -= scary[movie];
			if (power < 0) break;
			power += 47;
			power -= length[movie] - scary[movie];
			if (power < 0) break;
			
			++result;
		}
		return result;
	}

// 略:Permutation クラスの定義
}

2010-04-25

Member SRM468 Div2 Medium

| 16:22

http://www.topcoder.com/stat?c=problem_statement&pm=10762&rd=14183

T9という文字列変換プロトコルを実装し、引数から文字列を求めよ。』

import java.util.Arrays;

public class T9 {
	String[] cnvDict;

	public String message(String[] part, String[] dict, String[] keystr) {
		final StringBuilder mes = new StringBuilder();
		final StringBuilder word = new StringBuilder();

		Arrays.sort(dict);
		cnvDict = new String[dict.length];
		for (int i = 0; i < dict.length; ++i) {
			cnvDict[i] = convert(dict[i], part);
		}

		for (String input : keystr) {
			for (char c : input.toCharArray()) {
				if (c == '0') {
					mes.append(createWord(word, dict, part));
					mes.append(' ');
				} else {
					word.append(c);
				}
			}
		}
		mes.append(createWord(word, dict, part));
		
		return mes.toString();
	}

	private String convert(String string, String[] part) {
		final StringBuilder result = new StringBuilder();
		for (char c : string.toCharArray()) {
			for (int i = 0; i < part.length; ++i) {
				if (part[i].indexOf(c) >= 0) {
					result.append(Integer.toString(i + 1));
					break;
				}
			}
		}
		return result.toString();
	}

	private String createWord(StringBuilder wordBuf, String[] dict, String[] part) {
		String word = wordBuf.toString();
		if (word.length() == 0) return "";
		wordBuf.setLength(0);

		int count = 1;
		outer:
		for (int i = word.length() - 1; i >= 0; --i) {
			switch (word.charAt(i)) {
			case '#': ++count; break;
			case '*': count += 5; break;
			default: 
				word = word.substring(0, i + 1);
				break outer;
			}
		}

		for (int i = 0; i < cnvDict.length; ++i) {
			if (word.equals(cnvDict[i])) {
				--count;
				if (count == 0) {
					return dict[i];
				}
			}
		}

		throw new IllegalArgumentException();
	}
}

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

2010-03-21

SRM464 Div2 Medium(500pt.)

| 23:10

http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149

TLE解消せず。

import java.util.HashSet;
import java.util.Set;

public class ColorfulStrings {
	public String getKth(int n, int k) {
		if (n == 1) {
			return k > 10 ? "" : Integer.toString(k - 1);
		}
		if (n > 8 || k > f(8) / f(8 - n)) return "";

		int found = 0, end = endOf(n), i;
		for (i = beginOf(n); found < k && i < end; ++i) {
			if (isColorful(i)) ++found;
		}
		final String result = Integer.toString(i - 1);
		return result.length() == n ? result : "";
	}

	private int endOf(int n) {
		int result = 1;
		for (int i = 0; i < n; ++i) {
			result = result * 10;
		}
		return result + 1;
	}

	private int f(int i) {
		return i > 1 ? i * f(i - 1) : 1;
	}

	private int beginOf(int n) {
		if (n == 1) return 0;

		int result = 0;
		for (int i = 0; i < n; ++i) {
			result = result * 10 + (i + 1);
		}
		return result;
	}

	private boolean isColorful(int num) {
		final String asStr = Integer.toString(num);
		if (asStr.contains("0") || asStr.contains("1")) {
			return false;
		}
		final Set<Integer> products = new HashSet<Integer>();

		for (int start = 0; start < asStr.length(); ++start) {
			for (int end = start + 1; end <= asStr.length(); ++end) {
				if (!products.add(productOf(asStr, start, end))) return false;
			}
		}
		return true;
	}

	private Integer productOf(String string, int start, int end) {
		int answer = 1;
		for (int i = start; i < end; ++i) {
			answer *= string.charAt(i) - '0';//Character.digit(string.charAt(i), 10);
		}
		return Integer.valueOf(answer);
	}
}

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