hama_DU@TopCoderへの道

SRM377 (Practice)

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

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

SRM 377 SquaresInsideLattice

Java, div1q1 |

• 方針を検討
  • 正方形カウントして出すだけかな？
• サンプル合わない。
  • 軸に並行じゃない正方形も数えなきゃなのか
• 書いて出した

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

Java, div1q2 |

• 方針を検討
  • 行列累乗するだけっぽい
  • 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

Java, div1q3 |

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

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)

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

SRM 378 TrueStatements

Java, div2q2, div1q1 |

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

Java, div1q2 |

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)

197/391位

SRM 379 SellingProducts

Java, div2q2, div1q1 |

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

Java, div1q2 |

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