TopCoder SRM 635 Div1 Easy: SimilarRatingGraph

解法

Nが400以下なので、N-1個の区間の長さと傾きを計算しておき、傾きが等しく、長さの倍率が等しい区間を出せば良い……がっ……ダメっ……！！誤差ゲーなので値が小さくなり過ぎないように気をつけなければならない。

コード

import java.util.ArrayList;
import java.util.Collections;

public class SimilarRatingGraph {

	public double maxLength(int[] date, int[] rating) {
		int N = date.length;
		ArrayList<Rate> rates = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			rates.add(new Rate(rating[i], date[i]));
		}
		Collections.sort(rates);

		for (int i = 0; i < N; i++) {
			rating[i] = rates.get(i).rate;
			date[i] = rates.get(i).date;
		}

		double[] length = new double[N - 1];
		double[] grad = new double[N - 1];
		for (int i = 1; i < N; i++) {
			int dr = rating[i] - rating[i - 1];
			int dd = date[i] - date[i - 1];
			length[i - 1] = Math.sqrt((long) dr * dr + (long) dd * dd);// 長さ
			grad[i - 1] = (double) dr / dd;// 傾き
		}

		double max = 0;
		for (int i = 0; i < N - 1; i++) {
			for (int j = i + 1; j < N - 1; j++) {
				if (!same(grad[i], grad[j])) {
					continue;
				}
				double p = length[i] / length[j];
				int cnt = 0;
				while (j + cnt < N - 1 && same(grad[i + cnt], grad[j + cnt])
						&& same(p * length[j + cnt], length[i + cnt])) {
					cnt++;
				}

				double lengthI = 0;
				double lengthJ = 0;
				for (int k = 0; k < cnt; k++) {
					lengthI += length[i + k];
					lengthJ += length[j + k];
				}
				max = Math.max(max, Math.max(lengthI, lengthJ));
			}
		}

		return max;
	}

	private boolean same(double a, double b) {
		final double EPS = 1e-9;
		if (a + EPS < b || a - EPS > b) {
			return false;
		}
		return true;
	}

	class Rate implements Comparable<Rate> {
		int rate, date;

		public Rate(int r, int d) {
			this.rate = r;
			this.date = d;
		}

		@Override
		public int compareTo(Rate o) {
			return this.date - o.date;
		}
	}

}