Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-11SRM377,SRM378,SRM379 (Practice)

SRM377 (Practice)

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

Match Resultがないので自分の相対的な実力は分からないが、2完できたのでそんなに悪くはないはず。

ノーコン回だったのかな?

問題結果ポイントその他
250SquaresInsideLatticeAccepted185.32数え上げ
500GameOnAGraphAccepted351.83行列累乗
950AlienLanguageOpened0.00数学、行列累乗

SRM 377 SquaresInsideLattice

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

  • 方針を検討
    • 正方形カウントして出すだけかな?
  • サンプル合わない。
    • 軸に並行じゃない正方形も数えなきゃなのか
  • 書いて出した
public class SquaresInsideLattice {
	public long howMany(int width, int height) {
		long lw = width;
		long lh = height;
		long cnt = 0;
		
		long wh = Math.min(lw, lh); 
		for (long i = 1 ; i <= wh ; i++) {
			long col = (lw - i + 1);
			long row = (lh - i + 1);
			cnt += col * row;
		}
		for (long sum = 2 ; sum <= wh ; sum++) {
			long col = (lw - sum + 1);
			long row = (lh - sum + 1);
			cnt += col * row * (sum - 1);			
		}
		
		return cnt;
	}
}

SRM 377 GameOnAGraph

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

  • 方針を検討
    • 行列累乗するだけっぽい
    • whiteの操作の行列をW、blackの操作の行列をBとおく
    • Nターンの操作の行列は (BW)^(N/2)
      • ただしNが奇数の時はWを左からもう一つかける
    • こうしてできた行列に初期値をかければ答えが求まる
  • 特に罠はないっぽい。簡単すぎる・・・
import java.util.Arrays;

public class GameOnAGraph {

	long MOD = 1000000007;
	
	public long[][] pow(long[][] a, long n, long mod) {
		long i = 1;
		long[][] res = E(a.length);
		long[][] ap = mul(E(a.length), a, mod);
		while (i <= n) {
			if ((n & i) >= 1) {
				res = mul(res, ap, mod);
			}
			i *= 2;
			ap = mul(ap, ap, mod);
		}
		return res;
	}
	
	public long[][] E(int n) {
		long[][] a = new long[n][n];
		for (int i = 0 ; i < n ; i++) {
			a[i][i] = 1;
		}
		return a;
	}
	
	public long[][] mul(long[][] a, long[][] b, long mod) {
		long[][] c = new long[a.length][b[0].length];
		if (a[0].length != b.length) {
			System.err.print("err");
		}
		for (int i = 0 ; i < a.length ; i++) {
			for (int j = 0 ; j < b[0].length ; j++) {
				long sum = 0;
				for (int k = 0 ; k < a[0].length ; k++) {
					sum = (sum + a[i][k] * b[k][j]) % mod;
				}
				c[i][j] = sum;
			}
		}
		return c;
	}

	
	public int[] getMarks(String[] adj, String colors, String marks, int N) {
		int len = adj.length;
		long[][] white = new long[len][len];
		long[][] black = new long[len][len];
		for (int i = 0 ; i < len ; i++) {
			if (colors.charAt(i) == 'W') {
				for (int j = 0 ; j < len ; j++) {
					if (j == i) {
						white[i][j] = 1;
					}
					if (adj[i].charAt(j) == '1') {
						black[i][j] = 1;
					}
				}
			} else {
				for (int j = 0 ; j < len ; j++) {
					if (j == i) {
						black[i][j] = 1;
					}
					if (adj[i].charAt(j) == '1') {
						white[i][j] = 1;
					}
				}				
			}
		}
		
		
		int cur = N / 2;
		long[][] bw = mul(black, white, MOD);
		long[][] bwn = pow(bw, cur, MOD);
		if (N % 2 == 1) {
			bwn = mul(white, bwn, MOD);
		}
		
		long[][] fin = new long[len][1];
		for (int i = 0 ; i < len ; i++) {
			fin[i][0] = marks.charAt(i) - '0';
		}
		
		long[][] ans = mul(bwn, fin, MOD);
		int[] ansint = new int[len];
		for (int i = 0 ; i < len ; i++) {
			ansint[i] = (int)(ans[i][0] % MOD);
		}

		// System.out.println(Arrays.toString(ansint));
		return ansint;
	}
}

