はじめに
著者は水色コーダーで、pythonのみを用いてAtCoderに取り組んでいます。
競プロでコードを書く際に計算量がオーバーしないかは大切な指標です。
それぞれの操作の計算量については以下の記事で綺麗にまとまっています。
Pythonistaなら知っておきたい計算量のはなし
ここでは、計算量ごとに水色問題(ABCのE問題程度)まででよく使う操作をまとめました。基本的に最悪計算量で記載しています。
また、計算量がオーバーしがちな操作の対処法や代替案を記載しております。
基本的にAtCoderの問題では定数倍が原因となり計算量がオーバーすることは少ないです。
そのため同じ計算量で別の処理に書き換えるのでなく、O(N)をO(logN)にするなど、根本的な改良が求められるケースが多いです。
O(1)
基本的にこれらの操作は計算量として問題にならないです。
TLEの場合は他の操作が原因の可能性が高いです。
一般
#数値の初期化、代入、四則演算、比較
x = i
x += i
i1 == i2
#入力
x = input()
"""
正確には文字列長に比例するが、
AtCoderにおける一般的な実装でボトルネックになることは少ない印象のためここに記載。
"""
#出力
print(x)
"""
同上
"""
リスト
#初期化(要素なし)
l = []
#要素の追加
list.append(x)
#最後の要素の削除
l.pop()
#要素の出力
list[x]
#要素の代入
list[x] = i
#配列数の取得
len(list)
Set
厳密にはハッシュ値の衝突やリサイズにより最悪計算量がO(N)になりますが、
AtCoderの問題を解く上でネックとなることはほぼないのでO(1)としています。
#初期化
s = set()
#要素の追加
set.add(i)
#要素の削除
set.remove(i)
#要素の検索
i in set
辞書
setと同様に最悪計算量はO(N)ですが、ここではO(1)とします。
#初期化
d = dict()
#要素の追加
dict[i] = s
#要素の取得
dict[i]
#要素の削除
del dict[i]
dict.pop(i)
#要素の検索
i in dict
O(logN)
こちらもTLEのボトルネックになることは多くない印象です。
ただ下手に使いすぎると計算量に悪影響が出るため、O(1)の操作よりは慎重に行う必要があります。
List
#二部探索
import bisect
l = [1, 3, 4, 4, 6, 8]
print(bisect.bisect_left(l, 4)) # 2
#ヒープ操作(優先度付きキュー)
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
print(heapq.heappop(heap)) # 1
O(N)
基本的にボトルネックになる際にはこれらの操作が原因のことがほとんどです。
ただ、一般的にAtCoderでは10^8程度の計算量なら時間内に終わることが多く、Nが10^6以下ならこれらの操作が単体で問題になることは少ないです。
Nが10^10を超える場合にでO(N)の処理を行なっていないか、O(N)のループの中でO(N)の処理を行なっていないか(O^2になっていないか)などを確認しましょう。
一般
str.join(list)
"""
基本的にこの方法で出力して計算量がオーバーすることはほとんどないです。
"""
#str型の操作
s1 = "a" * N
s1 += s2
s1 == s2
"""
見落としがちですがstr型の計算量は文字列の長さに比例します。
そのため出力文字列を作成して一度に出力しようとするとTLEします。
都度出力する、join関数を使ってまとめて出力するなどしましょう。
"""
#誤り例
N = 10 ** 7
l = [str(i) for i in range(N)]
output = ""
for x in l:
output += x + " "
print(output[:-1])
#TLE
#修正例
N = 10 ** 7
l = [str(i) for i in range(N)]
print(" ".join(l))
#ループ
for i in range(1,N+1):
x += i
"""
基本的にループの内部の処理を効率できないか考えましょう。
上の場合は等差数列の公式を使うことで計算量を抑えられます。
"""
#修正例
x = (N*(N+1))//2
リスト
#配列の初期化
l = [0] * N
l = [0 for _ in range(N)]
"""
ループの度に配列を初期化するとボトルネックになりやすいです。
最初に初期化しておき、ループの内部では代入などO(1)で行える処理を記述しましょう。
"""
#誤り例 O(N^2)
for n in range(N):
l = [0] * N
#修正例 O(N)
l = [0] * N
for n in range(N):
#コピー
list.copy()
"""
値を保持しておくときは、差分のみを保持しておく方法などが一般的です。
"""
#挿入
list.insert(i,s)
"""
配列の最後に代入するappendは計算量O(1)です。
[よく使われる対処法]
1,あらかじめ要素の数や位置がわかっているとき
要素数で配列を初期化しておき適宜代入する。
2,前後関係や順序が大事な場合
ノードや双方向リストを使う。
3,範囲内の合計値や要素数を求めたい場合
SegmentTreeを使う。
4,特定の要素があるか確認したいとき
Setを使う
5,特定の要素の持つ値を取り出したいとき
辞書を使う
6,先頭の要素の追加や削除を行う
dequeを用いる
などの方法で代替する
"""
#削除
list.pop(i)
list.remove(s)
"""
最後の要素の削除ならpopを使ってO(1)で行えます。
辞書を使うことで任意の要素の削除をO(1)で行えます。
値を保持する必要がない場合はSetを用いることで簡単に実装できます。
"""
#合計、最小、最大
sum(list)
min(list)
max(list)
"""
範囲内の合計を複数回求めたい場合はSegmentTreeを用いるのが一般的です。
"""
#要素の検索
i in list
"""
要素があるかどうかを確認したいときはSetを使いましょう。
要素の位置なども必要なときは辞書のKeyに値を、Valueに要素の位置を保存することで対処できます。
"""
辞書
#コピー
dict.copy()
"""
リストと同様に差分を求めるときは差分のみどこかに保存しておくことが多いです。
"""
O(NlogN)
Nが10^6程度までならループの内部で行わなければ問題にならないです。
#ソート
l = [1, 3, 4, 4, 6, 8]
l.sort()
l2 = sorted(l)
O(N*M)
NやMの大きさによっては一度で計算量がオーバーする可能性も高いです。
慎重に実装しましょう。
#二重ループ
for i in range(N):
for j in range(M):
print(i+j)
#二次元配列
l = [[0 for _ in range(M)] for _ in range(N)]
終わりに
より最適な代替案や記述の誤り、追記した方が良い操作などありましたらコメント欄で教えていただければ幸いです。