Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-01SRM355 (Practice)

全体的に難しい回。

問題結果ポイントその他
300MixingLiquidsWA0.00貪欲法
600TetrahedronOpened0.00幾何
900BeautifulHexagonalTilingsOpened0.00ブルートフォース

SRM 355 MixingLiquids

|  SRM 355 MixingLiquids - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 355 MixingLiquids - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7886

  • 一度すべての溶液を混ぜる。
    • 濃度がぴったりだったら、合計をそのまま返す。
    • 濃度が薄すぎたら、一番薄いものから減らしていく。
    • 濃度が濃すぎたら、一番濃いものから減らしていく。
import java.util.Arrays;
import java.util.Comparator;

public class MixingLiquids {
	class Cup {
		int pcnt;
		int amnt;
		Cup(int p, int a) {
			pcnt = p;
			amnt = a;
		}
	}
	
	public double howMuch(int[] percent, int[] amount, int need) {
		int len = percent.length;
		Cup[] cup = new Cup[len];
		int ttl = 0;
		int cnt = 0;
		for (int i = 0 ; i < len ; i++) {
			ttl += amount[i];
			cnt += amount[i] * percent[i];
			cup[i] = new Cup(percent[i], amount[i]);
		}
		Arrays.sort(cup, new Comparator<Cup>(){
			public int compare(Cup a, Cup b) {
				return a.pcnt - b.pcnt;
			}
		});
		
		int from = 0;
		int to = len - 1;
		while (from <= to) {
			int newttl = ttl, newcnt = cnt;
			if (cnt == ttl * need) {
				return ttl;
			} else if (cnt < ttl * need) {
				newttl -= cup[from].amnt;
				newcnt -= cup[from].amnt * cup[from].pcnt;
				if (newttl * need < newcnt) {
					return ttl - (double)(cnt - ttl * need) / (cup[from].pcnt - need);
				} else {
					from++;
					ttl = newttl;
					cnt = newcnt;
				}
			} else {
				newttl -= cup[to].amnt;
				newcnt -= cup[to].amnt * cup[to].pcnt;
				if (newttl * need > newcnt) {
					return ttl - (double)(cnt - ttl * need) / (cup[to].pcnt - need);
				} else {
					to--;
					ttl = newttl;
					cnt = newcnt;
				}				
			}
		}
		return 0.0d;
	}
}

SRM 355 Tetrahedron

|  SRM 355 Tetrahedron - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 355 Tetrahedron - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7539

  • 幾何。点をA, B, C, Dと置く
    • まずどれかの3点について、三角形が作れないなら "NO"
    • それ以外の場合、A(0, 0) B(dist[A][B], 0) として、C, Dの座標を求める
      • このとき余弦定理を使うと楽に求められる
    • CDの最小最大を求め、dist[C][D]と比べて検証する
public class Tetrahedron {
	double EPS = 1e-11;
	
	public String exists(String[] d) {
		int[][] dist = new int[4][4];
		for (int from = 0; from <= 3; from++) {
			String[] line = d[from].split(" ");
			for (int to = 0; to <= 3; to++) {
				dist[from][to] = Integer.valueOf(line[to]);
			}
		}
		for (int i = 0; i < 4; ++i) {
			for (int j = 0; j < 4; ++j) {
				for (int k = 0; k < 4; ++k) {
					if (dist[i][j] + dist[j][k] < dist[i][k]) {
						return "NO";
					}
				}
			}
		}

		double coscab = (double)(dist[0][1] * dist[0][1] + dist[0][2] * dist[0][2] - dist[1][2] * dist[1][2]) / (2.0d * dist[0][1] * dist[0][2]);
		double cx = dist[0][2] * coscab;
		double cy = Math.sqrt(dist[0][2] * dist[0][2] - cx * cx);
		
		double cosdab = (double)(dist[0][1] * dist[0][1] + dist[0][3] * dist[0][3] - dist[1][3] * dist[1][3]) / (2.0d * dist[0][1] * dist[0][3]);
		double dx = dist[0][3] * cosdab;
		double dy = Math.sqrt(dist[0][3] * dist[0][3] - dx * dx);

		if (Math.hypot(cx - dx, cy - dy) - EPS < dist[2][3] && Math.hypot(cx - dx, cy + dy) + EPS > dist[2][3]) {
			return "YES";
		}
		return "NO";
	}
}

SRM 355 BeautifulHexagonalTilings

|  SRM 355 BeautifulHexagonalTilings - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 355 BeautifulHexagonalTilings - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7761

  • editorial曰くバックトラックで解けるらしい
    • あとでやる