Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-30SRM300台を練習していく part6

SRM 311 SumThemAll

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

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

(mediumにしては)簡単。

digitsの合計を表すテーブルを1000000まで持っておき、

lowerBoundとupperBoundを1000000で割った商と余りに分けてそれぞれ計算する。


public class SumThemAll {

	public long getSum(int lowerBound, int upperBound) {
		long[] dp = new long[1000001];
		long[] basesum = new long[1000001];
		for (int i = 1 ; i <= 9 ; i++) {
			dp[i] = i;
		}
		for (int i = 10 ; i <= 99 ; i++) {
			dp[i] = dp[i/10] + dp[i%10];
		}
		for (int i = 100 ; i <= 9999 ; i++) {
			dp[i] = dp[i/100] + dp[i%100];
		}
		for (int i = 10000 ; i <= 1000000 ; i++) {
			dp[i] = dp[i/10000] + dp[i%10000];
		}
		for (int i = 1 ; i <= 1000000 ; i++ ) {
			basesum[i] = basesum[i-1] + dp[i];
		}


		long ans = 0;
		if (upperBound <= 1000000) {
			return basesum[upperBound] - ((lowerBound == 0) ? 0 : basesum[lowerBound-1]);
		}

		long meta_a = lowerBound / 1000000;
		long meta_b = upperBound / 1000000;
		if (meta_a < meta_b) {
			long tmp_a = 0;
			if (lowerBound % 1000000 == 0) {
				tmp_a = basesum[999999];
			} else {
				tmp_a = basesum[999999] - basesum[lowerBound % 1000000 - 1];
			}
			ans += tmp_a + dp[(int)meta_a] * (1000000 - lowerBound % 1000000);

			for (long i = meta_a + 1 ; i < meta_b ; i++) {
				ans += basesum[999999] + dp[(int)i] * 1000000;
			}
			long tmp_b = basesum[upperBound % 1000000];
			ans += tmp_b + dp[(int)meta_b] * (upperBound % 1000000 + 1);
		} else {
			ans += dp[(int)meta_a] * (upperBound % 1000000 - lowerBound % 1000000 + 1);
			ans += basesum[upperBound % 1000000];
			if (lowerBound % 1000000 != 0) {
				ans -= basesum[lowerBound % 1000000 - 1];
			}
		}
		return ans;
	}
}




SRM 311 MatrixTransforming

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

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

3x3のマスをflipする操作を繰り返す。最小何回で目的のパターンが作れるか?

左上のマスが合っていなければflipする という操作を全てのマスで試せばおk


public class MatrixTransforming {

	public int minPushes(String[] a, String[] b) {
		int w = a[0].length();
		int h = a.length;
		int[] dx = {0, 1, 2, 0, 1, 2, 0, 1, 2};
		int[] dy = {0, 0, 0, 1, 1, 1, 2, 2, 2};

		int[][] aa = new int[h][w];
		int[][] bb = new int[h][w];
		for (int y = 0 ; y < h ; y++) {
			for (int x = 0 ; x < w ; x++) {
				aa[y][x] = a[y].charAt(x) - '0';
				bb[y][x] = b[y].charAt(x) - '0';
			}
		}

		int flips = 0;
		for (int y = 0 ; y <= h - 3 ; y++) {
			for (int x = 0 ; x <= w - 3 ; x++) {
				if (aa[y][x] != bb[y][x]) {
					for (int d = 0 ; d < 9 ; d++) {
						aa[y+dy[d]][x+dx[d]] = 1 - aa[y+dy[d]][x+dx[d]];
					}
					flips++;
				}
			}
		}


		for (int y = 0 ; y < h ; y++) {
			for (int x = 0 ; x < w ; x++) {
				if (aa[y][x] != bb[y][x]) {
					return -1;
				}
			}
		}

		return flips;
	}

}




SRM 312 ParallelepipedUnion

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

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

アホなコードを書いてしまった


public class ParallelepipedUnion {

	public int conv(int x1, int x2, int x3, int x4) {
		if (x2 < x3 || x4 < x1) {
			return 0;
		}
		if (x1 <= x3 && x4 <= x2) {
			return x4 - x3;
		}
		if (x3 <= x1 && x2 <= x4) {
			return x2 - x1;
		}
		if (x3 <= x1 && x2 <= x4) {
			return x2 - x1;
		}
		if (x1 <= x3 && x2 <= x4) {
			return x2 - x3;
		}
		if (x3 <= x1 && x4 <= x2) {
			return x4 - x1;
		}
		return 0;
	}

	public int getVolume(String[] parallelepipeds) {
		String[] c1 = parallelepipeds[0].split(" ");
		String[] c2 = parallelepipeds[1].split(" ");
		int x1 = Integer.valueOf(c1[0]);
		int x2 = Integer.valueOf(c1[3]);
		int y1 = Integer.valueOf(c1[1]);
		int y2 = Integer.valueOf(c1[4]);
		int z1 = Integer.valueOf(c1[2]);
		int z2 = Integer.valueOf(c1[5]);

		int x3 = Integer.valueOf(c2[0]);
		int x4 = Integer.valueOf(c2[3]);
		int y3 = Integer.valueOf(c2[1]);
		int y4 = Integer.valueOf(c2[4]);
		int z3 = Integer.valueOf(c2[2]);
		int z4 = Integer.valueOf(c2[5]);

		int con = conv(x1,x2,x3,x4) * conv(y1,y2,y3,y4) * conv(z1,z2,z3,z4);
		int all = (x2-x1)*(y2-y1)*(z2-z1) + (x4-x3)*(y4-y3)*(z4-z3);


		return all - con;
	}

}




