回答編集履歴

1

最後の入力パターンの出力結果が異なった理由を追記

2020/05/18 14:46

投稿

Yasumichi
Yasumichi

スコア1773

test CHANGED
@@ -35,3 +35,117 @@
35
35
 
36
36
 
37
37
  で a[] の要素数に関係なく j が増えていき、この例ですと `(i+1)!=a[1]` で a[1] にアクセスしようとして、`ArrayIndexOutOfBoundsException` が発生しています。
38
+
39
+
40
+
41
+ 【最後の入力パターンの出力結果が異なった理由】
42
+
43
+
44
+
45
+ `i+1==a[j]` の時が、i+1段目が壊れた床の時なので `(i+1)!=a[j]` に `j++` してしまうと壊れた床でなくても次の壊れた床の段を取得してしまいます。
46
+
47
+
48
+
49
+ なので正しくは、else ブロックで `j++` する必要があります。
50
+
51
+
52
+
53
+ ```java
54
+
55
+ dp[0]=1;
56
+
57
+ int j=0;
58
+
59
+ for(int i=0;i<N;i++){
60
+
61
+ if((i+1)!=a[j]){
62
+
63
+ if(i==0) dp[i+1]=dp[i];
64
+
65
+ else dp[i+1]=dp[i]+dp[i-1];
66
+
67
+ }
68
+
69
+ else {
70
+
71
+ dp[i+1]=0;
72
+
73
+ if (j < M-1) j++;
74
+
75
+ }
76
+
77
+ }
78
+
79
+ ```
80
+
81
+
82
+
83
+ なお、こうした場合、スキャン時の壊れた段が続く場合を考慮に入れなくても大丈夫です。
84
+
85
+
86
+
87
+ ```java
88
+
89
+ for(int i=0;i<M;i++){
90
+
91
+ a[i]=scan.nextInt();
92
+
93
+ // if(i!=0){
94
+
95
+ // if(a[i]-a[i-1]==1){
96
+
97
+ // System.out.println(0);
98
+
99
+ // return ;
100
+
101
+ // }
102
+
103
+ // }
104
+
105
+ }
106
+
107
+ ```
108
+
109
+
110
+
111
+ 例えば、4段目・5段目と壊れた床が続いていた場合、`dp[4]` と `dp[5]` はともに 0 になるため、以降、`dp[i]+dp[i-1];` の結果が常に 0 となるためです。
112
+
113
+
114
+
115
+  なお、N が 10 の 5 乗まで許されることから、dp[i+1] の計算が終わった時点で 1000000007 を超えたら、1000000007 を引く処置をしておいた方が良いかもしれません。
116
+
117
+
118
+
119
+ ```java
120
+
121
+ dp[0]=1;
122
+
123
+ int j=0;
124
+
125
+ for(int i=0;i<N;i++){
126
+
127
+ if((i+1)!=a[j]){
128
+
129
+ if(i==0) dp[i+1]=dp[i];
130
+
131
+ else dp[i+1]=dp[i]+dp[i-1];
132
+
133
+ if(dp[i+1] >= MOD) dp[i+1] -= 1000000007;
134
+
135
+ }
136
+
137
+ else {
138
+
139
+ dp[i+1]=0;
140
+
141
+ if (j < M-1) j++;
142
+
143
+ }
144
+
145
+ }
146
+
147
+ ```
148
+
149
+
150
+
151
+ 参考: [「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita](https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#3-%E5%89%B2%E3%82%8A%E7%AE%97-a--b)