Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-16SRM373 (Practice)

通せるはずの500を落としてしまった 167/377位

問題結果ポイントその他
250StringFragmentationAccepted187.10二分探索
500RoadCrossingWA0.00ギリギリを考えよ
1000SpiralConstructionOpened0.00幾何+DP

SRM 373 StringFragmentation

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

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

  • 文字を小さくすればフレームに収まらないということはないはず
    • 二分探索しよう
public class StringFragmentation {
	public boolean ispossible(String[] words, int width, int height, int size) {
		int maxline = height / (2 * size);
		int from = 0 ;
		int len = words.length;
		int maxletters = width / (size+2);
		for (int i = 0 ; i < maxline ; i++) {
			int letters = 0;
			while (letters < maxletters && from < len) {
				if (letters == 0) {
					letters += words[from].length();  
				} else {
					letters += 1 + words[from].length();
				}
				from++;
			}
			if (letters > maxletters) {
				from--;
			}
		}
		return (from == len);
	}
	
	public int largestFontSize(String text, int width, int height) {
		String[] words = text.split(" ");
		int min = 7;
		int max = 100000000;
		for (int cur = 0 ; cur < 100 ; cur++) {
			int mid = (min + max) / 2;
			if (ispossible(words, width, height, mid)) {
				min = mid;
			} else {
				max = mid;
			}
		}
		return (min <= 7) ? -1 : min;
	}
}

SRM 373 RoadCrossing

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

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

  • こういう問題のコツはギリギリの状況を考えること
    • 車が通れるか通れないかは特定の時間だけ調べればOK
    • 歩行者のペアについて、距離がちょうど車のサイズになった時間を全て列挙する
    • あと念のため、車が到着した時間、各歩行者についても候補に追加する
  • サンプル通った。提出
  • なぜかWA。方針はあってるはずだが・・・
    • 時間を求める計算式が間違っていた・・・
      • こういうのは頭の中で考えずちゃんと紙に書いて定式化すべき
    • 何故サンプルが通ったのか
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class RoadCrossing {

	public double EPS = 0.00000000001;
			
	public class Walker {
		double from;
		double speed;
		int fi, si;

		Walker(int t, int s) {
			from = t;
			speed = s;
			fi = t;
			si = s;
		}
	}

	public double passTime(String[] pedestrians, int roadWidth, int carWidth,
			int carArrival) {
		int len = pedestrians.length;
		Walker[] w = new Walker[len];
		for (int i = 0; i < len; i++) {
			String[] data = pedestrians[i].split(" ");
			w[i] = new Walker(Integer.valueOf(data[0]),
					Integer.valueOf(data[1]));
		}

		List<Double> candidates = new ArrayList<Double>();
		for (int i = 0; i < len; i++) {
			candidates.add(w[i].from);
			candidates.add(w[i].from + (roadWidth - carWidth) / w[i].speed);
			candidates.add(w[i].from + (carWidth) / w[i].speed);
			candidates.add(w[i].from + roadWidth / w[i].speed);
		}

		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (w[i].si == w[j].si) {
				} else {
					double d = w[i].from*w[i].speed - w[j].from*w[j].speed;
					double time1 = (d - carWidth) / (w[i].speed - w[j].speed);
					double time2 = (d + carWidth) / (w[i].speed - w[j].speed);
					candidates.add(time1);
					candidates.add(time2);
				}
			}
		}
		candidates.add(carArrival * 1.0d);

		double ptime = Double.MAX_VALUE;
		for (int i = 0; i < candidates.size(); i++) {
			double time = candidates.get(i);
			if (time < carArrival) {
				continue;
			}
			List<Double> positions = new ArrayList<Double>();
			for (int j = 0; j < len; j++) {
				if (time >= w[j].fi) {
					double pos = w[j].speed * (time - w[j].from);
					if (0 < pos && pos < roadWidth) {
						positions.add(pos);
					}
				}
			}
			Collections.sort(positions);
			if (positions.size() == 0) {
				ptime = Math.min(ptime, time);
			} else {
				positions.add(0.0d);
				positions.add(roadWidth * 1.0d);
				Collections.sort(positions);
				for (int j = 0; j < positions.size() - 1; j++) {
					double d = positions.get(j + 1) - positions.get(j);
					if (d + EPS > carWidth) {
						ptime = Math.min(ptime, time);
						break;
					}
				}
			}
		}
		return ptime;
	}
}

SRM 373 SpiralConstruction

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

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

  • 点の数が少ないからbitDPするんだろう
    • 状態は dp[使った点の組み合わせ][前回使った点][前々回使った点] でよいはず
      • 2^15*15*15 ≒ 7M
    • 線分が交差するか調べなければならないが、どう書くんだろう
      • 使った点の組み合わせだけでは直線は再現できないはず
    • あらかじめ4点のペアについて2線分が交差するかどうか前計算しておけばいい?

その後

  • editorial見て通した。
import java.util.Arrays;

public class SpiralConstruction {

	int[][] p;
	int[][][] memo;
	int len;
	
	public boolean convex(int pt, int last, int to) {
		int ax = p[last][0] - p[pt][0];
		int ay = p[last][1] - p[pt][1];
		int bx = p[to][0] - p[last][0];
		int by = p[to][1] - p[last][1];
		int cross = ax*by - ay*bx;
		int dot = ax*bx + ay*by;
		if (cross != 0) {
			return (cross > 0);
		}
		return dot >= 0;
	}
	
	public int dfs(int ptn, int prev, int prev2) {
		if (memo[ptn][prev][prev2] >= 0) {
			return memo[ptn][prev][prev2];
		}
		int ans = 0;
		for (int i = 0 ; i < len ; i++) {
			if ((ptn & (1<<i)) == 0) {
				int nptn = ptn | (1<<i);
				boolean isok = true;
				for (int j = 0 ; j < len+1 ; j++) {
					if (j == len || (ptn & (1<<j)) >= 1) {
						if (!convex(j, prev, i)) {
							isok = false;
							break;
						}
					}
				}
				if (isok) {
					ans = Math.max(ans, dfs(nptn, i, prev) + 1);
				}
			}
		}
		memo[ptn][prev][prev2] = ans;
		
		return ans;
	}
	
	
	public int longestSpiral(String[] points) {
		len = points.length;
		memo = new int[1<<len][len+1][len+1];
		for (int i = 0 ; i < 1<<len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				Arrays.fill(memo[i][j], -1);
			}
		}
		
		p = new int[len+1][2];
		for (int i = 0 ; i < len ; i++) {
			String[] data = points[i].split(" ");
			p[i][0] = Integer.valueOf(data[0]);
			p[i][1] = Integer.valueOf(data[1]);
		}
		p[len][0] = 0;
		p[len][1] = 0;
		
		int ans = 0;
		for (int i = 0 ; i < len ; i++) {
			ans = Math.max(ans, dfs(1<<i, i, len) + 1);
		}
		return ans;
	}

}