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

2021.10.09
2024.03.24
競技プログラミング
arrayAtCoderPython

はじめに

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

arrayとは

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

array --- 効率的な数値配列

array --- 効率的な数値配列

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

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

基本的な使い方

オブジェクト生成

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

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

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

array --- 効率的な数値配列

array --- 効率的な数値配列

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

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

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])

参考

Support

\ この記事が役に立ったと思ったら、サポートお願いします! /

buy me a coffee
Share

Profile

author

Masa

都内のIT企業で働くエンジニア
自分が学んだことをブログでわかりやすく発信していきながらスキルアップを目指していきます!

buy me a coffee