Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

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;
	}
}

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;
	}
}

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なるほど、ありがとうございます。
というかこんなケースよく見つけましたね・・・