Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-20SRM368, SRM369 (Practice)

SRM368 (Practice)

SRM368 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM368 (Practice) - hama_DU@TopCoderへの道

2連続0完 するめ直前なのに・・・

問題結果ポイントその他
250JumpingBoardTLE0.00再帰
500PolylineUnionWA0.00幾何+ブルートフォース
1000BinaryCodesOpened0.00グラフ?

SRM 368 JumpingBoard

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

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

  • 方針を検討
    • ダイクストラっぽいことをすればいいよね
    • 同じ所に戻ってきたら-1で
  • いやまて、それじゃダメだ
    • ある場所に到達するのに2つ以上の経路があると詰む
  • 別の方法を考える
    • 幅優先で書いて単純にステップ数が上限(2500ぐらい)を超えたら-1でいいのでは
  • サンプル通ったので出した
    • TLEした
    • ちゃんとメモ化再帰で書かないとダメでした
  • 計算量の見積もりが甘かった・・・
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class JumpingBoard {

	class State {
		int h, w;
		int step = 0;
		State(int i, int j, int s) {
			h = i;
			w = j;
			step = s;
		}
	}
	
	int[] dx = {1, 0, -1, 0};
	int[] dy = {0, 1, 0, -1};
	int[][] done;
	int INF = 1000000;
	String[] board;
	int h, w;
	
	public int dfs(int r, int c) {
		if (r < 0 || c < 0 || c >= w || r >= h) {
			return 0;
		}
		if (done[r][c] >= 0) {
			return done[r][c];
		}
		if (board[r].charAt(c) == 'H') {
			return 0;
		}
		
		done[r][c] = INF;
		int ch = board[r].charAt(c) - '0';
		int max = 0;
		for (int d = 0 ; d < 4 ; d++) {
			int ty = r + dy[d] * ch;
			int tx = c + dx[d] * ch;
			max = Math.max(max, dfs(ty, tx) + 1);
		}
		done[r][c] = max;
		return max;
	}
	
	public int maxJumps(String[] b) {
		board = b;
		h = board.length;
		w = board[0].length();
		done = new int[h][w];
		for (int i = 0 ; i < h ; i++) {
			Arrays.fill(done[i], -1);
		}
		
		int c = dfs(0, 0);
		return (c > 1000000) ? - 1: c;
	}
}

