TopCoder SRM 501

Div2 Easy: FoxProgression（Java）

与えられた数列に追加すると、その数列が等差数列または等比数列になるような数は何種類あるか、という問題。
先頭に入れるのもありかと思って時間がかかったが、後ろにappendする場合だけを考慮すればいいらしい。

public class FoxProgression {
	public int theCount(int[] seq) {
		if (seq.length == 1) return -1;
		int last = 0;
		int[] diffs = new int[seq.length-1];
		double[] ratios = new double[seq.length-1];
		boolean ari = true;
		boolean geo = true;
		for (int i = 1; i < seq.length; i++) {
			diffs[i-1] = seq[i] - seq[i-1];
			ratios[i-1] = (double)seq[i] / seq[i-1];
			if (seq[i-1] * (int)ratios[i-1] != seq[i]) geo = false;
			last = seq[i];
		}
		for (int i = 1; i < diffs.length; i++) {
			if (diffs[i] != diffs[i-1]) ari = false;
		}
		for (int i = 1; i < ratios.length; i++) {
			if (ratios[i] != ratios[i-1]) geo = false;
		}
		if (!ari && !geo) return 0;
		if (ari && geo) {
			if (last + diffs[0] == last * ratios[0]) {
				return 1;
			} else {
				return 2;
			}
		}
		return 1;
	}
}

Div2 Medium: FoxPlayingGame（Java）

スコア0から始めて、任意の順序でparamA / 1000.0をnA回足し、paramB / 1000.0をnB回かけることができる。最大スコアは何点か。

最初の回答。いくつかのパターンを挙げてつぶしていく。。

public class FoxPlayingGame {
	public double theMax(int nA, int nB, int paramA, int paramB) {
		double scoreA = paramA / 1000.0;
		double scoreB = paramB / 1000.0;
		double ret = Math.max(
			0 + (scoreA * nA) * Math.pow(scoreB, nB),
			0 * Math.pow(scoreB, nB) + (scoreA * nA));
		if (scoreB < 0) {
			if (nB % 2 == 0) {
				return Math.max(ret, 
						0 + (scoreA * nA) * Math.pow(scoreB, nB));
			} else {
				return Math.max(ret, 
						0 * scoreB + (scoreA * nA) * Math.pow(scoreB, nB-1));
			}
		}
		return ret;
	}
}

あっさりと他の参加者に撃墜される。こういう方法ではだめですね。

後日の復習で、他の人のコードを見て書き直し。
つまるところ、 (paramA / 1000.0) * nA に、nB回以下で任意の回数 (paramB / 1000.0) をかけて、最大値をとれば良い。

public class FoxPlayingGame {
	public double theMax(int nA, int nB, int paramA, int paramB) {
		double scoreA = paramA / 1000.0;
		double scoreB = paramB / 1000.0;
		double ret = scoreA * nA;
		for (int i = 0; i <= nB; i++) {
			ret = Math.max(ret, (scoreA * nA) * Math.pow(scoreB, i));
		}
		return ret;
	}
}

二つ二次元配列を用意して動的計画法らしく更新していくやり方の人もいるので、そっちも後で確認。

結果

Hard問題には手が出ず。レーティングは912から922に微増。