結果
問題 | No.425 ジャンケンの必勝法 |
ユーザー | 37zigen |
提出日時 | 2016-09-23 03:53:03 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 3,698 bytes |
コンパイル時間 | 4,253 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 42,292 KB |
最終ジャッジ日時 | 2024-04-28 22:48:51 |
合計ジャッジ時間 | 8,688 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 139 ms
41,308 KB |
testcase_01 | AC | 137 ms
41,060 KB |
testcase_02 | AC | 139 ms
41,152 KB |
testcase_03 | AC | 137 ms
41,048 KB |
testcase_04 | AC | 141 ms
41,132 KB |
testcase_05 | AC | 139 ms
41,452 KB |
testcase_06 | AC | 139 ms
41,260 KB |
testcase_07 | AC | 139 ms
40,880 KB |
testcase_08 | AC | 142 ms
41,024 KB |
testcase_09 | AC | 136 ms
41,172 KB |
testcase_10 | AC | 132 ms
41,596 KB |
testcase_11 | AC | 180 ms
42,124 KB |
testcase_12 | AC | 182 ms
42,280 KB |
testcase_13 | AC | 183 ms
42,132 KB |
testcase_14 | AC | 184 ms
42,292 KB |
testcase_15 | AC | 140 ms
41,156 KB |
testcase_16 | AC | 136 ms
41,280 KB |
testcase_17 | AC | 181 ms
41,992 KB |
testcase_18 | AC | 135 ms
41,044 KB |
testcase_19 | AC | 134 ms
41,476 KB |
testcase_20 | AC | 185 ms
41,744 KB |
testcase_21 | AC | 135 ms
41,220 KB |
testcase_22 | AC | 140 ms
41,156 KB |
ソースコード
package No400番台; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class C { public static void main(String[] args) { new C().run(); } void run() { solver(); } double EPS = 1e-6; void solver() { Scanner sc = new Scanner(System.in); int p = sc.nextInt(); int q = sc.nextInt(); ArrayList<Integer> list = new ArrayList<>(); int tmp = p; if (q != 0) { while (tmp != 100) { tmp = Math.min(100, tmp + q); list.add(tmp); } tmp = p; while (tmp != 0) { tmp = Math.max(0, tmp - q); list.add(tmp); } tmp = 0; while (tmp != 100) { tmp = Math.min(100, tmp + q); list.add(tmp); } tmp = 100; while (tmp != 0) { tmp = Math.max(0, tmp - q); list.add(tmp); } } list.add(p); list.sort(null); int idx = -1; for (int i = 0; i < list.size(); i++) { if (Math.abs(list.get(i) - p) < EPS) idx = i; while (i + 1 < list.size() && Math.abs(list.get(i) - list.get(i + 1)) < EPS) { list.remove(i + 1); } } int n = list.size(); double[][] vec = new double[n][1]; double[][] m = new double[n][n]; for (int i = 0; i < n; i++) { m[i][i] = 1.0; } for (int i = 0; i < n; i++) { vec[i][0] += list.get(i) / 100.0 * 0.5 + (100 - list.get(i)) / 100.0 * 1.0 / 3.0; int idx1 = list.indexOf(list.get(i) - q); if (idx1 == -1) m[i][0] -= list.get(i) / 100.0 * 0.5; else m[i][Math.max(0, idx1)] -= list.get(i) / 100.0 * 0.5; int idx2 = list.indexOf(list.get(i) + q); if (idx2 == -1) m[i][n - 1] -= (100 - list.get(i)) / 100.0 * 1.0 / 3.0; else m[i][idx2] -= (100 - list.get(i)) / 100.0 * 1.0 / 3.0; } m = Rev(m); vec = MtPrd(m, vec); System.out.println(1.0 / 3.0 + 1.0 / 3.0 * vec[idx][0]); } public static double[][] Rev(double[][] OM) { int n = OM.length, m = OM[0].length; if (n != m) return null; double[][] M = new double[n][2 * n]; m = 2 * n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { M[i][j] = OM[i][j]; } M[i][n + i] = 1; } double[][] res = operateElementarily(M); if (res == null) return null; // resotration double[][] ret = new double[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ret[i][j] = res[i][j + n]; } } return ret; } public static double[][] operateElementarily(double[][] M) { int n = M.length, m = M[0].length; int rank = n - 1; // Forward Elimination for (int i = 0; i < n; i++) { // select pivot double max = 1E-9; int maxj = -1; for (int j = i; j < n; j++) { double v = Math.abs(M[j][i]); if (v > max) { max = v; maxj = j; } } if (maxj == -1) { rank = i - 1; break; } if (maxj != i) { double[] dum = M[i]; M[i] = M[maxj]; M[maxj] = dum; } double D = M[i][i]; M[i][i] = 1; for (int j = i + 1; j < m; j++) { M[i][j] /= D; } for (int j = i + 1; j < n; j++) { double B = -M[j][i]; M[j][i] = 0; for (int k = i + 1; k < m; k++) { M[j][k] += M[i][k] * B; } } } // Back Substitution for (int i = rank; i >= 0; i--) { for (int j = rank; j >= i + 1; j--) { double B = -M[i][j]; M[i][j] = 0; for (int k = rank + 1; k < m; k++) { M[i][k] += B * M[j][k]; } } } return M; } double[][] MtPrd(double[][] A, double[][] B) { double[][] C = new double[A.length][B[0].length]; for (int i = 0; i < A.length; i++) { for (int j = 0; j < B[0].length; j++) { for (int k = 0; k < A[0].length; k++) { C[i][j] += A[i][k] * B[k][j]; } } } return C; } void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }