dpを用いた組み合わせの計算

Question

コード

import java.util.Scanner;
public class TypicalStairs {
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int N=scan.nextInt();
        int M=scan.nextInt();
        int[] a=new int[M];
        for(int i=0;i<M;i++){
            a[i]=scan.nextInt();
            if(i!=0){
                if(a[i]-a[i-1]==1){
                    System.out.println(0);
                    return ;
                }
            }
        }
        long[] dp=new long[N+1];
        dp[0]=1;
        int j=0;
        for(int i=0;i<N;i++){
            if((i+1)!=a[j]){
                if(i==0) dp[i+1]=dp[i];
                else dp[i+1]=dp[i]+dp[i-1];
                j++;
            }
            else dp[i+1]=0;
        }
        System.out.println(dp[N]%1000000007);
    }
}

#入力とエラーメッセージ
6 1
3
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
at TypicalStairs.main(TypicalStairs.java:21)

#質問内容
エラーメッセージを見ると配列にいれられていないということだと思うのですが，なぜこうなってしまうのか教えていただきたいです。
入力の場所は21行目ではないのにここでこうなってしまう理由が全く分からないです。

Answer 1

int M=scan.nextInt();

で a[] の要素数が決まるわけですが、 示された入力値だと 1 になります。この場合、a[] の最大インデックスは 0 になります。

        for(int i=0;i<N;i++){
            if((i+1)!=a[j]){
                if(i==0) dp[i+1]=dp[i];
                else dp[i+1]=dp[i]+dp[i-1];
                j++;
            }
            else dp[i+1]=0;
        }

で a[] の要素数に関係なく j が増えていき、この例ですと　(i+1)!=a[1] で a[1] にアクセスしようとして、ArrayIndexOutOfBoundsException が発生しています。

【最後の入力パターンの出力結果が異なった理由】

i+1==a[j] の時が、i+1段目が壊れた床の時なので (i+1)!=a[j] に j++ してしまうと壊れた床でなくても次の壊れた床の段を取得してしまいます。

なので正しくは、else ブロックで j++ する必要があります。

        dp[0]=1;
        int j=0;
        for(int i=0;i<N;i++){
            if((i+1)!=a[j]){
                if(i==0) dp[i+1]=dp[i];
                else dp[i+1]=dp[i]+dp[i-1];
            }
            else {
            	dp[i+1]=0;
            	if (j < M-1) j++;
            }
        }

なお、こうした場合、スキャン時の壊れた段が続く場合を考慮に入れなくても大丈夫です。

        for(int i=0;i<M;i++){
            a[i]=scan.nextInt();
//            if(i!=0){
//                if(a[i]-a[i-1]==1){
//                    System.out.println(0);
//                    return ;
//                }
//            }
        }

例えば、4段目・5段目と壊れた床が続いていた場合、dp[4] と dp[5] はともに 0 になるため、以降、dp[i]+dp[i-1]; の結果が常に 0 となるためです。

　なお、N が 10 の 5 乗まで許されることから、dp[i+1] の計算が終わった時点で 1000000007 を超えたら、1000000007 を引く処置をしておいた方が良いかもしれません。

        dp[0]=1;
        int j=0;
        for(int i=0;i<N;i++){
            if((i+1)!=a[j]){
                if(i==0) dp[i+1]=dp[i];
                else dp[i+1]=dp[i]+dp[i-1];
                if(dp[i+1] >= MOD) dp[i+1] -= 1000000007;
            }
            else {
            	dp[i+1]=0;
            	if (j < M-1) j++;
            }
        }

参考： 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

Comments

[grape_ll]

a[1]にアクセスしたりするのを防ぐために
if(j<M-1) j++;
としたら
ArrayIndexOutOfBoundsException
は現れなくなりました。
ありがとうございます。
しかし，直したものを提出してみたらAC,RE,WAが入り混じった結果となっていたので
どこが怪しいかを教えていただけると幸いです。
問題は以下のようになっています。
https://atcoder.jp/contests/abc129/tasks/abc129_c
よろしくお願いいたします。

[Yasumichi]

# AtCoder 使っていない人には、AC,RE,WA とか言われても分からないですよ。（用語集見たので理解はしましたが。）

逆に質問してみます。dp[i] に入る値の意味は、どういう意味と想定していますか？（一応、予想してはいますが。）

[grape_ll]

申し訳ございません。配慮が不足しておりました。
わざわざ調べていただきありがとうございます。
私の考えとしては、段数iにたどり着く経路の数を表していると想定していますが、この考えはあっていますでしょうか。
よろしくお願いします。

[Yasumichi]

最後の入力パターン

100 5
1
23
45
67
89

の出力結果が、608200469 ではなく 516971670 と誤った結果になった原因が分かりましたので追記しました。原因は、j++ していた場所でした。

[grape_ll]

理解することが出来ました！ありがとうございました！