【AtCoder】Python標準ライブラリarrayの使い方

スポンサーリンク

はじめに

Pythonの標準ライブラリであるarrayについて簡単な使い方をまとめました。また、AtCoderでarrayを利用することでACできる問題があったので、そちらも合わせて紹介していきます。

arrayとは

Pythonの標準ライブラリであるarrayは基本的にはlistと同じような振る舞いをします。しかし、arraylistと異なり格納できる値の型に制限があります。

array --- 効率のよい数値アレイ — Python 3.10.6 ドキュメント

公式ドキュメントには特別記載されていませんでしたが、listよりinsertがはやいということがAtCoder Beginner Contest 217 D - Cutting Woodsでわかりました。

基本的な使い方

オブジェクト生成

以下のように型を指定して生成します。初期値を渡すこともできます。

import array

arr = array.array('i', [1, 2, 2, 5])

型の一覧はドキュメントにあります。

array --- 効率のよい数値アレイ — Python 3.10.6 ドキュメント

append

末尾に要素を追加します。

arr.append(8)

count

要素の出現回数をカウントします。

cnt = arr.count(2)

extend

末尾に要素をまとめて追加します。

arr.extend([3, 4, 6, 7, 8])

fromlist

listから要素を追加します。

arr.fromlist([10, 11, 12])

index

最初に見つけた要素の添字を返します。

ind = arr.index(2)

insert

指定した添字の場所に要素を追加します。

arr.insert(3, 15)

pop

指定した添字の要素を削除します。

arr.pop(3)

remove

最初に見つけた指定した要素を削除します。

arr.remove(2)

tolist

listに変換します。

li = arr.tolist()

AtCoderでのサンプル

D - Cutting Woods
AtCoderisaprogrammingcontestsiteforanyonefrombeginnerstoexperts.Weholdweeklyprogrammingcontestsonline.

長さLの木材に対して、Q個のクエリを処理する問題です。こちらの問題はbisectで二分探索して、クエリに応じてinsertもしくは長さの出力をしています。

以下のようにlistを利用すると2つのテストケースにおいてTLEになってしまいます。

import bisect

l, q = map(int, input().split())
C = []
X = []

for _ in range(q):
    c, x = map(int, input().split())
    C.append(c)
    X.append(x)

a = [0, l]

for i in range(q):
    y = bisect.bisect(a, X[i])
    if C[i] == 1:
        a.insert(y, X[i])
    else:
        print(a[y]-a[y-1])

しかし、以下のようにarrayにすると全てのテストケースにおいてACすることができます。

import array
import bisect

l, q = map(int, input().split())
C = []
X = []

for _ in range(q):
    c, x = map(int, input().split())
    C.append(c)
    X.append(x)

a = array.array('i', [0, l])

for i in range(q):
    y = bisect.bisect(a, X[i])
    if C[i] == 1:
        a.insert(y, X[i])
    else:
        print(a[y]-a[y-1])

参考

タイトルとURLをコピーしました