動的メモリP0202

行ごとに長さが違う表

整数を入れる表がある。
表の行ごとに入っている値の数が違うことがあり、値が一つもない行もある。
最初は行が一つもない。
行番号は 1 から数える。
命令は六種類である。
- new k v1 … vk：値 k 個が入った新しい行を表のいちばん下につける。
k は 0 のこともある。
- copy i：i 番の行と同じ値が入った新しい行を表のいちばん下につける。
そのあと二つの行は互いに関係なく別々に変わる。
- add i v：i 番の行の末尾に値 v を一つつける。
- set i j v：i 番の行の j 番目の値（1 から数える）を v に変える。
- del i：i 番の行を消す。
その下の行は番号が一つずつ繰り上がる。
- print i：i 番の行の値の数 k と値 k 個を、空白一つで区切って一行に出力する。
行が空なら 0 だけを出力する。
命令に出てくる行番号と値の位置は必ず存在する。
一行目に命令数 q、続く q 行に命令が一つずつ与えられる。
print ごとに一行ずつ出力し、最後の行に残った行の数と表全体に入っている値の数を空白一つで区切って出力せよ。
行ごとに必要なだけメモリを別々に借りて解いてみよう（C は malloc・realloc・free、C++ は std::vector<std::vector<int>>）。
copy は値が入ったブロックを新しく借りて移し、del はその行のブロックを返す。

入力: 1 ≤ q ≤ 50,000、-10⁹ ≤ v ≤ 10⁹。
new の k は全部合わせて 100,000 以下。
いつでも表の行は 5,000 個以下、表全体の値は 500,000 個以下で、copy でコピーする値は全部合わせて 500,000 個以下、print が出力する値は全部合わせて 30,000 個以下。
出力: print ごとに一行、そして最後の行に「行の数値の数」

例 1 · stdin

9
new 3 1 2 3
copy 1
set 2 1 9
add 1 4
new 0
add 3 -5
del 2
print 1
print 2

stdout

4 1 2 3 4
1 -5
2 5

main.py プログラミング言語実行バージョン

入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 2 言語の解答

この問題は C・C++ だけを受け付けます。
行ごとにメモリを自分で借りて返すのはこの二つの言語の役目で、Python・JavaScript・TypeScript・Java・C#・Craykon のリストは勝手に伸び、ガベージコレクタが片づけてくれます（それらの言語でも copy には row[:]・[...row]・new ArrayList<>(row)・new List<int>(row) のように別のコピーを作る必要があります）。
C は行ごとに int *data・長さ・容量を持つ構造体を置き、行を入れる表も Row * で借りるので、二重に借ります。
伸ばすときは realloc が返したポインタを確かめてから入れ、del は free(data) のあとに重なる場所を詰めるので memcpy ではなく memmove を使います。
表を realloc するとブロックが移ることがあるので、その前に持った &t.rows[i] のようなポインタは取り直します。
最後に行ごとに free してから表を free します。
C++ は std::vector が借りる・伸ばす・返すをすべて引き受け（RAII）、std::vector<int> dup = rows[i]; のようにコピーすると新しいブロックに値をすべて移します。
落とし穴は四つ：① C で t.rows[n] = t.rows[i]; のように構造体を代入すると data ポインタだけがコピーされ、二つの行が一つのブロックを共有します。
片方を set するともう片方も変わり、最後に同じブロックを二回 free して止まります。
② memcpy(dst, src, len) の三つ目の引数はマスの数ではなくバイト数です。
len * sizeof(int) でなければならず、len だけ渡すと前の四分の一しかコピーされません。
③ C++ の auto row = rows[i]; row.push_back(v); はコピーにつけます。
元を変えるには auto &row です。
④ C++ で row.reserve(k) のあとに row[j] に書くと、reserve は容量を増やすだけでサイズは 0 のままなので、その行は空のまま残ります。
std::vector<int> row(k) か resize(k) でマスを作ります。

C++main.cpp · 45 行