SRM 377 AlienLanguage

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

  • 数式をごにょごにょすると行列累乗の形に持っていける
public class AlienLanguage {

	public long[][] pow(long[][] a, long n, long mod) {
		long i = 1;
		long[][] res = E(a.length);
		long[][] ap = mul(E(a.length), a, mod);
		while (i <= n) {
			if ((n & i) >= 1) {
				res = mul(res, ap, mod);
			}
			i *= 2;
			ap = mul(ap, ap, mod);
		}
		return res;
	}
	
	public long[][] E(int n) {
		long[][] a = new long[n][n];
		for (int i = 0 ; i < n ; i++) {
			a[i][i] = 1;
		}
		return a;
	}
	
	public long[][] mul(long[][] a, long[][] b, long mod) {
		long[][] c = new long[a.length][b[0].length];
		if (a[0].length != b.length) {
			System.err.print("err");
		}
		for (int i = 0 ; i < a.length ; i++) {
			for (int j = 0 ; j < b[0].length ; j++) {
				long sum = 0;
				for (int k = 0 ; k < a[0].length ; k++) {
					sum = (sum + a[i][k] * b[k][j]) % mod;
				}
				c[i][j] = sum;
			}
		}
		return c;
	}
	
	public int getNumberOfWords(int P, int Q, int N, int M) {
		long[][] p3 = {
			{P, P, 1},
			{0, P, 1},
			{0, 0, 1}
		};
		p3 = pow(p3, N, M);
		
		long[][] q3 = {
				{Q, Q, 1},
				{0, Q, 1},
				{0, 0, 1}
			};
		q3 = pow(q3, N, M);
		
		
		long p = (p3[0][0] + p3[0][1] + p3[0][2]) % M;
		long q = (q3[0][0] + q3[0][1] + q3[0][2]) % M;
		long pq1 = ((p * q) - 1 + M) % M;
		
		
		return (int)pq1;
	}
}

SRM378 (Practice)

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

数学回。またもや2完できず。easy早解きゲーだった模様 226/540位

問題結果ポイントその他
250TrueStatementsAccepted244.45速攻
500SolvePolynomialOpened0.00方針立たず。
1000TwistyPassagesOpened0.00無理

SRM 378 TrueStatements

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

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

  • 方針を検討
    • 「真実を言ってる人の数」と同じ事を言ってる人の数を数えて一致してたらそれの最大値でOK
  • 速攻で実装、サンプルを通す
    • 早解き勝負な気がするのでノーチェックで出す
public class TrueStatements {
	public int numberTrue(int[] statements) {
		int len = statements.length;
		int[] tcnt = new int[51];
		for (int i = 0 ; i < len ; i++) {
			tcnt[statements[i]]++;
		}
		
		int max = -1;
		for (int i = 0 ; i < 51 ; i++) {
			if (tcnt[i] == i) {
				max = Math.max(max, i);
			}
		}		
		return max;
	}
}

SRM 378 SolvePolynomial

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

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

  • 方針を検討
    • 2分探索?
      • いや、多分無理・・・
    • 解の候補を幾つか出してそれを試していけばいいのかなぁ
    • 分からん・・・

その後

  • 他の人のコードを読む。
    • なんか約数をとって候補としてる
      • なぜ?
    • あ、そっか
      • (多項式) = (x-a1)(x-a2)(x-a3) .... (x-an) と因数分解できるとする。
      • すると一番次数の小さい項は a1 * a2 * ... * an になってるはずだから・・・ということか
    • 定数項が0だったら候補を0に追加
    • 一番次数の小さい項xについて、x % i == 0 な i に対し i, -i, x/i, -x/i を候補に追加
  • 求めた候補に対して式を実際に計算し、0になるかどうか確かめる。
    • BigInteger使えばいいのかな・・・TLEしそうな気もするが
      • やっぱりダメだった
    • 他の人のコードを読むと、でかい素数のMODを2つぐらい取って0だったらOKとしてる
      • そんな適当でいいのか・・・?
  • そう書いたら通った。腑に落ちない・・・
