コード

html
1import java.util.Scanner;
2public class TypicalStairs {
3    public static void main(String[] args){
4        Scanner scan=new Scanner(System.in);
5        int N=scan.nextInt();
6        int M=scan.nextInt();
7        int[] a=new int[M];
8        for(int i=0;i<M;i++){
9            a[i]=scan.nextInt();
10            if(i!=0){
11                if(a[i]-a[i-1]==1){
12                    System.out.println(0);
13                    return ;
14                }
15            }
16        }
17        long[] dp=new long[N+1];
18        dp[0]=1;
19        int j=0;
20        for(int i=0;i<N;i++){
21            if((i+1)!=a[j]){
22                if(i==0) dp[i+1]=dp[i];
23                else dp[i+1]=dp[i]+dp[i-1];
24                j++;
25            }
26            else dp[i+1]=0;
27        }
28        System.out.println(dp[N]%1000000007);
29    }
30}

#入力とエラーメッセージ
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行目ではないのにここでこうなってしまう理由が全く分からないです。

行動規範の内容に同意します

回答1件

ベストアンサー

java
1int M=scan.nextInt();

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

java
1        for(int i=0;i<N;i++){
2            if((i+1)!=a[j]){
3                if(i==0) dp[i+1]=dp[i];
4                else dp[i+1]=dp[i]+dp[i-1];
5                j++;
6            }
7            else dp[i+1]=0;
8        }

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

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

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

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

java
1        dp[0]=1;
2        int j=0;
3        for(int i=0;i<N;i++){
4            if((i+1)!=a[j]){
5                if(i==0) dp[i+1]=dp[i];
6                else dp[i+1]=dp[i]+dp[i-1];
7            }
8            else {
9            	dp[i+1]=0;
10            	if (j < M-1) j++;
11            }
12        }

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

java
1        for(int i=0;i<M;i++){
2            a[i]=scan.nextInt();
3//            if(i!=0){
4//                if(a[i]-a[i-1]==1){
5//                    System.out.println(0);
6//                    return ;
7//                }
8//            }
9        }

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

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

java
1        dp[0]=1;
2        int j=0;
3        for(int i=0;i<N;i++){
4            if((i+1)!=a[j]){
5                if(i==0) dp[i+1]=dp[i];
6                else dp[i+1]=dp[i]+dp[i-1];
7                if(dp[i+1] >= MOD) dp[i+1] -= 1000000007;
8            }
9            else {
10            	dp[i+1]=0;
11            	if (j < M-1) j++;
12            }
13        }

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

投稿2020/05/16 12:09

編集2020/05/18 14:46

Yasumichi

総合スコア1773

grape_ll

2020/05/16 12:33

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