はじめに
Pythonの標準ライブラリであるarrayについて簡単な使い方をまとめました。また、AtCoderでarrayを利用することでACできる問題があったので、そちらも合わせて紹介していきます。
arrayとは
Pythonの標準ライブラリであるarrayは基本的にはlistと同じような振る舞いをします。しかし、arrayはlistと異なり格納できる値の型に制限があります。
array --- 効率のよい数値アレイ — Python 3.10.6 ドキュメント
docs.python.org
公式ドキュメントには特別記載されていませんでしたが、listよりinsertがはやいということがAtCoder Beginner Contest 217 D - Cutting Woodsでわかりました。
基本的な使い方
オブジェクト生成
以下のように型を指定して生成します。初期値を渡すこともできます。
import array
arr = array.array('i', [1, 2, 2, 5])型の一覧はドキュメントにあります。
array --- 効率のよい数値アレイ — Python 3.10.6 ドキュメント
docs.python.org
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.
atcoder.jp
長さ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])
