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

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

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

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

Q&A

解決済

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

Propromp
Propromp

総合スコア1

C++

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

1回答

0グッド

0クリップ

315閲覧

投稿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 }

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答1

1

ベストアンサー

ここで、配列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

総合スコア1769

Propromp❤️を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

Propromp

2022/12/04 11:16

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

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

ただいまの回答率
86.02%

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

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

質問する

関連した質問

同じタグがついた質問を見る

C++

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