AtCorderのFrog問題について

Question

前提・実現したいこと

Atcorderの、Educational DP Contestの二問目、B-Frog 2でACを取りたい
Frog問題の、カエルの跳べる距離の最大値が、標準入力で与えられるバージョンの問題です。

https://atcoder.jp/contests/dp/tasks/dp_b

発生している問題・エラーメッセージ

16のテストケースのうち、13こがACで3こWAになってしまっています。

エラーメッセージ

該当のソースコード

import java.util.Scanner;
 
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
 
		// N:足場の数
		// K:カエルの最大飛距離
		int N = sc.nextInt();
		int K = sc.nextInt();
 
		final int INF = 100100100;
 
		int[] h = new int[N];
		int[] dp = new int[N];
 
		for (int i = 0; i < N; i++) {
			dp[i] = INF;
		}
		for (int i = 0; i < N; i++) {
			h[i] = sc.nextInt();
		}
 
		// 初期条件
		dp[0] = 0;
 
		// Kの最大値はN
		if(N<K) {
			K = N;
		}
 
		for (int i = 1; i < N; i++) {
			// 2番目の足場は1番目の足場から遷移してくるのみ
			if (i == 1) {
				dp[i] = Math.abs(h[i] - h[i - 1]);
				// test
//				System.out.println("i=" + i + " " + dp[i]);
			} else {
				// 最大K通りの遷移が考えられる
				for (int j = 1; j <= K; j++) {
					// i-j>0にしてしまうと、例えば、i=2,j=2のときを考慮できない
					// iが0始まりであることに注意
					if (i >= j) {
						dp[i] = Math.min(dp[i], dp[i - j] + Math.abs(h[i] - h[i - j]));
						// test
//						System.out.println("i=" + i + " " + dp[i]);
					}
				}
			}
		}
		System.out.println(dp[N-1]);
	}
}

試したこと

他の方の提出したJavaでACになっているソースコードと比較しましたが、行っている処理は同じように思えました。
また、AtCorderの解説を見ましたが、そこでも行っている処理は同じように思えました。

補足情報（FW/ツールのバージョンなど）

テストケースの中身がわかれば、おそらく、解決するのですが調べてもテストケースは見当たりませんでした。

Answer 1

最大値宣言が甘いのでは？

Comments

[tanaka.moments]

まさにその通りでした。10^4 * 10^5なので最大10^9まで考えられました。INFを一桁増やして、INF=1001001001にしてみたらACになりました。

[swordone]

というか、Integer.MAX_VALUEを指定すればそれでいいのでは？

[tanaka.moments]

確かに、ほかの方のソースでもそうなっていました。次からはそうしてみます

Answer 2

dp[i] = Math.min(dp[i], dp[i - j] + Math.abs(h[i] - h[i - j]));

このあたりで桁あふれ起こしていそうですね。int型ではなくlong型を利用しても問題は再現しますか?

Comments

[tanaka.moments]

回答ありがとうございます。
hとdpの2つの配列をlong型で定義し直してみましたが、全く同じテストケースにてWAが出てしまいました

[tanaka.moments]

他の方の提出ソースコードでも、配列はintで定義しているため、そこで問題が発生しているとは考えにくいと思われます。