Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-29SRM357 (Practice)

問題結果ポイントその他
250HotelAccepted248.42DP
500WebsiteRankWA0.00グラフ
1100ChipAreaOpened0.00幾何

SRM 357 Hotel

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

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

  • 制約見てDPだと思った
  • 速度勝負だと思ったのでEgor風に提出してからデバッグを敢行した
import java.util.Arrays;

public class Hotel {

	public int marketCost(int minCustomers, int[] customers, int[] cost) {
		int[] dp = new int[5000];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		int len = customers.length;
		for (int i = 0 ; i < 5000 ; i++) {
			if (dp[i] != Integer.MAX_VALUE) {
				for (int j = 0 ; j < len ; j++) {
					int ti = i + customers[j];
					if (ti < 5000) {
						dp[ti] = Math.min(dp[ti], dp[i] + cost[j]);
					}
				}
			}
		}
		
		int res = Integer.MAX_VALUE;
		for (int i = minCustomers ; i < 5000 ; i++) {
			res = Math.min(res, dp[i]);
		}
		return res;
	}
}

SRM 357 WebsiteRank

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

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

  • めちゃくちゃ簡単なのに解けなかった、(自分に対して)訴訟
    • 素直に実装するだけ
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class WebsiteRank {

	boolean[][] graph, link;
	int len;
	
	public long countVotes(String[] votes, String website) {
		Map<String, Integer> namemap = new HashMap<String, Integer>();
		for (String v : votes) {
			String[] data = v.split(" ");
			int l = data.length;
			for (int i = 0 ; i < l ; i++) {
				if (!namemap.containsKey(data[i])) {
					namemap.put(data[i], namemap.size());
				}
			}
		}
		
		len = namemap.size();
		graph = new boolean[len][len];
		link = new boolean[len][len];
		for (String v : votes) {
			String[] data = v.split(" ");
			int l = data.length;
			int toid = namemap.get(data[0]);
			for (int i = 1 ; i < l ; i++) {
				int fromid = namemap.get(data[i]);
				graph[fromid][toid] = true;
				link[fromid][toid] = true;
			}
		}
		
		for (int k = 0 ; k < len ; k++) {
			for (int i = 0 ; i < len ; i++) {
				for (int j = 0 ; j < len ; j++) {
					if (graph[i][k] && graph[k][j]) {
						graph[i][j] = true;
					}
				}
			}
		}
		
		int[] indeg = new int[len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (link[i][j] && graph[j][i]) {
					link[i][j] = false;
				}
			}
		}

		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (link[i][j]) {
					indeg[j]++;
				}
			}
		}
		
		long[] val = new long[len];
		Arrays.fill(val, 1);
		
		while (true) {
			boolean done = false;
			for (int i = 0 ; i < len ; i++) {
				if (indeg[i] == 0) {
					for (int j = 0 ; j < len ; j++) {
						if (link[i][j]) {
							done = true;
							link[i][j] = false;
							indeg[j]--;
							val[j] += val[i];
						}
					}
				}
			}
			if (!done) {
				break;
			}
		}
		return val[namemap.get(website)];
	}
}

SRM 357 ChipArea

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

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

  • 頑張れば解けそう。
    • もうちょい考える
  • できた。
    • x座標の昇順にソートする
    • 各点を長方形の左端に置くことを考え、とりうるyの最小値と最大値を更新しながら見ていく。
      • そのままやると間に合わないけど点がランダムに分布するので枝刈りを仕込んでやると間に合った。やったー
import java.util.Arrays;

public class ChipArea {

	final static int MUL = 111;
	final static long MOD = 323537;
	
	class Pt implements Comparable<Pt> {
		long x, y;
		double dx, dy;
		Pt(long _x, long _y) {
			x = _x;
			y = _y;
			dx = (double) x / MOD;
			dy = (double) y / MOD;
		}
		public int compareTo(Pt o) {
			if (x != o.x) {
				return Long.signum(x - o.x);
			}
			return Long.signum(y - o.y);
		}
	}
	
	
	public boolean isin(Pt p, double fx, double tx, double fy, double ty) {
		if (fx < p.dx && p.dx < tx) {
			if (fy < p.dy && p.dy < ty) {
				return true;
			}
		}
		return false;
	}
	
	public double maxArea(int skip, int n) {
		Pt[] pts = new Pt[n+2];
		long now = 1;
		for (int i = 0 ; i < skip ; i++) {
			now = now * MUL % MOD;
		}
		for (int i = 0 ; i < n ; i++) {
			now = now * MUL % MOD;
			long x = now;
			now = now * MUL % MOD;
			long y = now;
			Pt pt = new Pt(x, y);
			pts[i] = pt;
		}
		pts[n] = new Pt(0, MOD / 2);
		pts[n+1] = new Pt(MOD, MOD / 2);
		Arrays.sort(pts);
		n += 2;
		
		long max = 0;
		for (int i = 0 ; i < n ; i++) {
			long from = pts[i].x;
			long basey = pts[i].y;
			long maxy = MOD;
			long miny = 0;
			long val = 0;
			
			boolean once = false;
			for (int j = i + 1 ; j < n ; j++) {
				max = Math.max(max, (maxy - miny) * (pts[j].x - from));
				if (basey > pts[j].y) {
					miny = Math.max(miny, pts[j].y);
				} else if (basey < pts[j].y) {
					maxy = Math.min(maxy, pts[j].y);
				} else {
					break;
				}
				if ((MOD - from) * (maxy - miny) <= max) {
					break;
				}
			}
		}
		return (double)max / MOD / MOD;
	}
}