Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-10SRM346 (Practice)

三日ぐらい前にやった。

500が難しい回。1000に逃げたのは正解だと思ったがWAを食らう。

問題結果ポイントその他
250CommonMultiplesAccepted236.48最小公倍数
500HeightRoundOpened0.00貪欲法
1000MeteoritesWA0.00幾何

SRM 346 CommonMultiples

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

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

  • やるだけ。
public class CommonMultiples {

	public long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a%b);
	}
	
	public long lcm(long a, long b) {
		long gcd = gcd(a, b);
		return (a / gcd) * b;
	}
	
	
	public int countCommMult(int[] a, int lower, int upper) {
		long lo = lower;
		long up = upper;
		
		long l = 1;
		for (int i = 0 ; i < a.length ;i++) {
			l = lcm(l, a[i]);
			if (l > up || l <= 0) {
				return 0;
			}
		}	
		return (int)((up / l) - ((lo - 1) / l));
	}
}

SRM 346 HeightRound

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

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

  • 貪欲法。難しい
    • editorialや他の人のコードを見ながら書いた。
    • 要復習
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HeightRound {
	public int[] getBestRound(int[] h) {
		int len = h.length;
		Arrays.sort(h);
		int[] ret = new int[len];
		ret[0] = h[0];
		for (int d = 0 ; d <= 1000 ; d++) {
			boolean isok = true;
			List<Integer> hv = new ArrayList<Integer>();
			for (int i = 1 ; i < len ; i++) {
				hv.add(h[i]);
			}
			int q = h.length - 1;
			while (q > 0) {
				int idx = hv.size() - 1;
				int prev = (q + 1 == ret.length) ? ret[0] : ret[q+1];
				while (idx >= 0) {
					if (Math.abs(hv.get(idx) - prev) <= d) {
						break;
					}
					idx--;
				}
				if (idx < 0) {
					isok = false;
					break;
				}
				ret[q] = hv.remove(idx);
				q--;
			}
			if (Math.abs(ret[1] - ret[0]) > d) {
				continue;
			}
			if (isok) {
				return ret;
			}
		}
		return ret;
	}
}

SRM 346 Meteorites

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

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

  • 各隕石ごとに他の隕石で覆われている部分をラジアンの区間で持つ。
    • 角度の計算はatan2を使うと場合分けしなくて済み楽。
  • 隕石が他の隕石に完全に含まれている場合に注意する
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Meteorites {

	class Seg implements Comparable<Seg> {
		double from;
		double to;
		Seg(double f, double t) {
			from = f;
			to = t;
		}
		public int compareTo(Seg arg0) {
			int c = Double.compare(from, arg0.from);
			if (c == 0) {
				return Double.compare(to, arg0.to);
			}
			return c;
		}
		public String toString() {
			return (from + "-" + to);
		}
	}
	
	public double perimeter(int[] x, int[] y, int[] r) {
		int len = x.length;
		double ret = 0.0d;
		for (int i = 0 ; i < len ; i++) {
			List<Seg> list = new ArrayList<Seg>();
			boolean insideof = false;
			for (int j = 0 ; j < len ; j++) {
				if (i == j) {
					continue;
				}
				long dx = x[i] - x[j];
				long dy = y[i] - y[j];
				long d2 = dx * dx + dy * dy;
				long dr1 = r[i] + r[j];
				long dr2 = r[i] - r[j];
				long lr1 = r[i];
				long lr2 = r[j];
				if (d2 <= dr2 * dr2 && r[i] < r[j]) {
					insideof = true;
					break;
				} else if (dr2 * dr2 < d2 && d2 < dr1 * dr1) {
					double radA = Math.atan2((y[j] - y[i]), (x[j] - x[i])) + Math.PI * 2;
					if (radA >= Math.PI * 2) {
						radA -= Math.PI * 2;
					}
					double radX = Math.acos((lr1 * lr1 + d2 - lr2 * lr2 * 1.0d) / (2.0d * lr1 * Math.sqrt(d2)));

					double from = radA - radX;
					double to = radA + radX;
					if (from < 0) {
						from += 2 * Math.PI;
					}
					if (to < 0) {
						to += 2 * Math.PI;
					}
					if (from > Math.PI * 2) {
						from -= 2 * Math.PI;
					}
					if (to > Math.PI * 2) {
						to -= 2 * Math.PI;
					}
					
					if (from < to) {
						list.add(new Seg(from, to));
					} else {
						list.add(new Seg(from, Math.PI * 2));
						list.add(new Seg(0, to));
					}
				}
			}
			
			if (!insideof) {
				double now = 0.0d;
				double earn = 0.0d;
				int l = list.size();
				Collections.sort(list);
				
				for (int j = 0 ; j < l ; j++) {
					Seg s = list.get(j);
					if (now < s.from) {
						earn += (s.from - now);
						now = s.to;
					} else if (now <= s.to) {
						now = s.to;
					}
				}
				earn += (2 * Math.PI - now);
				ret += earn * r[i];
			}
		}
		return ret;
	}
}