動的メモリP0158

二倍に伸びる配列

整数を入れる伸びる配列を自分で作る。
配列は要素の数（サイズ）と、メモリを借りておいたマスの数（容量）を別々に持つ。
最初はサイズが 0、容量が 1 である。
命令は四つある。
- push x：サイズが容量と同じなら、まず容量を 2 倍に増やしてから（増やし 1 回）、末尾に x を入れる。
- pop：空なら empty を出力する。
そうでなければ末尾の値を取り出して出力し、そのあと容量が 2 以上で、サイズ×4 が容量以下なら容量を半分に減らす（減らし 1 回）。
- get i：0 から数えて i 番目の値を出力する。
i がサイズ以上なら out of range を出力する。
- info：サイズと容量を空白一つで区切って出力する。
一行目に命令数 q、続く q 行に命令が一つずつ与えられる。
命令ごとに上の出力を一行ずつ行い、最後の行に「grow 増やした回数 shrink 減らした回数」を出力せよ。
info が出力する容量は、いつも上の規則で決まる値である。
C は realloc で借りたブロックの大きさを変え、C++ は容量を変数で自分で数えながら、std::vector の reserve でその分を前もって借りてみよう。

入力: 1 ≤ q ≤ 100,000、-1,000,000,000 ≤ x ≤ 1,000,000,000、0 ≤ i ≤ 100,000（整数）
出力: push 以外の命令ごとに一行、最後の行に「grow G shrink S」

例 1 · stdin

9
push 4
push 8
push 15
info
get 2
pop
pop
info
get 1

stdout

3 4
15
15
8
1 2
out of range
grow 2 shrink 1

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

入力(stdin)

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

$ 準備完了

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

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

この問題は C・C++ だけを受け付けます。
借りておくマスの数を自分で決めて移し替えるのはこの二つの言語の仕事で、Python list・JS の配列・Java ArrayList・C# List<T>・Craykon のリストは自動で伸びます（OpenJDK の Java ArrayList は 1.5 倍、.NET の C# List<T> は 2 倍のように、実装ごとに倍率が違います）。
C では realloc(p, newcap * sizeof *p) がブロックを伸ばしたり縮めたりし、その場で伸ばせなければ新しい場所へ移し替えて新しいアドレスを返します。
失敗すると NULL を返し古いブロックはそのままなので、v->data = realloc(v->data, ...) のようにすぐ上書きすると古いブロックを失います。
受け取ったポインタを別に確かめてから入れます。
C++ の std::vector もサイズ size() と容量 capacity() を別々に持ち、reserve(n) で前もって広げます。
ただし標準が約束するのは reserve(n) のあと容量が n 以上であることだけで、push_back が自分で増やす倍率も標準ライブラリごとに違います（libstdc++・libc++ は 2 倍、MSVC は 1.5 倍）。
そこで C++ の解答はこの問題の容量を変数 cap で自分で数え、reserve(cap) で少なくともその分を借りておきます。
二倍ずつ増やすと移し替えがまれになり、push 一回の費用は平均 O(1) です。
落とし穴は四つ：① 1 マスずつ増やすと push のたびに移し替えて全体で O(q²) になり、容量もこの問題の答えと違ってきます。
② サイズが容量の半分になった時点で減らすと、境目で push・pop を行き来するたびに増やしと減らしを繰り返します。
1/4 まで待ってから半分に減らせば、減らしたあとも半分が空いています。
③ C++ で容量を自分で数えずに capacity() をそのまま信じると、減らすところで誤ります。
reserve は容量を減らせず、今より小さい値を渡すと何もしません。
本当にマスを返すには、半分を reserve した新しい vector に移し替えて swap します。
shrink_to_fit() はサイズにぴったり合わせようとする（必ず守られるとは限らない）要求で、半分に減らすものではありません。
④ std::vector<int> v(1) はマスを一つ借りるのではなく、0 の入った要素を一つ作ります。
空のままマスだけ借りるなら v.reserve(1) です。

C++main.cpp · 53 行

