masakihori

Arrayは内部的に持てる要素数が決まっていてappendで場所が足りなくなったら場所を確保しなおすようになってます。この場所を確保しなおすのが重い処理なので単純にappendして行くだけだと遅くなります。予めArray#reserveCapacity(_:)で場所を確保しておけば問題ないです。

append でのバッファの確保は倍々に行われるので、バッファの allocate およびコピーの計算量がその長さに比例するとした場合、最終的に N 要素分の領域を確保するための計算量は reserveCapacity してもしなくても O(N) になります。もちろんそれでも reserveCapacity した方が定数倍速いんですが、競プロの問題は定数倍が原因で TLE になることは稀であり、成績を残すには速く解くことが重要なので、このようなケースでは reserveCapacity はほぼ必要ないと考えています。