SRM 368 PolylineUnion

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

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

  • 幾何ゲーから逃げない。
    • 点と点が一致するか
      • 単純に全部調べる
    • 点が線分のどこかと一致するか
      • 内積が0以上かつ外積が0かどうか調べる
    • 線分と線分が交差するか
      • 線分交差判定を書く。
      • 2点がもう一方の線分それぞれのどちら側かを外積を使って判定x2 両方共逆側になってたら交差してる
  • サンプル通った。
    • 交差判定とかintで書いちゃったけど大丈夫かな・・・
    • 条件を見ると (座標) <= 10000 みたいなこと書いてある。
      • 最大で(座標^2) <= 100,000,000 だからintでも大丈夫だろう
    • ある折れ線とある折れ線が交差したかどうかはUnionFindで管理
  • 出した。
    • WA食らう
    • よく見ると、線分の交差判定で (外積) * (外積) < 0 という計算をしてる。
      • それじゃintだとダメだよ・・・
        • (座標) ^ 4 になるので
      • longに直したら通った
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class PolylineUnion {

	class UnionFind {
		int[] parent, rank;
		UnionFind(int n) {
			parent = new int[n];
			rank = new int[n];
			for (int i = 0 ; i < n ; i++) {
				parent[i] = i;
				rank[i] = 0;
			}
		}
		
		int find(int x) {
			if (parent[x] == x) {
				return x;
			}
			parent[x] = find(parent[x]);
			return parent[x];
		}
		
		void unite(int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y) {
				return;
			}
			if (rank[x] < rank[y]) {
				parent[x] = y;
			} else {
				parent[y] = x;
				if (rank[x] == rank[y]) {
					rank[x]++;
				}
			}
		}
		boolean issame(int x, int y) {
			return (find(x) == find(y));
		}
	}
	
	public boolean intersects(long qx, long qy, long ax, long ay, long bx, long by) {
		long dx1 = (qx - ax);
		long dy1 = (qy - ay);
		long dx2 = (bx - qx);
		long dy2 = (by - qy);
		long dot = dx1 * dx2 + dy1 * dy2;
		if (dot >= 0) {
			if (dx1 * dy2 - dx2 * dy1 == 0) {
				return true;
			}
		}
		return false;
	}

	
	public boolean intersectsD(long ax, long ay, long bx, long by, long cx, long cy, long dx, long dy) {
		long lx = bx - ax;
		long ly = by - ay;
		long px = cx - ax;
		long py = cy - ay;
		long qx = dx - ax;
		long qy = dy - ay;
		long crossA = lx * py - ly * px;
		long crossB = lx * qy - ly * qx;
		if (crossA * crossB < 0) {
			return true;
		}
		return false;
	}
	
	public boolean intersects(long ax, long ay, long bx, long by, long cx, long cy, long dx, long dy) {
		return (intersectsD(ax, ay, bx, by, cx, cy, dx, dy) && intersectsD(cx, cy, dx, dy, ax, ay, bx, by));
	}
	public int countComponents(String[] polylines) {
		String line = "";
		for (String p : polylines) {
			line += p;
		}
		String[] lines = line.split(" ");
		int len = lines.length;
		UnionFind uf = new UnionFind(len);
		int[][] px = new int[len][];
		int[][] py = new int[len][];
		for (int i = 0 ; i < len ; i++) {
			String[] polys = lines[i].split("-");
			int pl = polys.length;
			px[i] = new int[pl];
			py[i] = new int[pl];
			for (int p = 0 ; p < pl ; p++) {
				String[] pt = polys[p].split(",");
				px[i][p] = Integer.valueOf(pt[0]);
				py[i][p] = Integer.valueOf(pt[1]);
			}
		}
		
		for (int i = 0 ; i < len ; i++) {
			for (int j = i + 1 ; j < len ; j++) {
				int al = px[i].length;
				int bl = px[j].length;
				boolean intersects = false;
				points: for (int a = 0 ; a < al ; a++) {
					for (int b = 0 ; b < bl ; b++) {
						if (px[i][a] == px[j][b] && py[i][a] == py[j][b]) {
							intersects = true;
							break points;
						}
					}
				}
				if (!intersects) {
					pointline:
					{
						for (int a = 0 ; a < al ; a++) {
							for (int b = 0 ; b < bl - 1 ; b++) {
								if (intersects(px[i][a], py[i][a], px[j][b], py[j][b], px[j][b+1], py[j][b+1])) {
									intersects = true;
									break pointline;
								}
							}
						}
						for (int b = 0 ; b < bl ; b++) {
							for (int a = 0 ; a < al - 1 ; a++) {
								if (intersects(px[j][b], py[j][b], px[i][a], py[i][a], px[i][a+1], py[i][a+1])) {
									intersects = true;
									break pointline;
								}
							}
						}
					}
				}
				if (!intersects) {
					lineline: for (int a = 0 ; a < al - 1 ; a++) {
						for (int b = 0 ; b < bl - 1 ; b++) {
							if (intersects(px[i][a], py[i][a], px[i][a+1], py[i][a+1], px[j][b], py[j][b], px[j][b+1], py[j][b+1])) {
								intersects = true;
								break lineline;
							}
						}
					}
				}
				if (intersects) {
					uf.unite(i, j);
				}
 			}
		}
		
		int cnt = 0;
		boolean[] done = new boolean[len];
		for (int i = 0 ; i < len ; i++) {
			if (done[i]) {
				continue;
			}
			done[i] = true;
			for (int j = 0 ; i < len ; i++) {
				if (uf.issame(i, j)) {
					done[j] = true;
				}
			}
			cnt++;
		}
		Set<Integer> gset = new HashSet<Integer>();
		for (int i = 0 ; i < len ; i++) {
			gset.add(uf.parent[i]);
		}	
		return gset.size();
	}
}

