Official
B - Arrays Editorial
by
B - Arrays Editorial
by
harurun4635
「可変長配列」の練習問題です。
Python の list や C++ の vector は標準で「可変長配列」として動作し、メモリを動的に
(必要な時に必要なだけ)確保することができます。
もし \(N \times M\) の(固定長)配列を用意しようとすると、たとえば \(L = (10^5 , 1, 1, \ldots , 1)\) のようなパターンで、\(10^5\) 行 \(10^5\) 列の二次元配列が必要となってしまいます。これは MLE となるでしょう。
しかし、可変長配列を用いて各数列を必要な長さだけ保持すれば、要素数の総和( \(L_i\) の総和)が制約から \(2 \times 10^5\) 以下であるため、メモリ内でデータを管理することができます。
詳しくは実装例を参照してください。
Python の実装例
n = int(input())
a = []
for _ in range(n):
row = list(map(int, input().split()))
a.append(row[1:]) # 必要な長さ分だけ追加すればよい
x, y = map(int, input().split())
print(a[x-1][y-1])
C++ の実装例
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<vector<int>> a(n);
for (int i=0; i<n; i++) {
int l; cin >> l;
a[i].resize(l); // 必要な長さだけ確保しておく
for (int j=0; j<l; j++) {
cin >> a[i][j];
}
}
int x, y; cin >> x >> y;
cout << a[x-1][y-1] << endl;
return 0;
}
posted:
last update:
