AtcoderのABC355 B問題を解く際、正解するためには効率的なアルゴリズムを使うことが重要ですが、時には意図しない動作を引き起こすことがあります。この記事では、特定のコードがなぜWA（Wrong Answer）となるのかを解析し、その原因と修正方法を詳しく解説します。質問者が投稿したコードについても触れながら、問題を解決する方法を考えます。
1. 問題の概要
AtcoderのABC355 B問題では、数列Aから数値が入力され、ある条件に基づいて「Yes」または「No」を出力する問題です。質問者は、数列Aの要素をbool型の配列に格納し、隣接する数をチェックして解こうとしました。しかし、1つのテストケースでWAが発生してしまいました。そこで、このコードが失敗する原因を探っていきます。
2. 提出されたコードの解説
質問者のコードは、与えられた数列Aを使って、隣接する要素があるかを確認するものです。具体的には、入力された値を配列Aに格納し、隣接する値（v-1、v+1）がすでに存在するかをチェックします。条件に合う場合、「Yes」を出力し、条件に合わなければ「No」を出力します。
ここまで見ると、アルゴリズムとしては直感的に理解できるものです。しかし、特定のケースでこのコードがWAを返す理由を考える必要があります。
3. WAの原因と解析
このコードのWAの原因は、隣接の要素を正しく扱えていないことにあります。具体的には、入力される数値が1や最大値に近い場合に、配列のインデックス範囲外にアクセスしてしまう恐れがあります。例えば、最小値vが1の場合、v-1（0番目のインデックス）は配列に存在しませんし、最大値に近い場合、v+1が配列外のインデックスになる可能性があります。この問題を避けるために、範囲外アクセスを防ぐ処理を追加することが重要です。
4. 修正方法
この問題を解決するためには、v-1やv+1の値が配列のインデックスとして有効かどうかを確認する必要があります。具体的には、配列Aのサイズを超えるインデックスへのアクセスを防ぐため、次のような修正を加えます。
- v-1が0以上かつv+1が配列Aのサイズ以下であることを確認
- 範囲外アクセスを避けるため、配列Aのサイズを適切に設定
修正後のコード例。
#include
int main(){
int N, M;
std::cin >> N >> M;
std::vector A(203, false);
for (int i = 0; i < N; i++){
int v; std::cin >> v;
A[v] = true;
if ((v > 0 && A[v-1]) || (v < 202 && A[v+1])){
std::cout << "Yes" << std::endl;
return 0;
}
}
std::cout << "No" << std::endl;
}
この修正により、インデックスの範囲外アクセスを防ぎ、WAを解決することができます。
まとめ
AtcoderのABC355 B問題では、隣接する要素をチェックする際に、配列のインデックス範囲外にアクセスしてしまうことが原因でWAが発生しました。修正方法としては、範囲外アクセスを防ぐために、v-1やv+1が有効なインデックスであるかを確認することが重要です。これにより、WAを解決し、正しい結果を得ることができます。
コメント