SRM369 (Practice)

SRM369 (Practice) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM369 (Practice) - hama_DU@TopCoderへの道

1000 > 250 > 500 だが0完 310/584位

全体的に難しい回だったらしい。500は通したかったなー

問題結果ポイントその他
250BeautifulStringOpened0.00貪欲法
500AbsSequenceWA0.00シミュレーション
1000MountainMapOpened0.00グラフ?

SRM 369 BeautifulString

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

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

  • これはダメだ、分からん
    • 適当にやるだけっぽいが明らかにサンプルが弱い
    • 先に500を見よう
public class BeautifulString {
	public int maximumLength(int countA, int countB, int maxA, int maxB) {
		if (maxA == 0 && maxB == 0) {
			return 0;
		}
		if (maxA == 0) {
			return Math.min(countB, maxB);
		}
		if (maxB == 0) {
			return Math.min(countA, maxA);
		}
		
		int max = -1;
		int aparts = (countA + maxA - 1) / maxA;
		if (countB < aparts - 1) {
			return countB + (countB + 1) * maxA;
		}

		int bparts = (countB + maxB - 1) / maxB;
		if (countA < bparts - 1) {
			return countA + (countA + 1) * maxB;
		}
		return countA + countB;
	}
}

SRM 369 AbsSequence

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

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


  • 方針を検討
    • 少し実験してみると、3つ組で考えたとき規則性があることに気づく
    • コーナーケースに注意してシミュレーションする
  • (a, b, c) で aが最大かつcが最小になるまで回す
    • min(a, b) / (c * 2) で規則が変わる瞬間が分かる
    • (min(a, b) / (c * 2)) * 3 が回すターン数を超えていたらその周期の中に答えはある
import java.util.ArrayList;
import java.util.List;

public class AbsSequence {
	
	public class Stat {
		long turn;
		long a, b;
		Stat(long t, long x, long y) {
			turn = t;
			a = x;
			b = y;
		}
	}
	
	public void processOne(long[] a) {
		long n = Math.abs(a[1] - a[2]);
		a[0] = a[1];
		a[1] = a[2];
		a[2] = n;
	}
	

	public String[] getElements(String first, String second, String[] indices) {
		
		long a0 = Long.valueOf(first);
		long a1 = Long.valueOf(second);
		
		long[] f3 = new long[]{a0, a1, Math.abs(a0 - a1)};
		int len = indices.length;
		String[] ans = new String[len];
		for (int i = 0 ; i < len ; i++) {
			ans[i] = "";
			long wanttoknow = Long.valueOf(indices[i]);
			
			long[] g3 = f3.clone();
			
			
			long res = -1;
			while (wanttoknow >= 3) {
				long min = Math.min(g3[0], Math.min(g3[1], g3[2]));
				long max = Math.max(g3[0], Math.max(g3[1], g3[2]));
				if (min == g3[2] && max == g3[0]) {
					if (min == 0) {
						if (wanttoknow % 3 == 2) {
							res = 0;
						} else {
							res = g3[1];
						}
						break;
					} else {
						long secondmin = Math.min(g3[1], g3[0]);
						long canrep = Math.min(secondmin / (min * 2), wanttoknow / 3);
						if (canrep >= 1) {
							long willproc = canrep * 3;
							wanttoknow -= willproc;
							g3[0] -= min * 2 * canrep;
							g3[1] -= min * 2 * canrep;
						} else {
							processOne(g3);
							wanttoknow--;
						}
					}
				} else {
					processOne(g3);
					wanttoknow--;
				}
			}
			if (res == -1) {
				ans[i] = String.valueOf(g3[(int)wanttoknow]);
			} else {
				ans[i] = String.valueOf(res);
			}
		}
		return ans;
	}
}