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

2021.10.09

2024.03.24

競技プログラミング

arrayAtCoderPython

はじめに

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

arrayとは

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

array --- 効率のよい数値アレイ

このモジュールでは、基本的な値 (文字、整数、浮動小数点数) のアレイ (array、配列) をコンパクトに表現できるオブジェクト型を定義しています。アレイはシーケンス (sequence) 型であり、中に入れるオブジェクトの型に制限があることを除けば、リストとまったく同じように振る舞います。オブジェクト生成時に一文字の型コードを用いて型を指定します。次の型コードが定義されています:,,...

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

基本的な使い方

オブジェクト生成

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

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

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

array --- 効率のよい数値アレイ

append

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

1arr.append(8)

count

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

1cnt = arr.count(2)

extend

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

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

fromlist

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

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

index

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

1ind = arr.index(2)

insert

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

1arr.insert(3, 15)

pop

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

1arr.pop(3)

remove

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

1arr.remove(2)

tolist

listに変換します。

1li = arr.tolist()

AtCoderでのサンプル

D - Cutting Woods

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

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

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

1import bisect
2
3l, q = map(int, input().split())
4C = []
5X = []
6
7for _ in range(q):
8    c, x = map(int, input().split())
9    C.append(c)
10    X.append(x)
11
12a = [0, l]
13
14for i in range(q):
15    y = bisect.bisect(a, X[i])
16    if C[i] == 1:
17        a.insert(y, X[i])
18    else:
19        print(a[y]-a[y-1])

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

1import array
2import bisect
3
4l, q = map(int, input().split())
5C = []
6X = []
7
8for _ in range(q):
9    c, x = map(int, input().split())
10    C.append(c)
11    X.append(x)
12
13a = array.array('i', [0, l])
14
15for i in range(q):
16    y = bisect.bisect(a, X[i])
17    if C[i] == 1:
18        a.insert(y, X[i])
19    else:
20        print(a[y]-a[y-1])