動的配列の成長

動的配列の成長

動的配列が容量を倍増させる仕組みをシミュレートし、再確保回数とコピーされた要素数を数えます。

このチャレンジで学べること

C++ の std::vector のような動的配列は、要素を 1 つのメモリブロックに格納します。ブロックが満杯の状態で新しい要素が来ると、2 倍の大きさのブロックを確保し、既存要素をコピーして、古いブロックを解放します。

空の配列を initial_capacity の容量で開始し、pushes 個の要素を 1 つずつ追加します。各 push の前に size == capacity なら再確保します。つまり、再確保回数を 1 増やし、コピーされた要素数に現在の size を加え、容量を 2 倍にします。

dynamic_array_growth(pushes, initial_capacity) を実装してください。

pushes: 追加される要素数。

initial_capacity: 空の配列の容量。

[reallocations, copied_elements, final_capacity] を返してください。

0 ≤ pushes ≤ 10^7

1 ≤ initial_capacity ≤ 10^6

例 1

入力：
pushes = 5
initial_capacity = 1

期待される出力：
expected = [3, 7, 8]

入力：
long long pushes = 5;
long long initial_capacity = 1;

期待される出力：
std::vector<long long> expected = {3, 7, 8};

入力：
long pushes = 5;
long initial_capacity = 1;

期待される出力：
long[] expected = new long[] {3, 7, 8};

容量は、2 個目、3 個目、5 個目の要素を追加するときに 1 → 2 → 4 → 8 と増え、1 + 2 + 4 = 7 個の要素がコピーされます: [3, 7, 8].

例 2

入力：
pushes = 4
initial_capacity = 4

期待される出力：
expected = [0, 0, 4]

入力：
long long pushes = 4;
long long initial_capacity = 4;

期待される出力：
std::vector<long long> expected = {0, 0, 4};

入力：
long pushes = 4;
long initial_capacity = 4;

期待される出力：
long[] expected = new long[] {0, 0, 4};

最初のブロックに 4 個すべての要素が収まるので、再確保は発生しません: [0, 0, 4].

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

再確保は配列がいっぱいのときだけ起こります。

ヒント 2

そのたびに今ある要素がすべてコピーされ、容量が倍になります。

ヒント 3

push を 1 回ずつ再現しなくても、倍増から次の倍増へ一気に進めます。

目安の計算量

時間 O(log push 数)、追加メモリ O(1)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。