AtcoderのABC253のE - Distance Sequence問題を解く際に、Java 11.0.6のバッグを発見した。
提出したコードは
import java.util.Scanner; import java.util.stream.IntStream; public class Main { /** mod対象数字 */ private static final long MOD = 998_244_353L; public static void main(String[] args) { try (Scanner scanner = new Scanner(System.in)) { int n = scanner.nextInt(), m = scanner.nextInt(), k = scanner.nextInt(); // dp[i][j]はi番目の数字がj以下のすべての組み合わせ数 long[][] dp = new long[2][m + 1]; IntStream.rangeClosed(0, m).forEach(i -> dp[0][i] = i); IntStream.range(1, n).forEach(i -> { dp[i & 1][0] = 0L; IntStream.rangeClosed(1, m).forEach(j -> { if (0 == k) { dp[i & 1][j] = (dp[(i - 1) & 1][m] + dp[i & 1][j - 1]) % MOD; } else { dp[i & 1][j] = (dp[(i - 1) & 1][m] - dp[(i - 1) & 1][Math.min(m, j + k - 1)] + dp[(i - 1) & 1][Math.max(0, j - k)] + MOD + dp[i & 1][j - 1]) % MOD; } }); }); System.out.println(dp[(n - 1) & 1][m]); } } }
であるが、「02_max_05.txt」のテストケースだけ「WA」になってしまう。
ローカルでの実行(OpenJDK 11.0.15を使用)は問題なかったのに、仕方なくAtCoderの使う11.0.6をダウンロードして、実行したら、実行するたびに異なる結果になっていた(原因不明)。
原因はよくわからないが、IntStreamで書いたforEach文を普通のfor文に置き換えたら、実行できた。最終的に提出したコードは
import java.util.Scanner; import java.util.stream.IntStream; public class Main { /** mod対象数字 */ private static final long MOD = 998_244_353L; public static void main(String[] args) { try (Scanner scanner = new Scanner(System.in)) { int n = scanner.nextInt(), m = scanner.nextInt(), k = scanner.nextInt(); // dp[i&1][j]はi番目の数字がj以下のすべての組み合わせ数 long[][] dp = new long[2][m + 1]; IntStream.rangeClosed(0, m).forEach(i -> dp[0][i] = i); for (int i = 1; i < n; i++) { dp[i & 1][0] = 0L; for (int j = 1; j <= m; j++) { if (0 == k) { dp[i & 1][j] = (dp[(i - 1) & 1][m] + dp[i & 1][j - 1]) % MOD; } else { dp[i & 1][j] = (dp[(i - 1) & 1][m] - dp[(i - 1) & 1][Math.min(m, j + k - 1)] + dp[(i - 1) & 1][Math.max(0, j - k)] + MOD + dp[i & 1][j - 1]) % MOD; } } } System.out.println(dp[(n - 1) & 1][m]); } } }
である。
結局、AtCoderのために、JDK 11.0.6が必要であることと、IntStreamが信頼できないことを学んだ。