SRM 314 GrasslandFencer

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

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

簡単なbitDP。


import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class GrasslandFencer {

	public double tri(double a, double b, double c) {
		double p = (a + b + c) / 2.0d;
		return Math.sqrt(p*(p-a)*(p-b)*(p-c));
	}

	public double maximalFencedArea(int[] fences) {
		int len = fences.length;
		if (len <= 2) {
			return 0.0;
		}

		java.util.Arrays.sort(fences);
		double dp[] = new double[1<<17];
		Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
		map.put(3, new HashSet<Integer>());
		for (int i = 0 ; i < len ; i++) {
			for (int j = i + 1 ; j < len ; j++) {
				for (int k = len - 1 ; k >= j + 1 ; k--) {
					if (fences[i] + fences[j] <= fences[k]) {
						continue;
					}
					int dpidx = 0;
					dpidx = dpidx | (1 << i);
					dpidx = dpidx | (1 << j);
					dpidx = dpidx | (1 << k);
					dp[dpidx] = tri(fences[i], fences[j], fences[k]);
					map.get(3).add(dpidx);
				}
			}
		}

		double maxres = 0.0d;
		for (int i = 6 ; i <= len ; i += 3) {
			map.put(i, new HashSet<Integer>());
			Set<Integer> ax = map.get(3);
			Set<Integer> bx = map.get(i - 3);
			for (int dpidx_a : ax) {
				for (int dpidx_b : bx) {
					if (Integer.bitCount((dpidx_a | dpidx_b)) == i) {
						int newdpidx = dpidx_a | dpidx_b;
						dp[newdpidx] = Math.max(dp[newdpidx], dp[dpidx_a] + dp[dpidx_b]);
						map.get(i).add(newdpidx);
					}
				}
			}
		}
		for (int i = 0 ; i < (1<<17L) ; i++) {
			maxres = Math.max(maxres, dp[i]);
		}
		return maxres;
	}
}




SRM 312 AntarcticaPolice

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

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

各町から町へ(別の町を経由しても)到達できるかどうかはワーシャルフロイド法を使うと簡単に調べられる。

グラフを強連結成分分解して考える。詳しくはeditorial参照

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm312


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class AntarcticaPolice {

	public double minAverageCost(int[] costs, String[] roads) {
		int n = costs.length;
		boolean[][] reachable = new boolean[n][n];
		for (int i = 0 ; i < n ; i++) {
			reachable[i][i] = true;
			for (int j = 0 ; j < n ; j++) {
				if (roads[i].charAt(j) == 'Y') {
					reachable[i][j] = true;
				}
			}
		}
		for (int k = 0 ; k < n ; k++) {
			for (int i = 0 ; i < n ; i++) {
				for (int j = 0 ; j < n ; j++) {
					if (reachable[i][k] && reachable[k][j]) {
						reachable[i][j] = true;
					}
				}
			}
		}

		int[] group = new int[n];
		int[] groupCost = new int[n];
		int[] groupCostIndex = new int[n];
		int gnum = 0;
		for (int i = 0 ; i < n ; i++) {
			group[i] = -1;
			groupCost[i] = -1;
		}
		for (int i = 0 ; i < n ; i++) {
			if (group[i] != -1) {
				continue;
			}
			group[i] = gnum;
			groupCost[gnum] = costs[i];
			groupCostIndex[gnum] = i;
			for (int j = i + 1 ; j < n ; j++) {
				if (reachable[i][j] && reachable[j][i]) {
					if (costs[j] < groupCost[gnum]) {
						groupCost[gnum] = costs[j];
						groupCostIndex[gnum] = j;
					}
					group[j] = gnum;
				}
			}
			gnum++;
		}

		int total = 0;
		int num = 0;
		for (int g = 0 ; g < gnum ; g++) {
			boolean iscon = false;
			for (int i = 0 ; i < n ; i++) {
				if (group[i] == g) {
					continue;
				}
				for (int j = 0 ; j < n ; j++) {
					if (group[j] != g) {
						continue;
					}
					if (reachable[i][j]) {
						iscon = true;
						break;
					}
				}
				if (iscon) {
					break;
				}
			}
			if (!iscon) {
				total += groupCost[g];
				num++;
				costs[groupCostIndex[g]] = 999999;
			}
		}

		java.util.Arrays.sort(costs);
		for (int i = 0 ; i < n ; i++) {
			double now = (double) total / num;
			if ((double)(total + costs[i]) / (num + 1) < now) {
				total += costs[i];
				num++;
			}
		}
		return (double) total / num;
	}
}