公式

B - Arrays 解説 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;
}

投稿日時:
最終更新: