/ 
Time Limit: 0 msec / Memory Limit: 0 KiB
キーポイント
- AtCoder では標準ライブラリ以外の一部のサードパーティライブラリを利用することができる
- 利用可能なサードパーティライブラリは、コンテストページ下部のルールのページから確認可能
- 2025年10月現在の情報はこちら
- 利用可能なサードパーティライブラリとして以下のようなものがある
sortedcontainersモジュールは、二分探索できる set、キーを二分探索できる dict などのデータ構造を持つ- AtCoder Library を Python に移植したモジュールとして
ac-library-pythonモジュール,acl-cpp-pythonモジュールの 2 種類が利用可能 numpy,networkx,pulpなど、競技プログラミング以外の用途でも広く使われているライブラリも利用可能
サードパーティライブラリについて
Python では標準ライブラリ以外に、誰でも自由にライブラリを作成し公開することができます。AtCoder上では様々なライブラリがインストール済みであり利用可能ですが、自身のパソコンで実行する場合にはライブラリをインストールする必要があります。
例えばターミナルで以下のコマンドを入力することで、numpy というライブラリがインストールされを利用できるようになります。
pip install numpy
他のライブラリも同様の方法でインストールすることができます。詳細については一般的なプログラミング解説サイトを参照してください。
AtCoderで利用可能なサードパーティライブラリ
2025年10月現在 AtCoder で利用可能なサードパーティライブラリのうち、利用する機会が比較的多いものをいくつか紹介します。
sortedcontainers
以下では、 sortedcontainers で提供されているデータ構造のいくつかとその使い方について説明します。詳細な説明は公式ドキュメントを参照してください。
github: grantjenks / python-sortedcontainers
SortedSet
次のような2種類の処理を高速に行うことを考えます。
- 要素の追加・要素の削除
- x が与えられ、x 以上の最小の要素を求める
Python の標準ライブラリにはこのような処理を直接行うことができるデータ構造は存在しません。
一方、この処理を直接行うことができるデータ構造が sortedcontainers.SortedSet として提供されています。
3.02.組み込みコンテナ で紹介した set とほぼ同様の使い方ができ、4.03.heapq・bisect で紹介した bisect とほぼ同様に二分探索を行うことができます。
from sortedcontainers import SortedSet s = SortedSet([7, 3, 1, 5]) i = s.bisect_left(4) # s の要素をソートしたリストに対して bisect_left を行ったときと同じ値である 2 が返される print(s[i]) # s の要素をソートしたリストに対して添字アクセスしたときと同じ値である 5 が返される s.add(6) s.discard(5) print(s[s.bisect_left(4)]) # 6
各メソッドの計算量は、 SortedSet が内部で保持する変数 _load の値(デフォルトは 1000 )を M として、次の通りです。
- add, discard, remove などは、平均計算量 \Theta\left(M+\frac{N}{M^2}+\log N\right) です。
- 添字アクセス, bisect などは、 SortedSet に対して変更を加えずに繰り返す場合 \Theta(\log N) です。 SortedSet に対して add や remove を行いながら添字アクセス・ bisect を行う場合、平均計算量は \Theta\left(\frac{N}{M^2}+\log N\right) になります。
SortedSet は、全要素をおよそ M 個ずつに分割し、リストのリストとして保持しています。 償却計算量として表す場合、再構築にかかるコストを add, remove 側に押し付けることで、「 add, remove は償却 \Theta\left(M+\frac{N}{M^2}+\log N\right) 、 添字アクセス・bisect は償却 \Theta(\log N) 」と表すこともできます。計算量に関する詳細
要素の追加・削除の際には、二分探索により位置を特定して insert, pop をしているため、基本的には計算量は \Theta(M + \log N) となります（ただし hash が衝突する要素が与えられた場合は、通常の set と同様 \Theta(N) となります）。
要素の追加・削除によりリストのサイズが M より十分に大きく・小さくなった場合にはリストの分割・合併が行われるため、追加の計算コストとして \Theta\left(M+\frac{N}{M}\right) の時間がかかります。
また、SortedSetは添字アクセス・bisectを高速に行うための情報(各リストの要素数をもつセグメントツリー)を内部で保持していますが、リストの分割・合併が行われた際にはその情報を破棄し、次に添字アクセス・bisectが行われるタイミングで \Theta\left(\frac{N}{M}\right) かけて再構築します。このため、 SortedSet に変更を加えることなく添字アクセス・bisect を繰り返す場合にはこれらの計算量は \Theta(\log N) であり、変更を加えながら行う場合には平均 \Theta\left(\frac{N}{M^2}+\log N\right) になります。
以下に示すように、「add のあとに bisect を繰り返す」と「add しながら bisect を繰り返す」では、今回の検証条件の下、実行時間に数十パーセント程度の差が出ます。（いずれもAtCoderのコードテスト環境で実行）
実行速度検証1(addのみ)
import random from sortedcontainers import SortedSet N = 10**6 s = SortedSet() for _ in range(N): s.add(random.randint(0, 10**9))
実行時間(ミリ秒)
| N | pypy | CPython |
|---|---|---|
| 10^6 | 825 | 1607 |
| 2\times 10^6 | 1833 | 4106 |
| 3\times 10^6 | 3164 | 6902 |
実行速度検証2(addしたあとbisect)
import random from sortedcontainers import SortedSet N = 10**6 s = SortedSet() for _ in range(N): s.add(random.randint(0, 10**9)) for _ in range(N): s.bisect_left(random.randint(0, 10**9))
実行時間(ミリ秒)
| N | pypy | CPython |
|---|---|---|
| 10^6 | 1591 | 3575 |
| 2\times 10^6 | 2988 | 8073 |
| 3\times 10^6 | 4520 | >10000 |
実行速度検証3(addしながらbisect)
import random from sortedcontainers import SortedSet N = 10**6 s = SortedSet() for _ in range(N): s.add(random.randint(0, 10**9)) s.bisect_left(random.randint(0, 10**9))
実行時間(ミリ秒)
| N | pypy | CPython |
|---|---|---|
| 10^6 | 1952 | 4198 |
| 2\times 10^6 | 3888 | >10000 |
| 3\times 10^6 | 5807 | >10000 |
SortedDict
sortedcontainers ではキーを二分探索することができる SortedDict というデータ構造も提供されています。
from sortedcontainers import SortedDict
d = SortedDict({7:49, 3:9, 1:1, 5:25})
i = d.bisect_left(4) # d のキーをソートしたリストに対して bisect_left を行ったときと同じ値である 2 が返される
print(d.peekitem(i)) # d のキーと値の組をソートしたリストに対して添字アクセスしたときと同じ値である (5, 25) が返される
d[6] = 36
d.pop(5)
print(d.peekitem(d.bisect_left(4))) # (6, 36)
各操作の時間計算量は SortedSet と同様です
SortedSet と似たデータ構造を実装した他のライブラリ
SortedSet と同様の機能を提供するデータ構造のより高速な実装も存在します。競技プログラミングでは以下のライブラリがしばしば使われます。このライブラリは 2025年10月時点の AtCoder のジャッジにはインストールされていないため、利用する際には github からコードをコピーしてくる必要があります。
github :tatyam-prime / SortedSet
ac-library-python, acl-cpp-python
競技プログラミングにおいてよく使われるアルゴリズムのうちいくつかを C++ で実装したものが、AtCoder 公式から AtCoder Library(ACL) として提供されています。
AtCoder では、 ACL と同様の機能を Python 向けに実装したライブラリとして、ac-library-python, acl-cpp-python の 2 種類を利用することができます。
提供されているアルゴリズムについては ACL のページを、各ライブラリの使い方については各ライブラリのページを参照してください。これらのライブラリの使い方のテストとしては AtCoder Library Practice Contest が便利です。
競技プログラミングに限らずよく利用されるライブラリ
以下で紹介するライブラリは、競技プログラミング以外の用途で広く一般に使われているライブラリのうち、競技プログラミングにおいても利用場面があるものの例です。ライブラリの使用方法などは各ライブラリの公式ドキュメントや一般の解説サイトを参照してください。
numpy
多次元配列の操作と行列演算を効率よく行うためのライブラリです。
github : numpy / numpy
networkx
単一始点最短経路問題や最大流問題、最大重みマッチングなど、グラフに関する様々な問題を解決するためのメソッドが用意されています。
github : networkx / networkx
pulp
線形最適化問題を解くためのモデリングライブラリです。整数計画問題などを高速に解くことができます。
github : coin-or / pulp
問題
本節にはEX問題はありません。本文中にある練習問題を解いてください。