SRM377,SRM378,SRM379 (Practice)

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

SRM377 (Practice)

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

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

	問題	結果	ポイント	その他
250	SquaresInsideLattice	Accepted	185.32	数え上げ
500	GameOnAGraph	Accepted	351.83	行列累乗
950	AlienLanguage	Opened	0.00	数学、行列累乗

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位

	問題	結果	ポイント	その他
250	TrueStatements	Accepted	244.45	速攻
500	SolvePolynomial	Opened	0.00	方針立たず。
1000	TwistyPassages	Opened	0.00	無理

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としてる
  - そんな適当でいいのか・・・？
そう書いたら通った。腑に落ちない・・・

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SolvePolynomial {

	long MOD = 1000000009;
	long MOD2 = 1000000007;
	
	public boolean isok(long x, int[] a) {
		int len = a.length;
		long l = 0;
		for (int i = len - 1 ; i >= 0 ; i--) {
			l = (l * x + a[i]) % MOD;
		}
		if (l == 0) {
			for (int i = len - 1 ; i >= 0 ; i--) {
				l = (l * x + a[i]) % MOD2;
			}
			if (l == 0) {
				return true;
			}
		}
		return false;
	}
	
	public int[] integerRoots(int[] X, int[] Y, int n) {
		int[] a = new int[n+1];
		int lx = X.length;
		int ly = Y.length;
		for (int i = 0 ; i <= n ; i++) {
			int p = i % lx;
			int q = (i + Y[i % ly]) % lx;
			a[i] = X[p];
			X[p] = X[q];
			X[q] = a[i];
		}
		
		
		Set<Integer> candidate = new HashSet<Integer>();
		if (a[0] == 0) {
			candidate.add(0);
		}
		for (int i = 0 ; i <= n ; i++) {
			if (a[i] != 0) {
				int ch = Math.abs(a[i]);
				for (int j = 1 ; j * j <= ch ; j++) {
					if (ch % j == 0) {
						candidate.add(j);
						candidate.add(ch/j);
						candidate.add(-j);
						candidate.add(-ch/j);						
					}
				}
				break;
			}
		}

		System.out.println(candidate.size());
		
		
		List<Integer> ok = new ArrayList<Integer>();
		for (int c : candidate) {
			if (isok(c, a)) {
				ok.add(c);
			}
		}
		if (ok.size() == 0) {
			return new int[]{};
		} else {
			int[] ans = new int[ok.size()];
			for (int i = 0 ; i < ok.size() ; i++) {
				ans[i] = ok.get(i);
			}
			Arrays.sort(ans);
			return ans;
		}
	}
}

SRM379 (Practice)

197/391位

	問題	結果	ポイント	その他
250	SellingProducts	Accepted	224.31	簡単
500	FillBox	WA	0.00	素で間違えた猛省
1000	TVGame	Unopened	0.00	-

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

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

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

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

		2012/03
日	月	火	水	木	金	土
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31