en




SRM379 (Practice)

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

197/391位

問題結果ポイントその他
250SellingProductsAccepted224.31簡単
500FillBoxWA0.00素で間違えた 猛省
1000TVGameUnopened0.00-

SRM 379 SellingProducts

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

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

  • やるだけ
public class SellingProducts {
	public int optimalPrice(int[] price, int[] cost) {
		int ans = 0;
		int opt = -1;
		int len = price.length;
		for (int i = 0 ; i < len ; i++) {
			int sell = price[i];
			int profit = 0;
			for (int j = 0 ; j < len ; j++) {
				if (sell <= price[j]) {
					if (cost[j] < sell) {
						profit += sell - cost[j];
					}
				}
			}
			if (ans < profit) {
				ans = profit;
				opt = sell;
			} else if (ans == profit && opt > sell) {
				opt = sell;
			}
		}
		return (opt == -1) ? 0 : opt;
	}
}

SRM 379 FillBox

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

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

  • 使えるCube数が無限大と仮定した時、各大きさのCubeが何個必要か求めておく
  • 大きいCubeから貪欲に使っていってOK
    • n段階小さいCubeで大きいCubeを代用するには pow(8, n)個必要
    • オーバーフローに注意する
import java.util.Arrays;

public class FillBox {
	public int minCubes(int length, int width, int height, int[] cubes) {
		int len = cubes.length;
		long[] lcubes = new long[len];
		for (int i = 0 ; i < len ; i++) {
			lcubes[i] = cubes[i];
		}
		
		long minlwh = Math.min(length, Math.min(width, height));
		long[] needpack = new long[100];
		long lwh = minlwh;
		int cnt = 0;
		while (lwh >= 1) {
			lwh /= 2;
			cnt++;
		}
		
		for (int mc = cnt - 1 ; mc >= 0 ; mc--) {
			long size = (long)Math.pow(2, mc);
			long ln = length / size;
			long wl = width / size;
			long hl = height / size;
			needpack[mc] = ln * wl * hl;
			long pw = 1;
			for (int bigger = mc + 1 ; bigger < 100 ; bigger++) {
				pw *= 8;
				if (needpack[bigger] >= 1) {
					needpack[mc] -= pw * needpack[bigger];
				}
			}
		}
		
		long used = 0;
		for (int i = cnt - 1 ; i >= 0 ; i--) {
			if (needpack[i] >= 1) {
				long needv = needpack[i] * (long)Math.pow(8, i);
				for (int u = Math.min(i, len-1) ; u >= 0 ; u--) {
					if (lcubes[u] >= 1) {
						long pu = (long)Math.pow(8, u);
						long canuse = Math.min(needv / pu, lcubes[u]);
						lcubes[u] -= canuse;
						used += canuse;
						needv -= canuse * pu;
					}
					if (needv <= 0) {
						break;
					}
				}
				if (needv >= 1) {
					return -1; 
				}
			}
		}	
		return (int)used;
	}
}

utmathutmath2012/03/26 13:34SRM378 Medium 落としておきました。

hama_DUhama_DU2012/03/26 17:27うっ、嘘解法でしたからね・・・
どんなケースで落としたのか教えていただけるとうれしいです。

utmathutmath2012/03/27 15:563552*x^25 + 730*x^20 + 886*x^15 + 68*x^10 + 160*x^5 + 62*x + 4 です。x = 4 を代入すると、4 * (10^9+9) * (10^9 +7) になり、どちらで mod をとっても 0 になってしまいます。

hama_DUhama_DU2012/03/29 16:19なるほど、ありがとうございます。
というかこんなケースよく見つけましたね・・・