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
- 方針を検討
- 正方形カウントして出すだけかな?
- サンプル合わない。
- 軸に並行じゃない正方形も数えなきゃなのか
- 書いて出した
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
- 方針を検討
- 行列累乗するだけっぽい
- 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
- 数式をごにょごにょすると行列累乗の形に持っていける
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
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
http://www.topcoder.com/stat?c=problem_statement&pm=8273
- 方針を検討
- 2分探索?
- いや、多分無理・・・
- 解の候補を幾つか出してそれを試していけばいいのかなぁ
- 分からん・・・
- 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としてる
- そんな適当でいいのか・・・?
- BigInteger使えばいいのかな・・・TLEしそうな気もするが
- そう書いたら通った。腑に落ちない・・・
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
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
http://www.topcoder.com/stat?c=problem_statement&pm=8442
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; } }
どんなケースで落としたのか教えていただけるとうれしいです。
というかこんなケースよく見つけましたね・・・