Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-27SRM300台を練習していく part2

SRM 303 Knights

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

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

ナイトの駒の関係はグラフに帰着できる。

さらに、ナイトの動き方の制約上、駒は大きく分けて二種類に分類でき、

同じ種類の駒が関係を結ぶことはない。

(こういう特別なグラフを「2部グラフ」というらしい)

問題は、グラフのノードを取り除いて、関係(リンク)の無いグラフを作るとき、

取り除く必要のある最小のノード数を求める、というもの。

そして、この問題はどうやら「2部グラフの最大マッチング問題」というものに帰着できるらしい。

確か蟻本に載っていたような気がするので、あとで調べる。

SRM 304 Conditional

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

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

条件付き確率。分母はメモ化再帰で求められる。

メモ化再帰の際、探索中に既に条件

「値がvのサイコロを少なくともひとつは使う」

を満たしたかを示すフラグ isok を用意する。


public class Conditional {

	public double[][][] memo;

	public int _side;

	public int _v;

	public double search(int n, int v, boolean isok) {
		if (v <= 0) {
			if (isok) {
				return 1.0d;
			} else if (n >= 1) {
				double a = 1.0d;
				for (int i = 0 ; i < n ; i++) {
					a *= (double)(_side - 1) / _side;
				}
				return 1.0d - a;
			} else {
				return 0.0d;
			}
		}
		if (n == 0) {
			return 0.0d;
 		}
		double prob = 0.0d;
		int is = isok ?  1 : 0;
		if (memo[n][v][is] >= 0) {
			return memo[n][v][is];
		}
		for (int i = 1 ; i <= _side ; i++) {
			boolean next = (i == _v) || isok;
			prob += search(n-1, v-i, next) / _side;
		}
		memo[n][v][is] = prob;
		return prob;
	}

	public double probability(int nDice, int maxSide, int v, int theSum) {
		memo = new double[nDice+1][theSum+1][2];
		for (int i = 0 ; i <= nDice ; i++) {
			for (int j = 0 ; j <= theSum ; j++) {
				memo[i][j][0] = -1.0d;
				memo[i][j][1] = -1.0d;
			}
		}
		_side = maxSide;
		_v = v;
		double a = search(nDice, theSum, false);
		double b = 1.0d;
		if (maxSide > 1) {
			for (int i = 0 ; i < nDice ; i++) {
				b *= (double)(maxSide - 1) / maxSide;
			}
		} else {
			b = 0.0d;
		}
		System.out.println(a);
		System.out.println(1.0d - b);
		return a / (1.0d - b);
	}

}


SRM 304 PolyMove

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

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

自力では解けなかった。

各頂点を1だけ引き伸ばすことによる面積の増加分を全て求める。

隣り合う頂点を使うことはできないので、DPをする。更新式は以下のとおり。

dp[i] = max(dp[i-2] + i番目の頂点を伸ばすことによる増加分, dp[i-1])

注意しなければならないのは、最初の頂点と最後の頂点が隣り合っているため、

最初の頂点を使う場合と使わない場合とで二パターンのDPをする必要があること。


public class PolyMove {

	double[] inc;

	public double L(int x1, int y1, int x2, int y2) {
		return Math.hypot(Math.abs(x1 - x2),  Math.abs(y1 - y2));
	}

	public double addedArea(int[] x, int[] y) {
		int len = x.length;
		inc = new double[len];
		for (int i = 0 ; i < len ; i++) {
			int ida = ((i + len) - 1) % len;
			int idb = (i + len + 1) % len;
			inc[i] = L(x[ida], y[ida], x[idb], y[idb]);
		}

		double[] dp = new double[len];
		double[] dpx = new double[len];
		dp[0] = inc[0];
		dp[1] = Math.max(inc[0], inc[1]);
		dpx[0] = 0;
		dpx[1] = inc[1];
		for (int i = 2 ; i < len ; i++) {
			if (i == len - 1) {
				dpx[i] = Math.max(dpx[i-2] + inc[i], dpx[i-1]);
			} else {
				dp[i] = Math.max(dp[i-2] + inc[i], dp[i-1]);
				dpx[i] = Math.max(dpx[i-2] + inc[i], dpx[i-1]);
			}
		}

		return Math.max(dp[len-2], dpx[len-1]) / 2.0d;
	}

}


SRM 303 SpiralNumbers

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

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

やるだけ!


public class SpiralNumbers {

	public int[] dx = {-1, 0, 1, 0};
	public int[] dy = {0, 1, 0, -1};

	public String getPosition(int N) {
		long n = N;
		if (N == 1) {
			return "(" + 0 + "," + 0 + ")";
		}
		int a = 0;
		for (long i = 1 ; i <= 1000000 ; i += 2) {
			if (n <= i * i) {
				long proc = i * i - n;
				System.out.println(i);
				int sx = a;
				int sy = -a;
				for (int d = 0 ; d < 4 ; d++) {
					for (int b = 0 ; b < 2 * a ; b++) {
						if (proc == 0) {
							return "(" + sy + "," + sx + ")";
						}
						sx += dx[d];
						sy += dy[d];
						proc--;
					}
				}

				break;
			}
			a++;
		}
		return null;
	}

}




SRM 305 UnfairDivision

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

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

各人のassetsの分け方の全パターンを列挙する。


public class UnfairDivision {

	public int albertsShare(int[] assets) {
		int len = assets.length;
		int max_al = 0;
		for (int i = 1 ; i < len ; i++) {
			int al = 9999999;
			int bet = 0;
			for (int j = 1 ; j < len ; j++) {
				if (i == j) {
					continue;
				}
				int a = Math.min(i, j);
				int b = Math.max(i, j);
				int sa = 0, sb = 0, sc = 0;
				for (int x = 0 ; x < a ; x++) {
					sa += assets[x];
				}
				for (int x = a ; x < b ; x++) {
					sb += assets[x];
				}
				for (int x = b ; x < len ; x++) {
					sc += assets[x];
				}
				int max = Math.max(sa, Math.max(sb, sc));
				int min = Math.min(sa, Math.min(sb, sc));
				int mid = sa + sb + sc - max - min;
				if (bet < mid) {
					al = min;
					bet = mid;
				} else if (bet == mid){
					al = Math.min(al, min);
				}
			}
			if (max_al < al) {
				max_al = al;
			}
		}
		return max_al;
	}

}