#include <iostream>#include <string>#include <vector> int main() {    std::ios::sync_with_stdio(false);    // 용량은 이 문제의 규칙대로 직접 센다.    // capacity()가 돌려주는 값은 표준 라이브러리마다 다를 수 있다(reserve(n) 뒤에는 n 이상이라는 것만 약속된다).    std::size_t cap = 1;    std::vector<int> v;    v.reserve(cap);  // 크기(size)는 0인 채로 적어도 cap칸을 빌려 둔다    int grow = 0, shrink = 0;    int q;    std::cin >> q;    std::string cmd;    for (int i = 0; i < q; i++) {        std::cin >> cmd;        if (cmd == "push") {            int x;            std::cin >> x;            if (v.size() == cap) {  // 가득 찼으면 두 배로: 늘리는 때를 직접 정한다                cap *= 2;                v.reserve(cap);                grow++;            }            v.push_back(x);  // capacity()가 cap 이상이라 여기서는 다시 옮겨 담지 않는다        } else if (cmd == "pop") {            if (v.empty()) {                std::cout << "empty\n";                continue;            }            std::cout << v.back() << '\n';            v.pop_back();  // 크기만 줄고 빌린 칸은 그대로다            if (cap > 1 && v.size() * 4 <= cap) {                cap /= 2;                // reserve는 칸을 줄이지 못한다: 반만큼 빌린 새 vector에 옮겨 담고 맞바꾼다                std::vector<int> smaller;                smaller.reserve(cap);                smaller.assign(v.begin(), v.end());                v.swap(smaller);                shrink++;            }        } else if (cmd == "get") {            std::size_t k;            std::cin >> k;            if (k < v.size()) std::cout << v[k] << '\n';            else std::cout << "out of range\n";        } else {            std::cout << v.size() << ' ' << cap << '\n';        }    }    std::cout << "grow " << grow << " shrink " << shrink << '\n';}

Cmain.c · 68 行

#include <stdio.h>#include <stdlib.h>#include <string.h> /* 직접 만든 늘어나는 배열: data는 cap칸을 빌려 두고, 앞의 size칸만 쓴다 */typedef struct {    int *data;    int size, cap;    int grow, shrink;} IntVec; /* 칸 수를 newcap으로 바꾼다. realloc은 자리를 옮길 수 있어서 돌려받은 포인터를 쓴다 */static void resize(IntVec *v, int newcap) {    int *p = realloc(v->data, (size_t)newcap * sizeof *p);    if (p == NULL) {             /* 실패하면 옛 블록은 그대로 남아 있다 */        free(v->data);        exit(1);    }    v->data = p;    v->cap = newcap;} static void push(IntVec *v, int x) {    if (v->size == v->cap) {     /* 가득 찼으면 두 배로: 옮겨 담기가 드물어진다 */        resize(v, v->cap * 2);        v->grow++;    }    v->data[v->size++] = x;} /* 빈 배열이면 0, 아니면 *out에 마지막 값을 꺼내고 1 */static int pop(IntVec *v, int *out) {    if (v->size == 0) return 0;    *out = v->data[--v->size];    if (v->cap > 1 && v->size * 4 <= v->cap) {  /* 1/4 이하로 줄면 반으로 */        resize(v, v->cap / 2);        v->shrink++;    }    return 1;} int main(void) {    IntVec v = { NULL, 0, 0, 0, 0 };    resize(&v, 1);               /* 처음에 한 칸 빌려 둔다 */    int q;    scanf("%d", &q);    for (int i = 0; i < q; i++) {        char cmd[8];        int x;        scanf("%7s", cmd);        if (strcmp(cmd, "push") == 0) {            scanf("%d", &x);            push(&v, x);        } else if (strcmp(cmd, "pop") == 0) {            if (pop(&v, &x)) printf("%d\n", x);            else puts("empty");        } else if (strcmp(cmd, "get") == 0) {            scanf("%d", &x);            if (x < v.size) printf("%d\n", v.data[x]);            else puts("out of range");        } else {            printf("%d %d\n", v.size, v.cap);        }    }    printf("grow %d shrink %d\n", v.grow, v.shrink);    free(v.data);                /* 빌린 블록은 마지막에 한 번 돌려준다 */    return 0;}