結果
問題 | No.425 ジャンケンの必勝法 |
ユーザー | 37zigen |
提出日時 | 2016-09-23 13:38:41 |
言語 | Java21 (openjdk 21) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,280 bytes |
コンパイル時間 | 4,046 ms |
コンパイル使用メモリ | 80,556 KB |
実行使用メモリ | 51,812 KB |
最終ジャッジ日時 | 2024-04-28 21:27:56 |
合計ジャッジ時間 | 8,241 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | AC | 128 ms
41,052 KB |
testcase_03 | AC | 133 ms
41,036 KB |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
ソースコード
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 = ReMt(m); vec = MtPrd(m, vec); System.out.println(1.0 / 3.0 + 1.0 / 3.0 * vec[idx][0]); } // 行列式:detA(Aが正方行列であることを仮定) // 定義通り計算している。遅い。 // O(n!)? double detMt(double[][] A) { double sum = 0; if (A.length == 1 || A[0].length == 1) { return A[0][0]; } else { for (int j = 0; j < A.length; j++) { sum += Math.pow(-1, j) * A[j][0] * detMt(subMt(j + 1, 0 + 1, A)); } return sum; } } // i行、j列を除いた小行列を出力 double[][] subMt(int i, int j, double[][] A) { double[][] B = new double[A[0].length - 1][A.length - 1]; for (int k = 0; k < A[0].length - 1; k++) { for (int l = 0; l < A.length - 1; l++) { int kk = k; int ll = l; if (k >= i - 1) { kk++; } if (l >= j - 1) { ll++; } B[k][l] = A[kk][ll]; } } return B; } // 逆行列を求める。余因子行列を用いている。 double[][] ReMt(double[][] A) { double[][] B = new double[A.length][A[0].length]; double detA = detMt(A); for (int i = 0; i < A.length; i++) { for (int j = 0; j < A[0].length; j++) { B[i][j] = Math.pow(-1, i + j) * detMt(subMt(j + 1, i + 1, A)) / detA; } } return B; } 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)); } }