結果

問題 No.498 ワープクリスタル (給料日編)
ユーザー KilisameKilisame
提出日時 2017-04-25 16:26:18
言語 Java21
(openjdk 21)
結果
AC  
実行時間 289 ms / 2,000 ms
コード長 3,324 bytes
コンパイル時間 2,578 ms
コンパイル使用メモリ 79,968 KB
実行使用メモリ 57,984 KB
最終ジャッジ日時 2024-09-13 08:50:32
合計ジャッジ時間 7,576 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 128 ms
54,168 KB
testcase_01 AC 128 ms
54,072 KB
testcase_02 AC 130 ms
53,996 KB
testcase_03 AC 128 ms
54,140 KB
testcase_04 AC 181 ms
56,768 KB
testcase_05 AC 128 ms
53,892 KB
testcase_06 AC 182 ms
57,144 KB
testcase_07 AC 289 ms
57,984 KB
testcase_08 AC 210 ms
57,220 KB
testcase_09 AC 177 ms
57,000 KB
testcase_10 AC 130 ms
53,832 KB
testcase_11 AC 170 ms
56,832 KB
testcase_12 AC 131 ms
54,140 KB
testcase_13 AC 156 ms
56,288 KB
testcase_14 AC 131 ms
54,248 KB
testcase_15 AC 131 ms
53,944 KB
testcase_16 AC 131 ms
53,896 KB
testcase_17 AC 130 ms
54,024 KB
testcase_18 AC 200 ms
57,112 KB
testcase_19 AC 195 ms
57,220 KB
testcase_20 AC 197 ms
57,080 KB
testcase_21 AC 200 ms
56,868 KB
testcase_22 AC 180 ms
57,032 KB
testcase_23 AC 187 ms
56,924 KB
testcase_24 AC 180 ms
57,000 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static int gx;
    private static int gy;
    private static int[][] crystalArray;
    private static List<int[]> resultSelectPatternList;
    private static final BigInteger DIVISER = new BigInteger("1000000007");

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        gx = Integer.parseInt(sc.next());
        gy = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        /* k種のクリスタル。[k][0]=x移動量, [k][1]=y移動量, [k][2]=個数 */
        crystalArray = new int[k][3];
        for (int i = 0; i < k; i++) {
            crystalArray[i][0] = Integer.parseInt(sc.next());
            crystalArray[i][1] = Integer.parseInt(sc.next());
            crystalArray[i][2] = Integer.parseInt(sc.next());
        }
        sc.close();
        /* ナップサック問題のように、k種目のクリスタルを0個使う場合～N(k)個使う場合に、ゴールまでの相対座標を求める。 */
        resultSelectPatternList = new ArrayList<int[]>();
        selectCrystal(0, new int[k], new int[2]);
        /* 何番目のクリスタルを何個使った時にゴールにたどり着くかの全パターンが求まるので、あとは各パターンごとにクリスタルを使う順が何通りあるかを求め、足し合わせる */
        BigInteger result = BigInteger.ZERO;
        for (int[] selectPattern : resultSelectPatternList) {
            result=result.add(permutation(selectPattern));
            while (result.compareTo(DIVISER) > 0) {
                result = result.mod(DIVISER);
            }
        }
        System.out.println(result);
    }

    private static void selectCrystal(int index, int[] selected, int[] position) {
        if (index == crystalArray.length) {
            if (position[0] == gx && position[1] == gy) {
                resultSelectPatternList.add(selected);
            }
            return;
        }
        for (int i = 0; i <= crystalArray[index][2]; i++) {
            int[] currentSelect = Arrays.copyOf(selected, selected.length);
            int[] currentPosition = Arrays.copyOf(position, position.length);
            currentSelect[index] = i;
            currentPosition[0] += crystalArray[index][0] * i;
            currentPosition[1] += crystalArray[index][1] * i;
            selectCrystal(index + 1, currentSelect, currentPosition);
        }
    }

    private static BigInteger permutation(int[] pattern) {
        int total = 0;
        for (int i = 0; i < pattern.length; i++) {
            total = total += pattern[i];
        }
        BigInteger totalFact = factorialBI(total);
        for (int i = 0; i < pattern.length; i++) {
            totalFact = totalFact.divide(factorialBI(pattern[i]));
        }
        while (totalFact.compareTo(DIVISER) > 0) {
            totalFact = totalFact.mod(DIVISER);
        }
        return totalFact;
    }

    private static BigInteger factorialBI(int n) {
        BigInteger bi = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            bi = bi.multiply(new BigInteger(String.valueOf(i)));
        }
        return bi;
    }

}
0