結果
問題 | No.498 ワープクリスタル (給料日編) |
ユーザー | Kilisame |
提出日時 | 2017-04-25 16:26:18 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 304 ms / 2,000 ms |
コード長 | 3,324 bytes |
コンパイル時間 | 2,516 ms |
コンパイル使用メモリ | 79,824 KB |
実行使用メモリ | 59,920 KB |
最終ジャッジ日時 | 2023-10-11 09:41:01 |
合計ジャッジ時間 | 7,648 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 115 ms
55,892 KB |
testcase_01 | AC | 116 ms
56,056 KB |
testcase_02 | AC | 114 ms
56,112 KB |
testcase_03 | AC | 115 ms
56,364 KB |
testcase_04 | AC | 203 ms
58,820 KB |
testcase_05 | AC | 114 ms
55,780 KB |
testcase_06 | AC | 212 ms
59,348 KB |
testcase_07 | AC | 304 ms
59,920 KB |
testcase_08 | AC | 209 ms
59,308 KB |
testcase_09 | AC | 197 ms
59,124 KB |
testcase_10 | AC | 116 ms
56,164 KB |
testcase_11 | AC | 179 ms
59,280 KB |
testcase_12 | AC | 118 ms
55,932 KB |
testcase_13 | AC | 147 ms
58,536 KB |
testcase_14 | AC | 120 ms
55,844 KB |
testcase_15 | AC | 120 ms
55,608 KB |
testcase_16 | AC | 119 ms
54,276 KB |
testcase_17 | AC | 119 ms
55,804 KB |
testcase_18 | AC | 217 ms
59,608 KB |
testcase_19 | AC | 203 ms
58,772 KB |
testcase_20 | AC | 207 ms
58,976 KB |
testcase_21 | AC | 236 ms
58,744 KB |
testcase_22 | AC | 201 ms
58,740 KB |
testcase_23 | AC | 219 ms
58,972 KB |
testcase_24 | AC | 228 ms
58,976 KB |
ソースコード
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; } }