AtCoder ABC166-B

Question

AtCoder ABC166-B

https://atcoder.jp/contests/abc166/tasks/abc166_b

この問題でWAとREというエラーメッセージが出ました。
解決法を教えてください。よろしくお願いします。

発生している問題・エラーメッセージ

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long INF = 1LL << 60;

int main()
{
  int N, K;
  cin >> N >> K;
  vector<int> d(K);
  vector<vector<int>> A(K, vector<int>(K));
  rep(i,K)
  {
    cin >> d[i];
    rep(j, d[i])
    {
      cin >> A[i][j];
    }
  }
  vector<bool> have(N,false);
  rep(i,K) rep(j,K)
  {
    have[A[i][j]] = true;
  }
  
  int res = 0;
  rep(i,N)
  {
    if(!have[i]) res++;
  }
  cout << res << endl;
}

考え

まずboolの配列haveをfalseで初期化しました。
次に配列Aに登場する数字番目の要素をtrueにしました。
最後にfalseの数を数え上げて、答えとしました。

Answer 1

vector<vector<int>> A(K, vector<int>(K));
が原因で、2番目の K は本来であれば、d_iである必要があり、配列外参照が起こっています。

簡単な解決方法としては、
vector<vector<int>> A(K, vector<int>(N));
にすれば良いと思います。

また、have[A[i][j]] = true;も配列外参照が起こるとおもうので、
have[A[i][j] - 1] = true;にする必要があります。

Comments

[yuki23]

A[i][j] - 1 にすると A[i][j] == 0 のときに配列外参照してしまうので、Aを固定長にするのはダメです

[minaminao]

> A[i][j] - 1 にすると A[i][j] == 0 のときに配列外参照してしまう
A[i][j] の制約は 1~N じゃないですか？

[minaminao]

A[i][j] == N のときに、have[A[i][j]] が have[N] になって配列外参照するように見えます…

[yuki23]

入力値の範囲はそうですが、d[i] <= N は毎回異なります。入力されていないところは初期値の0になってしまいます。

[minaminao]

加えて、rep(i,K) rep(j,K) を rep(i,K) rep(j,d[i]) にしてください

[Ryuking885]

探索範囲など、もろもろ間違えていましたが、解決しました。
ありがとうございました。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long INF = 1LL << 60;

int main()
{
int N, K;
cin >> N >> K;
vector<int> d(K);
vector<vector<int>> A(K, vector<int>(N));
rep(i,K)
{
cin >> d[i];
rep(j, d[i])
{
cin >> A[i][j];
}
}

vector<bool> have(N,false);
rep(i,K) rep(j, d[i])
{
have[A[i][j]] = true;
}

int res = 0;
for(int i = 1; i <= N; i++)
{
if(!have[i]) res++;
}
cout << res << endl;
}