結果

問題 No.425 ジャンケンの必勝法
ユーザー 37zigen
提出日時 2016-09-23 03:53:03
言語 Java
(openjdk 23)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 3,698 bytes
コンパイル時間 3,600 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 42,636 KB
最終ジャッジ日時 2024-11-17 19:51:25
合計ジャッジ時間 7,436 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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));
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0