Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-27SRM300台を練習していく part4

SRM 310 PyramidOfCubes

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

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

一番下のlevelに入るcubeの個数が決まれば上面と底面の面積が求まる。

あとはlevelごとに側面積を求めていく。

ちょっと苦戦。汚いコードだ( ゚д゚)、ペッ


public class PyramidOfCubes {
	public double surface(int K) {
		long cnum = K;
		long dan = 0;
		long used = 0;
		double result = 0.0d;
		while (used < cnum) {
			dan++;
			used += dan * dan;
		}
		if (used == cnum) {
			result += dan * dan * 2;
			for (long d = 1 ; d <= dan ; d++) {
				result += d * 4;
			}
		} else {
			long unused = K;
			for (long d = dan ; d >= 1 ; d--) {
				if (unused <= d * d) {
					if (unused >= d) {
						long sht = (unused - 1) / d + 1;
						result += (d + sht) * 2;
					} else {
						result += (1 + unused) * 2;
					}
					if (d == dan) {
						result += unused * 2;
					}
					break;
				}
				if (d == dan) {
					result += dan * dan * 2;
				}
				result += d * 4;
				unused -= d * d;
			}
		}
		return result;
	}
}



SRM 306 LightSwitches

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

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

ある複数個のスイッチの組み合わせで再現できるスイッチを取り除いて、

答えは 2^(最後に残ったスイッチの数) ということはすぐ分かる。

問題はその余分なスイッチをどうやって見つけるか。

各スイッチはベクトルとみなすことができて、その各要素は各バルブにつながっているかどうか。(つながっている=1 つながっていない=0)

すると、余分なスイッチとは他のスイッチ(ベクトル)に対して一次従属であるということ。

余分なスイッチを全て取り除いた残りのスイッチ(ベクトル)は線形独立なので、

各スイッチに対応するベクトルを縦に並べた行列をAとおくと、この問題はAのランクを求めることに帰着できる。


参考:

http://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E3%81%AE%E6%B6%88%E5%8E%BB%E6%B3%95


public class LightSwitches {
	public long countPossibleConfigurations(String[] switches) {
		int sn = switches.length;
		int bn = switches[0].length();
		int[][] conf = new int[sn][bn];
		for (int i = 0 ; i < sn ; i++) {
			for (int j = 0 ; j < bn ; j++) {
				if (switches[i].charAt(j) == 'Y') {
					conf[i][j] = 1;
				} else {
					conf[i][j] = 0;
				}
			}
		}

		int cnt = 0;
		for (int i = 0 ; i < bn ; i++) {
			int chosen = -1;
			for (int x = cnt ; x < sn ; x++) {
				if (conf[x][i] == 1) {
					chosen = x;
					break;
				}
			}
			if (chosen == -1) continue;

			for (int m = 0 ; m < bn ; m++) {
				int tmp = conf[chosen][m];
				conf[chosen][m] = conf[cnt][m];
				conf[cnt][m] = tmp;
			}

			for (int n = cnt + 1 ; n < sn ; n++) {
				if (conf[n][i] == 1) {
					for (int m = 0 ; m < bn ; m++) {
						if (conf[n][m] == 1 ^ conf[cnt][m] == 1) {
							conf[n][m] = 1;
						} else {
							conf[n][m] = 0;
						}
					}
				}
			}
			cnt++;
		}
		return 1L << cnt;
	}
}

SRM 309 ScoreRecomposition

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

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

特にいい方法が思い浮かばなかったのでnext_permutationを使った。

質問の数は高々10だから、順列の数は10! = 3,628,800。いける!


public class ScoreRecomposition {
	public int minError(String questions, int score) {
		int len = questions.length();
		int min = 99999;
		int[] scores = new int[len];
		for (int i = 0 ; i < len ; i++) {
			scores[i] = i + 1;
		}
		do {
			int sc = 0;
			for (int i = 0 ; i < len ; i++) {
				if (questions.charAt(i) == 'C') {
					sc += scores[i];
				}
			}
			if (sc == score) {
				int err = 0;
				for (int i = 0 ; i < len ; i++) {
					err = Math.max(err, Math.abs(i+1 - scores[i]));
				}
				if (err < min) {
					min = err;
				}
			}
		} while (next_permutation(scores));

		if (min == 99999) return -1;
		return min;
	}

	public boolean next_permutation(int[] num) {
		int len = num.length;
		int x = len - 2;
		while (x >= 0 && num[x] >= num[x+1]) {
			x--;
		}
		if (x == -1) return false;

		int y = len - 1;
		while (y > x && num[y] <= num[x]) {
			y--;
		}
		int tmp = num[x];
		num[x] = num[y];
		num[y] = tmp;
		java.util.Arrays.sort(num, x+1, len);
		return true;
	}
}