私は InterviewStreet で練習プログラムに取り組んでおり、5.15xx 秒の時間で実行されるソリューションを持っていますが、Java ソリューションに許可されている最大時間は 5 秒です。5 秒未満にするために、ここにあるものでできることはありますか? 256 MB の制限もあるので、私が言える限り、これは問題に対する最も時間とメモリ効率の良い解決策です...
編集: N と K の可能な値は、N <= 10^9 および K <= N です。これが、BigInteger を使用してすべてを行うことを選択した理由です。試行の最大数は 10000 です。したがって、基本的には、試行の数を入力し、次に試行の数ごとに整数値のペアを入力すると、プログラムは 2 番目のループで方程式の 2 項係数の 3 つのバージョンを計算します。すべてを配列に読み込んでから配列を処理し、結果を 3 番目の配列に入れて 3 番目のループで処理する方が速いと考えました。すべてを同じループで実行しようとしましたが、実行速度が遅くなりました。
二項係数を計算するために 3 つまたは 4 つの異なるアルゴリズムを試しました (nCr - または n は r を選択します。すべて同じことを言う別の方法です)。一部のアルゴリズムには、c[n][k] のような 2 次元配列が含まれます。これは、私が提出した唯一の解決策であり、何らかのメモリ エラーが発生しませんでした。nCr * nCr の答えはかなり大きくなるので、答えは output mod (10 ^ 6) + 3 である必要があります。プログラムの実行例は次のとおりです。
3
4 1
5 2
90 13
2
5
815483
カウントするためにマシンに渡す必要があるため、より高速なマシンでは実行できません。基本的に私はコードを送信し、テストケースに対して実行します。入力が上記の範囲内。
そしてプログラム自体：
import java.math.BigInteger;
import java.util.Scanner;
public class Solution {
public BigInteger nCr(int n, int r) {
if (r > n ) {
return BigInteger.ZERO;
}
if (r > n / 2) {
r = n - r;
}
BigInteger result = BigInteger.ONE;
for (int i = 0; i < r; i++) {
result = result.multiply(BigInteger.valueOf(n - i));
result = result.divide(BigInteger.valueOf(i + 1));
}
return result;
}
public static void main(String[] args) {
Scanner input = new Scanner( System.in );
BigInteger m = BigInteger.valueOf(1000003);
Solution p = new Solution();
short T = input.nextShort(); // Number of trials
BigInteger intermediate = BigInteger.ONE;
int[] r = new int[T];
int[] N = new int[T];
int[] K = new int[T];
short x = 0;
while (x < T) {
N[x] = input.nextInt();
K[x] = input.nextInt();
x++;
}
x = 0;
while (x < T) {
if (N[x] >= 3) {
r[x] = ((p.nCr(N[x] - 3, K[x]).multiply(p.nCr(N[x] + K[x], N[x] - 1))).divide(BigInteger.valueOf((N[x] + K[x]))).mod(m)).intValue();
} else {
r[x] = 0;
}
x++;
}
x = 0;
while (x < T) {
System.out.println(r[x]);
x++;
}
}
}