TopCoder SRM 502

Div2 Easy: TheProgrammingContestDivTwo

時間内に複数のタスクをこなさなければならない。順序は任意。一つのタスクをこなすと、そのタスクが終わった時点での経過時間がペナルティとして加算される。制限時間Tと各タスクの必要時間requiredTimeが与えられた時、こなせる最大のタスク数と累計のペナルティを答える。

import java.util.Arrays;

public class TheProgrammingContestDivTwo {

	public int[] find(int T, int[] requiredTime) {
		int solved = 0;
		int passed = 0;
		int t = 0;
		Arrays.sort(requiredTime);
		for (int i = 0; i < requiredTime.length; i++) {
			if (T < passed + requiredTime[i]) break;
			solved++;
			passed += requiredTime[i];
			t += passed;
		}
		int[] res = {solved, t};
		return res;
	}
	
}

テスト実行しながら何回か書き直しつつ正解。一発で書きたいなぁ。英語の問題文がぱっと頭に入ってこないのが問題。

Div2 Medium: TheLotteryBothDivs

くじを一枚持っている。くじは"000000000"から"999999999"までの10桁の数字からなる文字列で表されるとする。この時、1桁から10桁までの文字列（suffix）がいくつか与えられ、くじ番号の末尾にそのどれかが一致すれば当たりである。与えられた文字列配列から、当たりの確率を答える。ただし、浮動小数点演算による1e-9以下の誤差は許される。

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

class StringLengthComparator implements Comparator<String> {
	public int compare(String o1, String o2) {
		if (o1.length() < o2.length()) {
			return -1;
		} else if (o2.length() < o1.length()) {
			return 1;
		} else {
			return 0;
		}
	}
}

public class TheLotteryBothDivs {

	public double find(String[] goodSuffixes) {
		double res = 0.0;
		Set<String> set = new HashSet<String>();
		Arrays.sort(goodSuffixes, new StringLengthComparator());
		for (String suffix : goodSuffixes) {
			boolean ignore = false;
			for (int i = 1; i <= suffix.length(); i++) {
				String check = suffix.substring(suffix.length()-i, suffix.length());
				ignore = set.contains(check);
				if (ignore) break;
			}
			if (!ignore) {
				set.add(suffix);
				res += Math.pow(0.1, suffix.length());
			}
		}
		return res;
	}
	
}

例えば {"1", "2"} が渡されると当たりの確率は0.2。 {"01", "02"} であれば0.02。{"1", "2", "01", "02"} だったら、長いほうの文字列は確率に影響を与えないので0.2のまま。
文字列を短い順に並び替えて、憶えておく。前に共通のサフィックスを使う文字列が現れていたら、確率には加算しない。文字列の種類は最大でも50と少ないから、トライ木のようなデータ構造を使わなくても一文字ずつ削りながら処理していけばOK。
Javaで比較処理のもっと簡単な書き方ってないっけ。。

Div2 Hard: TheCowDivTwo

飼っている牛の数と逃げ出した牛の数が渡される。逃げ出した牛の組み合わせは何通りあるか、という問題。
組み合わせの定義を調べてやってみたがうまく動かず、時間切れ。やっぱり中学数学からやり直しが必要だな。。

結果

EasyとMediumの二問正解で491.79pt。Div2 758人中143位。レーティングは922から979にアップ。次で4桁になれれば初回挑戦以来だ！