#include <iostream>#include <string>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    // 바깥 vector가 줄들을, 안쪽 vector가 줄마다 값들을 빌려 쥔다. 지워지면 알아서 돌려준다(RAII)    std::vector<std::vector<int>> rows;    int q;    std::cin >> q;    std::string cmd;    while (q--) {        std::cin >> cmd;        int i, j, k, v;        if (cmd == "new") {            std::cin >> k;            std::vector<int> row(k);  // 크기 k: 칸이 k개 생긴다(reserve는 칸을 만들지 않는다)            for (int &x : row) std::cin >> x;            rows.push_back(std::move(row));        } else if (cmd == "copy") {            std::cin >> i;            std::vector<int> dup = rows[i - 1];  // vector 복사는 새 블록을 빌려 값을 모두 옮긴다(깊은 복사)            rows.push_back(std::move(dup));        } else if (cmd == "add") {            std::cin >> i >> v;            rows[i - 1].push_back(v);        } else if (cmd == "set") {            std::cin >> i >> j >> v;            rows[i - 1][j - 1] = v;        } else if (cmd == "del") {            std::cin >> i;            rows.erase(rows.begin() + (i - 1));  // 그 줄의 블록을 돌려주고 뒤를 당긴다        } else {            std::cin >> i;            const auto &row = rows[i - 1];            std::cout << row.size();            for (int x : row) std::cout << ' ' << x;            std::cout << '\n';        }    }    long long cells = 0;    for (const auto &row : rows) cells += row.size();    std::cout << rows.size() << ' ' << cells << '\n';}

Cmain.c · 98 行

#include <stdio.h>#include <stdlib.h>#include <string.h> typedef struct {    int *data; /* 이 줄의 값들을 담으려고 빌린 블록 */    int len;   /* 들어 있는 값의 수 */    int cap;   /* 빌린 칸의 수 */} Row; typedef struct {    Row *rows;    int n, cap;} Table; /* 빌리기에 실패하면 멈춘다(받은 포인터를 확인한 다음에 담는다) */static void *grow(void *p, size_t count, size_t size) {    void *q = realloc(p, count * size);    if (q == NULL) {        fprintf(stderr, "out of memory\n");        exit(1);    }    return q;} /* 표 끝에 빈 줄 자리를 하나 만들어 그 주소를 돌려준다.   표의 블록이 옮겨질 수 있으니, 이 함수를 부르기 전에 쥔 Row 포인터는 부른 뒤에 쓰지 않는다 */static Row *append_row(Table *t, int cap) {    if (t->n == t->cap) {        t->cap = t->cap ? t->cap * 2 : 4;        t->rows = grow(t->rows, (size_t)t->cap, sizeof *t->rows);    }    Row *r = &t->rows[t->n++];    r->len = 0;    r->cap = cap > 0 ? cap : 1;    r->data = malloc((size_t)r->cap * sizeof *r->data);    if (r->data == NULL) exit(1);    return r;} static void push(Row *r, int v) {    if (r->len == r->cap) {        r->cap *= 2;        r->data = grow(r->data, (size_t)r->cap, sizeof *r->data);    }    r->data[r->len++] = v;} int main(void) {    Table t = {NULL, 0, 0};    int q, i, j, k, v;    char cmd[8];    if (scanf("%d", &q) != 1) return 0;    while (q--) {        scanf("%7s", cmd);        if (strcmp(cmd, "new") == 0) {            scanf("%d", &k);            Row *r = append_row(&t, k);            for (j = 0; j < k; j++) {                scanf("%d", &v);                push(r, v);            }        } else if (strcmp(cmd, "copy") == 0) {            scanf("%d", &i);            int len = t.rows[i - 1].len;            Row *dst = append_row(&t, len);  /* 먼저 자리를 만들고 */            const Row *src = &t.rows[i - 1]; /* 그다음 원본 주소를 쥔다 */            memcpy(dst->data, src->data, (size_t)len * sizeof *src->data); /* 바이트 수 = 칸 수 × 칸 크기 */            dst->len = len;        } else if (strcmp(cmd, "add") == 0) {            scanf("%d %d", &i, &v);            push(&t.rows[i - 1], v);        } else if (strcmp(cmd, "set") == 0) {            scanf("%d %d %d", &i, &j, &v);            t.rows[i - 1].data[j - 1] = v;        } else if (strcmp(cmd, "del") == 0) {            scanf("%d", &i);            free(t.rows[i - 1].data);            /* 뒤의 줄들을 한 칸씩 당긴다: 겹치는 자리라 memcpy가 아니라 memmove */            memmove(&t.rows[i - 1], &t.rows[i], (size_t)(t.n - i) * sizeof *t.rows);            t.n--;        } else {            scanf("%d", &i);            const Row *r = &t.rows[i - 1];            printf("%d", r->len);            for (j = 0; j < r->len; j++) printf(" %d", r->data[j]);            printf("\n");        }    }    long long cells = 0;    for (i = 0; i < t.n; i++) {        cells += t.rows[i].len;        free(t.rows[i].data); /* 줄마다 빌린 블록을 돌려주고 */    }    free(t.rows); /* 마지막으로 표의 블록을 돌려준다 */    printf("%d %lld\n", t.n, cells);    return 0;}