質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

742閲覧

C++で配列の初期化処理をするタイミングにより実行結果が異なる

Propromp

総合スコア1

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2022/12/04 10:34

競技プログラミングの鉄則という本を購入し、競技プログラミングの勉強をしている者です。
このリンク先の例題を解いていたところ、謎の現象に遭遇しました。
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_i
この2つの提出結果をみていただければわかると思いますが、配列Zの初期化処理をする位置を入れ替えるだけで本来ACになるはずの所がWAになってしまいます。なぜでしょうか?
https://atcoder.jp/contests/tessoku-book/submissions/37017661
https://atcoder.jp/contests/tessoku-book/submissions/37017657

該当のソースコード

ACになるコード

C++

1 #include <iostream> 2   3 using namespace std; 4   5 int H, W; 6 int N; 7 int A[100001], B[100001], C[100001], D[100001]; 8 int X[1501][1501], Z[1501][1501]; 9   10 int main() { 11 cin >> H >> W >> N; 12 for (int i = 1; i <= N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i]; 13   14   15   16 // 各日について加算 17 for (int t = 1; t <= N; t++) { 18 X[A[t]][B[t]] += 1; 19 X[A[t]][D[t] + 1] -= 1; 20 X[C[t] + 1][B[t]] -= 1; 21 X[C[t] + 1][D[t] + 1] += 1; 22 } 23 24 //初期化処理 25 for(int i = 0; i <= H; i++) { 26 for(int j = 0; j <= W; j++) { 27 Z[i][j] = 0; 28 } 29 } 30   31 for (int i = 1; i <= H; i++) { 32 for (int j = 1; j <= W; j++) Z[i][j] = Z[i][j - 1] + X[i][j]; 33 } 34 for (int j = 1; j <= W; j++) { 35 for (int i = 1; i <= H; i++) Z[i][j] = Z[i - 1][j] + Z[i][j]; 36 } 37   38 for (int i = 1; i <= H; i++) { 39 for (int j = 1; j <= W; j++) { 40 if (j >= 2) cout << " "; 41 cout << Z[i][j]; 42 } 43 cout << endl; 44 } 45 return 0; 46 }

WAになるコード

C++

1 #include <iostream> 2   3 using namespace std; 4   5 int H, W; 6 int N; 7 int A[100001], B[100001], C[100001], D[100001]; 8 int X[1501][1501], Z[1501][1501]; 9   10 int main() { 11 cin >> H >> W >> N; 12 for (int i = 1; i <= N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i]; 13   14 //初期化処理 15 for(int i = 0; i <= H; i++) { 16 for(int j = 0; j <= W; j++) { 17 Z[i][j] = 0; 18 } 19 } 20   21 // 各日について加算 22 for (int t = 1; t <= N; t++) { 23 X[A[t]][B[t]] += 1; 24 X[A[t]][D[t] + 1] -= 1; 25 X[C[t] + 1][B[t]] -= 1; 26 X[C[t] + 1][D[t] + 1] += 1; 27 } 28   29 for (int i = 1; i <= H; i++) { 30 for (int j = 1; j <= W; j++) Z[i][j] = Z[i][j - 1] + X[i][j]; 31 } 32 for (int j = 1; j <= W; j++) { 33 for (int i = 1; i <= H; i++) Z[i][j] = Z[i - 1][j] + Z[i][j]; 34 } 35   36 for (int i = 1; i <= H; i++) { 37 for (int j = 1; j <= W; j++) { 38 if (j >= 2) cout << " "; 39 cout << Z[i][j]; 40 } 41 cout << endl; 42 } 43 return 0; 44 }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

ここで、配列Xの範囲外に書き込んでいるのが原因だと思われます。

c++

1 // 各日について加算 2 for (int t = 1; t <= N; t++) { 3 X[A[t]][B[t]] += 1; 4 X[A[t]][D[t] + 1] -= 1; 5 X[C[t] + 1][B[t]] -= 1; 6 X[C[t] + 1][D[t] + 1] += 1; 7 }

例えば、以下の入力の場合

text

11500 1500 1 21 1 1500 1500

このような処理になります。

c++

1 X[1][1] += 1; 2 X[1][1500 + 1] -= 1; 3 X[1500 + 1][1] -= 1; 4 X[1500 + 1][1500 + 1] += 1;

int X[1501][1501]と定義されているので、Xのインデックスは縦横最大1500までですが、これでは1501番目の要素に書き込んでしまうことになります。
その結果、たまたま隣にあったZの値が書き換わってしまったのでしょう。
この処理の後にZを初期化した場合は、Zに入れてしまった値がリセットされ、たまたま正常動作したようにみえたのでしょう。

投稿2022/12/04 11:08

編集2022/12/04 11:09
actorbug

総合スコア2212

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Propromp

2022/12/04 11:16

わかり易い回答ありがとうございます!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問