0.はじめに
2020年の5月よりAtcoderのコンテストに参加してから一年経った、現在水色コーダーとなりました、H20と申します。
AtCoderではPythonを使用して参加しており、水色になるまでに様々なアルゴリズムを使用しました。
アルゴリズムについてはほとんど自作せず、有識者の作成されたスニペットを調べては、ある程度理解しながら使用していました。
この記事では、Pythonにてあるアルゴリズムを使用する際にお勧めな書き方の説明をしているスニペットの記事に、それを利用してACしたコードを添えて紹介していきたいと思います。
（ただ、私のACコードは極力見ないで自力で解いてください。綺麗とは言い難いので…）
1.目次
※各アルゴリズムで紹介している問題は、感覚的な難易度順に並べています。基本的に後半は解けたら凄い！くらいの想いで載せてます。
解き方は多種多様であり、特に難易度の低い問題では、必ずしもそのアルゴリズムを使わないといけないわけではありません。
提出については特殊な事情がない限り、Pypy(AtCoder上でのPyPy3 (7.3.0))を使用してください。
Python (3.8.2)よりPyPy3 (7.3.0)の方が基本的に速度が速いです。（参考）
紹介した問題には、私のACコードでPython (3.8.2)による提出をした場合にTLEする問題が含まれています。
●除算の切り上げ、切り下げ
●約数列挙
●素因数分解
●エラトステネスの篩
●BIT全探索
●Union-Find
●重み付きunion-find
●クラスカル法（最小全域木）
●リスト（配列）の中身を連結・結合して文字列に
●多次元配列のソート
●defaultdict（辞書）
●カウンター
●ModInt
●逆元
●階乗
●コンビネーション
●ある値の累乗の何度も使用する場合
●最大公約数
●中国剰余定理
●DFS
●メモ化再帰
●二分探索（bisect）
●二分探索（その他）
●最長増加部分列（LIS）
●累積和（合わせて、いもす法）
●短めな順列の作成
●二次元累積和
●ダイクストラ法
●ワーシャルフロイド法
●セグメント木（セグ木）
●転倒数
●桁DP
●ダブリング
●最長共通部分列
●BitDP
●10進数を2進数、8進数、16進数に変換
●10進数とn進数の変換
●正規表現
●キュー
●優先度付きキュー
●しゃくとり法
●ベルマンフォード法
●平衡二分探索木
●Mo's Algorithm
●おすすめな情報
●アルゴリズムを使用するにあたって
●おわりに
●よければのお話
2.除算の切り上げ、切り下げ
リンク：割り算をするときの切り上げと切り捨て
Pythonの切り捨てとして、処理が高速かつ短く書けるコードです。mathをimportする必要はありません。
Pythonでの切り捨て除算は除算値を超えない最大の整数となるため、値をマイナスにして、さらにマイナスを掛けることで、切り上げの値を取得できます。
慣れれば、切り上げもそらで書けるようになるはずです。
# 整数A,BについてA/Bの切り捨てを求める書き方
F = A // B
# 整数A,BについてA/Bの切り上げを求める書き方
C = -(-A // B)
老婆心ながら、小数点を求めたい場合でない除算については/ではなく切り捨て除算の//演算子を使用しましょう。
詳細については以下の記事が参考になると思います。
切り捨てはmath.floor()より//演算子を使ったほうが良いかも
pythonの除算結果が浮動小数点数になったので、必要な精度が失われた話
問題：
ABC176 A Takoyaki - 【ACコード】
ABC195 B Many Oranges - 【ACコード】
ABC046 C AtCoDeerくんと選挙速報 - 【ACコード】
3.約数列挙
リンク：約数を高速で列挙するコード(Python)
問題によってはそのまま貼るだけだったことも。
計算量が $O(\sqrt{N})$ となるため、制約の$N$が$10^{12}$までなど大きな値をとる場合にはまず約数を疑ってかかるのも手です。
問題：
ABC180 C Cream puff - 【ACコード】
MojaCoder Polygon of Polygons - 【ACコード】
ABC112 D Partition - 【ACコード】
ABC190 D Staircase Sequences - 【ACコード】
diverta 2019 D - DivRem Number - 【ACコード】
(expert!) ARC108 A Sum and Product - 【ACコード】
アルゴリズムを理解して、その処理を応用する解法の問題にも対応できるようになっておきましょう。
4.素因数分解
リンク：Pythonで素因数分解（試し割り法）
note.nkmk.meさんのサイトより。皆さんご存じだとは思いますがこのサイトは、紹介しきれないくらいのいい記事がたくさんありますので、ググって見つかったらまず参考にしています。
他のアルゴリズムでもこのサイトを紹介しているものがあります。
問題：
MojaCoder 楔数（くさびすう） - 【ACコード】
ABC169 D Div Game - 【ACコード】
ABC177 E Coprime - 【ACコード】
ABC152 F Flatten - 【ACコード】
若干難しくなりがちなので、素因数分解を使用すれば解けると気づけたときはレートアップのチャンスですね。
最初の楔数の問題は拙作です。ABCのCで出る灰色問題を想定しました。作問後、解いた方から別のアルゴリズムを使用して、制約が $1 \leq N \leq 10^8$ あたりでもTLEせずに、とても効率よく解く方法を教えてもらいました。ここで紹介しているアルゴリズムを複数使用します。解法は記載しませんが、皆さんは気づきますでしょか？ この制約の場合水色以上の難易度だと思います。
5.エラトステネスの篩
リンク：Pythonで競技プログラミング 〜基本的なアルゴリズム 〜（エラトステネスの篩）
$N$までの素数の一覧を作成するには $\sqrt{N}$ まで確認すればよいです。
引数$N$までについてis_primeではその値が素数かどうか、tableでは素数である値の一覧の二つの情報が返却されるところが好きです。
元のコードでのis_primeは整数1からNまでのテーブルとなるので、インデックスで混乱しやすいこともあり、is_primeを使用する場合は、先頭にFalse（0）を追加して返却するように書き換えて使用しています。
問題：
天下一プログラマーコンテスト2012 予選C A - 【ACコード】
ABC149 C Next Prime - 【ACコード】
(expert!) ABC170 D Not Divisible - 【ACコード】
天下一プログラマーコンテスト2012 予選Aの問題についてPypyで解くとMLE(メモリオーバー)するので、Pythonで提出してください。
古い問題のためメモリ制限が64MBで、Pypyで提出するとオーバーしてしまいます。
6.BIT全探索
リンク：Python de アルゴリズム（bit全探索）
$2^N$のパターンを全て試す際に使います。制約の中に10~20前後（またはそれに落とし込める）の値があれば、BIT全探索を使用する問題の可能性が高いです。
問題探るとC問題に結構出やすいことに気付きました。頻出なので、これを簡単に使えるようになっていないと辛い時が来ると思います。
問題：
ABC167 C Skill Up - 【ACコード】
ABC182 C To 3 - 【ACコード】
ABC190 C Bowls and Dishes - 【ACコード】
ARC114 A Not coprime - 【ACコード】
ABC197 C ORXOR - 【ACコード】
ABC128 C Switches - 【ACコード】
ABC147 C HonestOrUnkind2 - 【ACコード】
ABC104 C All Green - 【ACコード】
7.Union-Find
リンク：PythonでのUnion-Find（素集合データ構造）の実装と使い方
それぞれ、素な集合を互いにくっつけていった後の状態を管理するのに使用します。
作り方によっては外すこともできるらしいですが、あまり詳しくないです。基本的にできるのは、くっつけるだけと思って構いません。
ARCの問題、または、友達関係を表す問題で出やすいです。
ACLに同機能のDSUがありますが、個人的には上記リンク先の内容の方に慣れてしまっているため、こちらの方が好きです。
少し古い話になりますが、上記リンク先はARC106の後の2020年10月25日にアップデートがありました。
all_group_members()の処理が最適化されています。
それ以前に入手された方は最新のものを使用しましょう。
all_group_members()は全グループについて要素をまとめたリストを$O(N)$ で取得できます。
#クラス部分の記述は省略
N = 10000
uf = UnionFind(N)
#全グループについて要素をまとめたリストが欲しい場合
#推奨する書き方
GM = uf.all_group_members()
for L in GM.values():
#そのリストLについて処理
pass
#場合によってTLEしてしまう書き方、競プロではやってはいけない書き方
roots = uf.roots()
for r in roots:
L = uf.members(r)
#そのリストLについて処理
全グループについて要素をまとめたリストを取得する際に、rootsとmembersを組み合わせて取得する処理はやってはいけません。
テストケースに必ず含まれるような全てがくっついていないパターンにて、計算量は最悪の$O(N^2)$となり、TLEをしてしまいます。
処理速度の差を実際に比べてみてください。
問題：
ABC177 D Friends - 【ACコード】
ACL Beginner Contest C - 【ACコード】
yukicoder No.1390 Get together - 【ACコード】
ARC106 B Values - 【ACコード】
MojaCoder Bonsai - 【ACコード】
ARC114 B Special Subsets - 【ACコード】
ABC157 D Friend Suggestions - 【ACコード】
ABC120 D Decayed Bridges - 【ACコード】
ARC111 B Reversible Cards - 【ACコード】
ABC183 F Confluence - 【ACコード】
Confluenceを解く場合は、dictの知識が必要です。defaultdictの章も参考になると思います。ちなみに、カウンターを使用するとTLEしました。
追記： コメントでご指摘をいただきました。Counterを使用してもACします。話が逸れるのでTLEしてしまった詳細についてはカウンターの追記を参照ください。
7.1重み付きUnion-Find
リンク：Python:重み付きUnion-Find木について
重み付きUnion-Findを使用する問題と参考となるスニペットがあったため、気になった方は確認してみてください。
結合しているグループ内で相対的な重みの情報を確認することができます。「重み」では分かりにくいため、ポテンシャル付きUnion-Findという言い回しの方がいいのではという話もあるようです。
問題の難易度が高くなるためリンクの貼り付けだけに留めます。
問題：
ABC218 F Pay or Receive - 【ACコード】
8.クラスカル法（最小全域木）
リンク：Prim法とKruskal法をPython 3で実装してみた：無向グラフの最小全域木を求めるアルゴリズム
説明が分かりやすいリンクを載せましたが、↓のACコードはUnion-Findで紹介したスニペットを使用して書いてます。
最小全域木は、全域木を構成する辺のコストの総和が最小となるグラフのことです。それを求める有名なアルゴリズムの一つがクラスカル法です。
600点以上の難しい問題で解法のためにこの方法プラスαで使わないと解けない、という問題が出るらしいです。が、そういうのは解いたことなく…
恐らく簡単な問題でこのアルゴリズムを使う問題が出るとすると、言い換えると最小全域木となる問題だった、というのが出るのかなと。
未だAtCoderのコンテスト本番で出会った経験はないのですが...作問する側にとって作りにくい問題な気もします。
最小全域木の問題を解くアルゴリズムはクラスカル法のほかにプリム法がありますが、どちらか片方だけ覚えればよいです。
Union-Findを使えるようになれば、クラスカル法も簡単に使えますので、プリム法は覚えなくてよいかなと思います。
Union-Findで挙げたある問題にについて、こちらに載せるとただのネタバレとなるため上記問題に入れました。その問題について、正しくは最小全域木の問題です。
問題：
いろはちゃんコンテスト Day2 D - 【ACコード】
ABC218 E Destruction - 【ACコード】
ABC065 D Built? - 【ACコード】
多次元配列のソートの章も参照ください。
9.リスト（配列）の中身を連結・結合して文字列に
それといった参考元が見つからず、そのまま以下にスニペットを貼りました。
文字列などをリスト化して編集した後、それをまた文字列の形式に戻します。
文字列を文字列として扱うよりは、リスト化した方が値をいじりやすく、使う機会は多いと思われるスニペットです。
L = list(input())
#中略(要素に対して色々と書き換えを行う)
print(''.join(map(str, L)))
#空白区切りで出力する場合→ print(' '.join(map(str, L)))
#カンマ区切りで出力する場合→ print(','.join(map(str, L)))
天下一プログラマーコンテスト2012 予選A B - 【ACコード】
ARC039 A A - B problem - 【ACコード】
ABC192 Kaprekar Number - 【ACコード】
ABC137 C Green Bin - 【ACコード】
ABC199 C IPFL - 【ACコード】
ABC137 Cについて、順番前後しますが、カウンターの章も参照のことお願いします。
10.多次元配列のソート
リンク：【Python】2次元配列を二番目の要素に注目して降順にソートする
いくつかのパターンを覚えるのではなく、配列の要素の二番目を降順でソートするスニペットを持っておけば、そのスニペットの応用で、たいていのソートを悩まず扱えるはずです。
L = [[1,2,3],[2,3,4],[3,4,5]]
L = sorted(L, reverse=True, key=lambda x: x[1]) #[1]に注目して降順ソート
print(*L)
複数キーのソート方法については↓です。
多重キーでのソート
ただ私は、優先度の低いキー順にソートを複数回実行する方法でソートしています。その分処理に時間かかるのであんまりよくはないのですが…
sort()は元のリストをソートし、sorted()はソートした新たなリストを生成します。
sort()の方が高速です。（参考）
昇順、降順がどちらの順に並ぶか混乱するときは、階段を昇っていく、降りていくをイメージすると迷わなくなります。
階段は1段目→2段目→3段目...と昇り、昇順は1→2→3と並べる、とイメージすると覚えやすいです。
補足として、二次元配列を使う場合の宣言（初期化）の書き方もおいておきます。（参考）
L = [[0] * 4 for i in range(3)]
# [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
問題：
ABC128 B Guidebook - 【ACコード】
キーエンス プログラミング コンテスト 2020 B Robot Arms - 【ACコード】
ABC113 C ID - 【ACコード】
11.defaultdict（辞書）
リンク：Python defaultdict の使い方
辞書型です。dict を使用した場合、存在しないキーに代入しようとするとエラーとなるため、その分岐処理の煩わしさを解消すべく、defaultdictを使います。
ただリストを用意すれば解ける問題に、defaultdictを使ったとしても、それが原因でTLEに繋がることはまずないため、バンバン使ってもいいと思います。（keyにタプルを使用し、そのキーの数が相当数になる場合は別…）
また、これがあるおかげで、通常のdictはあまり使用していないです。周りの人がどうかはちょっと詳しくないですが。
累積和の章にもdefaultdictを使用する問題を記載してますので、それも解いてみてください。
問題：
yukicoder No.1338 Giant Class - 【ACコード】
ABC127 D Integer Cards - 【ACコード】
ABC188 F +1-1x2 - 【ACコード】
順番前後しますが、ABC188 Fはメモ化再帰を使用します。後述のDFSの章を理解した上で解いてください。
12.カウンター
リンク：PythonのCounterでリストの各要素の出現個数をカウント
collections.Counterでリストの出現回数が調べられます。
使う場面はとても多いです。
難しい問題になると、そのアルゴリズム＋カウンターの兼ね合わせで答える問題が多いと、この記事を作る際に感じました。
collections.Counterは多機能なため、使いこなせるようになるとACコードを書くまでの時間を短縮できるはずです。
問題：
yukicoder No.1468 Colourful Pastel - 【ACコード】
ABC118 B Foods Loved by Everyone - 【ACコード】
ABC082 C Good Sequence - 【ACコード】
ABC163 C management - 【ACコード】
ABC171 D Replacing - 【ACコード】
AGC031 A Colorful Subsequence - 【ACコード】
ABC181 D Hachi - 【解説】（解説にそのままコードが記載されているため…）
ABC111 C //// - 【ACコード】
ABC052 C Factors of Factorial - 【ACコード】
ABC052 Cについては、前述の素因数分解も参照のこと挑んでください。
追記：
Counter同士の合算は、例えばC1とC2の合算を取りたい場合にC1+=C2といった書き方は出来るのですが、見た目に反して新しくCounterを作成する処理らしく、処理速度は遅いようです。
TLEする場合もあるので処理速度が気になるようでしたらupdateを推奨します。
Union-Findで紹介したABC183 F ConfluenceをCounterを使用して解いた際に、この書き方の差一つでTLEするか間に合うかが変わりました。
import collections
#TLEしがちな合算
C1 = collections.Counter([1,1,2,3,5,8])
C2 = collections.Counter([2,4,6,8,10])
C1+=C2
print(C1) #Counter({1: 2, 2: 2, 8: 2, 3: 1, 5: 1, 4: 1, 6: 1, 10: 1})
#速度の早い合算
#（以下の例では行っていないですがC1とC2のlen比較を行って要素数の大きい方をベースとして結合する方が速度が早くなるようです）
C1 = collections.Counter([1,1,2,3,5,8])
C2 = collections.Counter([2,4,6,8,10])
C1.update(C2)
print(C1) #Counter({1: 2, 2: 2, 8: 2, 3: 1, 5: 1, 4: 1, 6: 1, 10: 1})
13.ModInt
リンク：Pythonでmodintを実装してみた
modをとる問題で使います。大きな値になると、C++などではオーバーフローしてしまうため、modをとった値で答えを出力することが多いです。
Pythonでは大きな値も扱えるには扱えますが、そのままでは処理速度はとても遅くなるため、modを取りながら計算する必要がある問題もよく出ます。
この際に、ModIntを使用すると計算が楽に行えます。
ModIntで四則演算が行えば、勝手に$10^9+7$など、定めた値で割った余りの値になってくれます。
習うより慣れろで試してみることをお勧めします。
ここでは問題を紹介しません。計算中にMOD取るのが煩わしい場合に使用するものであり、絶対使わないといけないというものではないため、問題紹介が難しく…
今回紹介している問題で私が使用したのは素因数分解で紹介したFlattenのみです。
14.逆元
MODの世界で割り算が必要な時があります。
ModIntを使ってもよいのですが、わざわざ割り算のためだけに使うのもなって時、割り算を行いたいときは逆元を掛ける、ということを行えばよいです。（参考）
ModInt使うなら、そこまで使う必要もないのですが、記憶の片隅に留めておいて困ることはないと思います。
バージョン差で、Pythonで提出する場合には使用でき、Pypyでは使用できない方法があります。
#Pypy(7.3.0)、Python(3.8.2)どちらでも提出可能
#ただし、modは素数、aとmodは素である必要あり（AtCoderで提出する場合は、そこまで気にする必要はなさそうです）
a = 2
mod = 10**9+7
div = pow(a, mod - 2, mod)
#Python(3.8.2)で提出可能、Pypy(7.3.0)で提出するとエラー
#ただし、aとmodは素である必要あり（AtCoderで提出する場合は、そこまで気にする必要はなさそうです）
a = 2
mod = 10**9+7
div = pow(a, -1, mod)
問題：
リンク：ABC177 C Sum of product of pairs - 【ACコード】
紹介した問題は、別に逆元とる必要なかった問題でしたが（使用しないACコード）、一応記載します。
パッといい問題は見つからず…
15.階乗
$N!$を求めます。AtCoderでは組み合わせを使用する問題は巨大な値となることが多く、$10^9+7$などでModを取った値を答える必要のある問題が多いです。
仮にModをとり、何度も使用することがある場合は、以下のような下準備をしてあると便利です。
MOD = 10**9+7
fact = [1]
N = 10000
for n in range(1,N+1):
fact.append(fact[-1]*n%MOD)
math.factorial()という階乗を求める関数がmathモジュールに用意されていますが、呼び出す度に指定した値の階乗を求める計算が行われます。AtCoderで使用する場合は最悪TLEする危険があるため、注意が必要です。
何度も繰り返し階乗の計算する問題では気を付けましょう。
#仮に、1～10000までの階乗を全て求める場合
#MODなしfactorial、実行時間PyPyにて4000ms以上
import math
fact = [1]
for n in range(1,10001):
fact.append(math.factorial(n))
# Modなし 150ms程度
fact = [1]
for n in range(1,10001):
fact.append(fact[-1]*n)
#MODありfactorial、実行時間PyPyにて4000ms以上
MOD = 10**9+7
fact = [1]
for n in range(1,10001):
fact.append(math.factorial(n)%MOD)
#MODあり 100msを切る
MOD = 10**9+7
fact = [1]
for n in range(1,10001):
fact.append(fact[-1]*n%MOD)
と、ここまで書いて挙げたAtCoderの階乗の問題は、math.factorial()を使用して解けちゃう問題ですが多いです。
複雑な処理が必要な問題は、コンビネーションの問題になってくるので、コンビネーションの知識を使用せずに、上の知識のみが必要になってくる問題は見つからず…
問題：
ABC 055 B Training Camp - 【ACコード】
ABC 065 C Reconciled? - 【ACコード】
ABC 185 C Duodecim Ferra - 【ACコード】
追記： 記事作成後、1問見つけたため紹介します。良問です。
MojaCoder 入力1個数え上げ - 【ACコード】
16.コンビネーション
リンク：Python で二項係数 nCr を高速に計算したい
階乗の続きとなり、コンビネーションも下準備をしておくと、その結果を使用して高速に求められます。
内部で逆元の計算もしているのでさらに高速です。使う側は逆元について意識する必要はありません。
pは問題のmodの値に合わせて変更してください。
この処理で階乗の情報も取得できます。fact[n]とすることで$n!$のmodを取った値が取得できます。
コンビネーションで計算した結果に、ModIntを使用してさらに計算する、といった解き方で解く問題が多いと思われます。
(とは思いつつもその難易度の問題を解いたことがないです…)
問題：
ABC034 C 経路 - 【ACコード】
ABC145 D Knight - 【ACコード】
ABC132 D Blue and Red Balls - 【ACコード】
ABC167 E Colorful Blocks - 【ACコード】
$998244353$で割った余りの問題もありますので、気を付けてください。
ちなみに、$998244353$が使われる理由は、ACL-for-pythonのconvolutionのwikiに書かれていました。
（フーリエ全く分かってない…）
17.ある値の累乗の何度も使用する場合
何度も累乗の計算をしていると、TLEする恐れがあるため、階乗と同じく下準備しておく方が無難です。
MOD = 10**9+7
N=1000000
p = [1]
for n in range(N):
p.append(p[-1]*2%MOD)
Pythonのpowやべき乗は繰り返し二乗法により高速に計算するのですが、使用する指数がかなり大きくなれば処理は遅くなってしまいます。
以下、参考までに簡単に調べた処理速度です。
#仮に、2^1から2^Nまでの乗数を全て求める場合（他のパターンはTLEしたので除外）
#MODあり 300ms前後
MOD = 10**9+7
p = [1]
for n in range(1,5000000):
p.append(p[-1]*2%MOD)
#MODありpow、実行時間PyPyにて2000ms前後
MOD = 10**9+7
p = [1]
for n in range(1,5000000):
p.append(pow(2,n,MOD))
問題：
HHKB プログラミングコンテスト 2020 E Lamps - 【ACコード】
Lampsを解くためには、ABC129 D Lamp - 【ACコード】が解けている必要があります。挑戦する前にこの問題を解いてください。
18.最大公約数
リンク：Pythonで最大公約数と最小公倍数を算出・取得
バージョンの差異に気を付けてください。2021年4月現在のAtCoderで使用できるPythonのバージョンは3.8.2なので最大公約数は以下の方法取得できます。古い書き方であるfractions.gcdも3.8.2では使用できません。
3つ（以上）の要素について最大公約数を調べたい場合は、2つの最大公約数を調べた結果と3つ目の要素の最大公約数をとるように使用すればよいです。最小公倍数も同様です。
import math
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
print(my_lcm(6, 4))
最大公約数や3つ以上の引数をサポートする3.9以降が使用できる日が待ち遠しいですね。AtCoderの言語アップデートはそろそろ行われるはずです。
ちなみに、Python 3.9の次バージョンはPython 3.10らしいです。わかりにくい…
問題が少ないため、最大公約数のほか、最小公倍数を使用した問題も並べます。どちらを使用する問題か、検討して使用してみてください。
問題：
ABC102 A Multiple of 2 and N - 【ACコード】
ARC105 B MAX-=min - 【ACコード】
ABC131 C Anti-Division - 【ACコード】
yukicoder No.1464 Number Conversion - 【ACコード】
ARC110 A Redundant Redundancy - 【ACコード】
19.中国剰余定理
リンク：ACL-for-python/math.py
Wiki(使用例)
以下のような問題を解くのに使用します。
3で割ると2余り、5で割ると3余り、7で割ると2余る。この条件を満たす（最小の）正の整数を求めよ。
アルゴリズムを理解するのは難しいですが、使うだけなら非常に楽です。その上、解けば水色や青色のパフォを出すことも夢ではありません。
次に中国剰余定理の知識が必要な出た場合は、みんな勉強してきてると思われるのでdifficultyの数値は下がりそうですが…
中国剰余定理はACLに含まれているので、そのPython移植版を使用します。
#ACL部分は省略
#3で割ると2余り、5で割ると3余り、7で割ると2余る
C = [3,5,7]#これで割ったら
R = [2,3,2]#この余りになる対のリスト
r,m = crt(R,C)
print(r)#23
矛盾（例として4で割って1余り、2で割って0余る。などという存在しえない条件の場合）のある場合は返却値の2つ目の要素が0であるかで判断できます。
ちなみに、2つ目の要素は値が一巡する法の値となります。
内部処理をPythonに置き換えた方が処理を細かく説明している記事もありますので、そちらも確認してみてください。（参考）
問題：
ABC186 E Throne - 【ACコード】
ABC193 E Oversleeping - 【ACコード】
20.DFS
リンク：よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜
問題解決力を鍛える!アルゴリズムとデータ構造の著者で有名なけんちょんさんの記事です。
いつもはC++のコードですが、DFSの記事については、Pythonのコードも載っています。
popの書き方は毎回そのような書き方をする必要があるわけではないです。
上記サイトの『細かい注意点』に記載があるよう、以下の書き方は毎回リストを作り直すような挙動になるため、注意が必要とあります。
そこまで長くならないと制約から読み取れるDFSの処理では以下の書き方でよいのでは、と思っています。
制約から深くなりそうと思えば、popやリストを外だしで管理して使用する書き方にするのがいいと思います。
比較的簡単な問題ではlistを引数にするのではなく、値を引数にすることが多いかと思います。
import sys
sys.setrecursionlimit(10 ** 9) #再帰回数の限界を変更
def dfs(A):
# 数列の長さが N に達したら打ち切り
if len(A) == N:
# 処理
return
for v in range(M):
dfs(A+[v])
dfs([])
元のコードよりもMLEやTLEが心配ですが、そこまで大きな値にならないと分かれば上記の書き方の方が分かりやすいかなと。
Python版のACコードがなかったり、ちょっとだけ変えた書き方をしましたので、上記記事で紹介されている問題も↓に並べます。
問題：
ABC114 C 755 - 【ACコード】
ABC161 D Lunlun Number - 【ACコード】
ABC165 C Many Requirements - 【ACコード】
パナソニックプログラミングコンテスト D String Equivalence - 【ACコード】
ABC119 C Synthetic Kadomatsu - 【ACコード】
ABC198 E Unique Color - 【ACコード】
ABC196 D Hanjo - 【ACコード】
上記問題は全てPypyによる提出でTLEしていませんが、Pypyの提出でTLEしてしまう問題もあります。その時はPythonで提出してみましょう。通ることがあります。しかし、それでもTLEしてしまう問題もあります。その場合はキューを使用したコードに置き換えましょう。
どれで提出すればよいか見極めなければならないのは、Pythonのネックな箇所ですね…
追記：
PypyでもTLEを気にせずDFS使えるようなよい情報がありました。
すべての問題に対して試したわけではないですが、確かにTLEせずに通った問題があります。
試す際は、念のため提出前にAtCoder上のコードテストを行ってから提出するようにして使うつもりです。
※それでもPypyでTLEするけれどPythonでACすることがあったので、Pythonの提出も試す必要がありそうです
（ABC284 EにてPythonでACするがPypyでTLEするコード）
再帰の関係でPyPyだとTLE/MLEするやつ
— eheka (@ehekatlact) February 7, 2022
先頭に
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
と書くとPyPyでもACできるし、Pythonよりも早いことを確認
提出 #29147867 - AtCoder Beginner Contest 149 https://t.co/UvHYer4SNM pic.twitter.com/DOdqAspWsD
20.1.メモ化再帰
リンク：Python 3でfunctools.lru_cacheを使って簡単にメモ化再帰
DFSの項が長くなっちゃうので少し分割してメモ化再帰についての補足的な内容です。
functools.lru_cacheを使用してメモ化再帰を簡潔に書くことができます。
値が確定する呼び出しについて、再び呼び出す時に過去に同じパラメーターの呼び出しがあれば前回の値を再利用して返却するような仕組みです。
使う機会は少ないとは思いますが、記憶の片隅にでも留めておくと、いつか役に立つときが来るかもしれません。
問題：
ABC260 C Changing Jewels - 【ACコード】
ABC270 D Stones - 【ACコード】
ABC280 E Critical Hit - 【ACコード】
21.二分探索（bisect）
リンク：Python標準ライブラリ：順序維持のbisect
昇順ソートされたリストに対してソート順序を保ったまま値を挿入したい(よくある問題としては挿入される場所を知りたい)場合はbisectを使用します。
入力された値がばらばらなリストの内容を昇順リストに変換してから二分探索を行うといった問題が出やすいです。
left、rightの違い、また0から開始する（正しい言い回しとしては、zero-basedとか0オリジンとか）ことに気を付けて使いましょう。
問題：
ABC143 D Triangles - 【ACコード】
ABC077 C Snuke Festival - 【ACコード】
ABC184 F Programming Contest - 【ACコード】
22.二分探索（その他）
リンク：めぐる式二分探索 コピペで使えるPython実装
上記bisectによる二分探索は、昇順リストの中身を二分探索して調べるものです。
昇順リストではない、ある閾値を調べるための二分探索する場合のアルゴリズムとして有名なものが【めぐる式二分探索】です。
自作するとどうしてもバグが起きやすいとされる二分探索のバグを極端に減らしてくれる優れものです。
あるキャラのなりきりアカウントから有名になった手法のため、こんな名前がつきました。
色々あって、公には使いにくい名称となっているよう。きっとこのなりきりをしていたお茶目な方は、今も元気に仕事とTwitterをやっていそうですね。
問題：
yukicoder No.1101 鼻水 - 【ACコード】
ARC109 B log - 【ACコード】
ABC174 E logs - 【ACコード】
ARC050 B 花束 - 【ACコード】
補足1：
整数の二分探索だけでなく、三分探索や実数に対する問題に対するスニペットの情報も欲しいですよね。
リンク：競プロのライブラリ整理~二分探索と三分探索~
AtCoder側のアカウントは削除されていますが、yukicoderの提出コードは残っているのでそこから使い方を推量りましょう。
問題(三分探索の)：
ARC122 B Insurance - 【ACコード】
ARC049 B 高橋ノルム君 - 【ACコード】
補足2:
受験っぽいですが、ABC で「○○の最小値を最大化しろ」（かその逆） って言われたら二分探索をして 95% 以上は間違いないと思います（ABC199 までだと多分 100%）https://t.co/4hCsEYvcXH pic.twitter.com/zRkX1lnCbk
— えびま (@evima0) May 2, 2021
23.最長増加部分列（LIS）
リンク：最長増加部分列
処理や機能の説明は以下のサイトが分かりやすかったです。
最長増加部分列(LIS)の長さを求める
同じ値も増加列とみなす場合は広義最長増加列と言います。
広義最長増加列を取得したい場合紹介したアルゴリズムのこの部分だけを直せば問題ないです。
変更前
idx = bisect(dp, a-1)#最長増加部分列(original)
変更後
idx = bisect(dp, a)#広義最長増加部分列
逆に最長減少部分列の長さを確認したい場合は、リストを逆順にして、最長増加部分列のアルゴリズムを行えば取得できます。
LISのアルゴリズムの紹介先のサイトでは、他にも様々なアルゴリズムなどがありますので一通り眺めてみることをお勧めします。文字列系のアルゴリズムが他にも記載されています。(GitHubはこちらから)
後半で説明する転倒数、最長共通部分列もこちらのサイトから紹介しています。
問題：
ABC006 D トランプ挿入ソート - 【ACコード】
ABC134 E Sequence Decomposing - 【ACコード】
(expert!) AGC024 B Backfront - 【ACコード】
24.累積和（合わせて、いもす法）
リンク：すごいぞitertoolsくん（順列・組み合わせ）
itertools.accumulateで累積和を求めることができます。累積和をたったワンライナーで求めることができます。
累積和を前準備することで範囲を求める処理が $O(1)$ で済みます。
累積和を求めるメリットの詳細はけんちょんさんの記事がよくわかると思います。
いもす法についてもけんちょんさんの記事を読んでください。（何か書こうにも丸パクリの上に劣化になっちゃうので…）
累積和にてある範囲を取る場合、範囲の指定はこのようになります。
import itertools
L = list(range(1,7)) #[1,2,3,4,5,6]
AC = list(itertools.accumulate(L)) #[1,3,6,10,15,21]
#要素の3つ目から5つ目の合計が知りたい場合の書き方(3+4+5=12)
l,r=2,4#0から開始なので1個ずれちゃいます（正しい言い回しとしては、zero-basedとか0オリジンとか）
print(AC[r]-AC[l-1])# 12 AC[r]からAC[l-1]を引くと範囲となる
この書き方をすることで問題ないように思えますがlが1つ目の要素だった場合、l-1は、マイナスの値になってしまいます。
ここで、Pythonはリストの-1を指定するとリストの末尾を参照してくれる優れた機能があるため、累積和の末に0を付け加えると、lが0でも気にならなくなるテクニックがあります。
ぜひ覚えておいてください。
import itertools
L = list(range(1,7)) #[1,2,3,4,5,6]
AC = list(itertools.accumulate(L))+[0] #[1,3,6,10,15,21,0]
#要素の1つ目から5つ目の合計が知りたい場合の書き方(1+2+3+4+5=15)
l,r=0,4
print(AC[r]-AC[l-1])# 15 (AC[4]-AC[-1]→15-0→15)
また、いもす法を実現する場合にもr+1まで値を更新することになるため、元のリストの長さに要素を一つ追加した長さのリストを用意しておくと便利です。
ちなみに、負の値のないリストの累積和を取る場合、昇順ソートされた状態になるので二分探索（bisect）とも相性が良いです。
問題：
AGC023 A Zero-Sum Ranges - 【ACコード】
ABC014 C AtColor - 【ACコード】
ABC183 D Water Heater - 【ACコード】
ABC035 D オセロ - 【ACコード】
ABC188 D Snuke Prime - 【ACコード】
東京海上日動 プログラミングコンテスト2020 C Lamps - 【ACコード】
ABC105 D Candy Distribution - 【ACコード】
ARC100 D Equal Cut - 【ACコード】
25.短めな順列の作成
リンク：すごいぞitertoolsくん（順列・組み合わせ）
全探索するための順列をワンライナーで作成できます。
itertools.productを使用して、BIT全探索をことも可能なようです。
ここでは2問しか紹介しませんでしたが、この章以外の問題でも使っています。
問題：
ABC028 C 数を3つ選ぶマン - 【ACコード】
ABC183 C Travel - 【ACコード】
26.二次元累積和
リンク：蟻本 Python 二次元累積和 競技プログラミング Atcoder
（リンク切れになっています。こういった場合を想定しておらず、ひとまずそのまま残します）
二次元累積和です。
累積和の方では、範囲を求めるためにリストの末尾に[0]を付けることをお勧めしましたが、今回紹介した内容は、始点の計算についてモジュール内で正しく分岐されるようになっているため不要です。（一次元の時と同じく、いもす法を実現するのであればリストの末尾に[0]を付けていた方が処理を考えるのに楽です）
二次元累積和を求める計算が短く、なんでこれだけの要素だけで求められるのだろうと気になって調べたら、こういう理屈だったと知って思わず感嘆しました。
数学弱者にはこんなの思いつけない…
累積和でも紹介しましたが、二次元でのいもす法の値の設定方法もいもす法のサイトに記載されているので参照ください。
問題：
MojaCoder ASCII Squares - 【ACコード】
ARC025 B チョコレート - 【ACコード】
ABC203 D Pond - 【ACコード】
27.ダイクストラ法
リンク：競技プログラミングで使う有名グラフアルゴリズムまとめ ダイクストラ法(defaultdictで実装) 経路復元も
リンク先のダイクストラ法は、頂点をdefaultdictで管理するため、数値以外の頂点も使用できます。
（キーにタプルなどを使用すると少々処理が遅くなるため、頂点の数の注意が必要です）
また経路復元を行った結果も返却されます。
ダイクストラを使用する問題では、その処理の中身を変更しないといけない問題が多いので、カスタマイズできるよう、コードはしっかり理解しましょう。
問題：
ARC109 A Hands - 【ACコード】
ABC160 D Line++ - 【ACコード】
ABC191 E Come Back Quickly - 【ACコード】
(expert!) MojaCoder As Soon As Possible - 【ACコード】
(expert!) ABC192 E Train - 【ACコード】
(expert!※) yukicoder No.807 umg tours - 【ACコード】
(expert!※)ZONeエナジー プログラミングコンテスト E 潜入 - 【ACコード経路復元あり】【ACコード経路復元なし】
expert!について、中のアルゴリズムを書き換える必要があったり、中の処理が分かればすぐ答えられる問題となっています。
※について、解けはしましたが制限時間ギリギリで、頂点を1次元で管理（特殊な頂点はマイナス扱い）、経路復元処理なしなど処理を変更することで安定した回答となりました。頂点や辺の数が多い場合は、処理時間の削減できる場所を見つけて処理時間を短縮する必要あります。超頂点といった言葉が参考になりそうです。
経路復元ありを説明に使いましたが、別に経路復元必要な問題解いてないですね…
重みに負数がある場合は、ベルマンフォード法を使用しなければなりません。リンク先にも紹介があるのですが、ベルマンフォード法についてはこの記事内のベルマンフォード法を参照ください。
28.ワーシャルフロイド法
リンク：競技プログラミングで使う有名グラフアルゴリズムまとめ ワーシャルフロイド法
重み付き有向グラフの全ペアの最短経路を取得できます。紹介したリンク先は、ダイクストラ法と同じ記事です。
処理や機能の説明は以下のサイトが分かりやすかったです。
素人によるワーシャルフロイド法
制約から予測するのが危ない場合もありますが、コストを考える必要のあるグラフについて、頂点の数が $1 \leq N \leq 300$ 程度の制約であるとワーシャルフロイドで解く問題なのかと想像します。オーダーが $O(N^3)$ のため。
頂点が増えるとTLEするため、頂点の数が多い場合は使用しないです。
参考のものは負経路を検出できます。使用しないことが多いとは思いますが、あって困らないかなと。戻り値は複数なため、探索結果を受け取る時は↓のようにして受け取りましょう。
hasNegativeCycle, d = graph.WarshallFloyd_search() #dに本来の結果が入る
問題：
ARC079 D Wall - 【ACコード】
ARC073 D joisino's travel - 【ACコード】
(expert!) yukicoder No.1344 Typical Shortest Path Sum - 【ACコード】
(expert!) ABC074 D Restoring Road Network - 【ACコード】
29.セグメント木（セグ木）
リンク：ACL-for-python/segtree.py
Wiki(使用例)
任意の区間に対する操作（一要素の更新・区間に対するクエリ）を高速に行えます。
中国剰余定理と同様、セグ木もACLに含まれているので、そのPython移植版を使用します。
基本的に使用する操作やそれに必要な要素についてもWikiに載ってますので参照のこと。
相当高度なアルゴリズムなのですが、ただ使うだけの典型問題なら緑Diffになると判明し、話題になりました。
使用する際の個人的な注意点としては、G.prod(l,r)について、範囲は$[l,r)$であり、rが含まれていない点です。
これに気付いていれば解けてた問題をずっと悩んで答えられなかった過去があります…
セグ木は私自身そこまで理解できておらず、基本的な方法で解ける問題のみ紹介します。
問題：
ABC185 F Range Xor Query - 【ACコード】
ABC123 C GCD on Blackboard - 【ACコード】
yukicoder No.875 Range Mindex Query - 【ACコード】
ACL Beginner Contest D Flat Subsequence - 【ACコード】
補足：
ちなみにACLに遅延セグメント木が存在しますが、私は使い方を理解できません。
難しいと思われた方は、LISのアルゴリズムの紹介先のサイトに、ある機能に特化した遅延評価セグメント木が存在するため、それで対応できる問題であれば、そちらを使用してみるとよいと思います。
30.転倒数
リンク：反転数
転倒数とは、バブルソートをした際の交換する回数を高速に求めるアルゴリズムです。
リンク先の名前は反転数となっていますが、転倒数と同じ意味です。
実装については、ある程度条件がありますので、元のリストが記載された条件に沿わない形であれば沿うような形に直してから行ってください。
ちなみに、転倒数はセグ木でも求められます。セグ木で実装するのは機能過多にあたるそうです。気になった方は調べてみてください。
問題：
yukicoder No.742 にゃんにゃんにゃん 猫の挨拶 - 【ACコード】
yukicoder No.1115 二つの数列 / Two Sequences - 【ACコード】
ABC190 F Shift and Inversions - 【ACコード】
ARC120 C Swaps 2 - 【ACコード】
31.桁DP
リンク：桁DPに入門してみた
$1$以上$N$以下の整数のうち○○である個数を求めよ。となっており、$N$の制約が$ 1 \le N \le 10^{10000}$だったりする場合は桁DPの出番です。
紹介したリンクは、普通のforの書き方よりもスマートに書けて、コードの内容も混乱しにくく出来ています。
ただし、defaultdictでの書き方であると、問題によってはTLEするため、リストで管理する書き方（↓）に置き換えて使用しています。
dp=[[[[[0] * 8 for _ in range(3)] for _ in range(2)] for _ in range(2)] for _ in range(n+1)]
dp[0][0][0][0][0] = 1
A以下B以上の非負整数のうち、「3が付くまたは3の倍数」かつ「8の倍数でない」数の総数を求める（折り畳みコード）
from itertools import product
a = int(input())
b = int(input())
def count(x):
a = str(x)
n = len(a)
#配列は末から
dp=[[[[[0] * 8 for _ in range(3)] for _ in range(2)] for _ in range(2)] for _ in range(n+1)]
dp[0][0][0][0][0] = 1
#条件に合わせてDP
for i, less, has3, mod3, mod8 in product(range(n), (0,1), (0,1), range(3), range(8)):
max_d = 9 if less else int(a[i])
for d in range(max_d+1):
less_ = less or d < max_d
has3_ = has3 or d == 3
mod3_ = (mod3 + d) % 3
mod8_ = (mod8*10 + d) % 8
dp[i + 1][less_][has3_][mod3_][mod8_] += dp[i][less][has3][mod3][mod8]
#合致するものを合算
ret = 0
for less, mod8 in product((0,1), range(1,8)):
ret += dp[n][less][1][0][mod8]
ret += dp[n][less][1][1][mod8]
ret += dp[n][less][1][2][mod8]
ret += dp[n][less][0][0][mod8]
return ret
print(count(a) - count(b-1))
他の人の書き方に比べ処置時間は掛かりますが、この書き方のせいでTLEすることはまずないかなと思います。F問題になるとギリギリアウトな問題が出てくるかもしれませんが...
紹介したのは$1$以上$N$以下の整数のうち、といったパターンですが、ビットで行う桁DPの問題などもあるので、気になった場合は調べてみてください。（追記に追加）
問題：
ABC154 E Almost Everywhere Zero - 【ACコード】
ABC135 D Digits Parade - 【ACコード】
ABC029 D 1 - 【ACコード】
yukicoder189 SUPER HAPPY DAY - 【ACコード】
yukicoder1417 100の倍数かつ正整数(2) - 【ACコード】
100の倍数かつ正整数(2)は拙作です。ちょっと特別なことに気づけないと解けない問題ですが、ぜひ挑戦してくれたら嬉しいです！ 解き方が分からない場合は問題の解説を読んでください。
追記：
アルファベットで行う桁DPの問題、ビットで行う桁DPの問題を追記ました。ぜひ解いてみてください。
yukicoder1740 Alone 'a' - 【ACコード】
ABC129 E Sum Equals Xor - 【ACコード】
ARC129 A Smaller XOR - 【ACコード】
32.ダブリング
リンク：[競プロ用]ダブリングまとめ
あるリストに対して、毎回同じ変化があり、N回数後の状態を求める問題で、そのNの最大が$10^9$以上など非常に大きな値であればダブリングを使う場面かと思います。詳細はリンクを確認してください。
一回使い方を覚えるとすんなりと使えるようになるはずです。ダブリングでないと解けない問題はそこまで多くはないのですが、覚えておいて損はないかなと。
ダブリングが想定解の問題は、ダブリングを使用することに気付けるかどうかがポイントになりやすいです。
問題：
ABC179 E Sequence Sum - 【ACコード】
ABC013 D 阿弥陀 - 【ACコード】
MojaCoder Three Teleporters - 【ACコード】
MojaCoder hyper fibonacci sequence - 【ACコード】
33.最長共通部分列
リンク：最長共通部分列
LCS （Longest Common Subsequence）とも呼びます。二つの文字列から一部分取り除いて、同じ文字列を作る時の最長となる部分文字列を求めます。
問題：
CODE FESTIVAL 2015 あさぷろ Middle B ヘイホー君と削除 - 【ACコード】
34.BitDP
リンク：BitDPについて
愚直に解こうとすると$N!$になる数え上げについて、$2^N$まで処理を高速化できます。
巡回セールスマン問題を解く場合にも、このアルゴリズムを使用します。
現在のABCで出てくるとしたらE問題以降だと思います。典型でも水色Diffなので、解けたら大分レートアップするはず。
問題：
ABC180 E Traveling Salesman among Aerial Cities - 【ACコード】
ABC142 E Get Everything - 【ACコード】
ABC199 E Permutation - 【ACコード】
ABC180 E がほぼ典型らしいのですが、その典型の情報を知らないで解くと難しいほうの部類に入る気がします。
ABC180 E で理解できなかった場合は、そのまま（リンク先の問題含め）別の問題で理解を深めることをお勧めします。
35.10進数を2進数、8進数、16進数に変換
リンク：Pythonで2進数、8進数、16進数の数値・文字列を相互に変換
コンテスト中に調べる時間がもったいないので、このような情報をもって、すぐに使えるようにしておきましょう。
i=255
print(format(i, 'b'))
print(format(i, 'o'))
print(format(i, 'x'))
# 11111111
# 377
# ff
# 戻り値は文字列
補足として、popcount(整数値の1ビットの数)を数えるならこんな書き方です。
popcountについての記事を見るとそこまで処理は遅くはないようです。
i=200
print(bin(i).count('1'))#iのpopcountを表示(この場合3)
int.bit_count()はPython 3.10以降で使える書き方で今のAtCoderの提出では使えません。
処理速度にかなりの差があるので、言語アップデート後はint.bit_count()を使用しましょう（参考）
問題：
ABC186 C Unlucky 7 - 【ACコード】
yukicoder No.1729 16進数と8進数(1) - 【ACコード】
ABC147 Xor Sum 4 - 【ACコード】
36.10進数とn進数の変換
リンク：Python で10進数とn進数の変換
2進数、8進数、16進数以外に変換したい場合もあります。逆に10進数へ変換した場合もあると思います。上記のリンクのモジュールを用意して変換しましょう。
Base_10_to_n()を使用するときは、切り捨て除算//に置き換えて使用した方がよいかなとは思います。処理ももう少し最適化できますが、AtCoderで出る問題は、C++でも整数型として扱える範囲でしか出ないと思われますので、気にしなくてもよいかなと。
10進数をn進数に変換する他の方法として、標準ライブラリのintを使用する方法があります。
Python 標準ライブラリ（int）
int('100', 16)のような書き方で、第二引数の基数に変換できますが、基数として指定できるのは0と2～36までのため、使用する場合は、注意して使用しましょう。
問題：
ABC156 B Digits - 【ACコード】
ABC192 D Base n - 【ACコード】
37.正規表現
リンク：Pythonの正規表現モジュールreの使い方（match、search、subなど）
覚えていると非常に簡単。
使いやすいように、以下のような状態ですぐ使えるようにしています。
import re
s = input()
ans = re.match('^AAA.*$', s)
if ans:
print('Yes')
else:
print('No')
問題：
Tenka1 Programmer Beginner Contest 2019 B - 【ACコード】
ABC017 B choku語 - 【ACコード】
ABC049 C 白昼夢 - 【ACコード】
38.キュー
リンク：Pythonのdequeでキュー、スタック、デック（両端キュー）を扱う
Pythonではキューとしてcollections.dequeとqueue.Queueがあります。（listもありますが遅いです。）
AtCoderでは、collections.dequeを使用しましょう。queue.Queueはcollections.dequeに比べ機能が少ない上、処理が遅くTLEしてしまいます。（参考1）（参考2）
（参考1にて、collections.dequeはスレッドセーフでないような言い回しですが、公式のドキュメントを確認したところ、スレッドセーフであるよう。スレッドセーフの仕様の違いで処理速度に違いがあるのかもしれないです。）
問題：
ABC066 C pushpush - 【ACコード】
ARC108 B Abbreviate Fox - 【ACコード】
ZONeエナジー プログラミングコンテスト D 宇宙人からのメッセージ - 【解説】（解説にそのままコードが記載されているため…）
AGC033 A Darker and Darker - 【ACコード】
注意点の追記：
Python 3.6の公式のドキュメントの説明にて、以下の注意があります。
両端への添字アクセスは $O(1)$ ですが、中央部分へは $O(N)$ と遅くなります。 高速なランダムアクセスが必要であればリストを使ってください。
端っこの参照は気にしなくてもよいですが、中央へ参照する際は処理速度が遅くなることに気を付けましょう。
私は動作を確認していませんが、各要素にO(1)でランダムアクセスできるdeque(両端キュー)を作成された方もいるようです。
注意点についてどうでもいい補足：
この注意点について、何故かPython3.8の日本語の公式ドキュメントからは記述が消えています。英語版にはちゃんと残っています。Python3.9の英語版にも残っている記述なので、中央へのアクセスには時間が掛かるままだと思われます。
39.優先度付きキュー
リンク：【Python】優先度付きキューの使い方【heapq】【ABC141 D】
ある状態での最小値や最大値を取得し、取りうる要素の追加も合間に繰り返す場合に使用します。詳細はリンク先で説明されています。
ちょっとした注意点が、リストの最初のアイテムは常に最小の値となることが保証されている程度であることです。ヒープの中が最小値順にソートされていることは保証されていません。（参考）
また、タプルについても優先度付きキューに取り込むことが可能です。（参考）
問題：
ABC137 D Summer Vacation - 【ACコード】
AGC053 B Taking the middle - 【ACコード】
40.しゃくとり法
リンク：AtCoder Beginner Contest 172を見直す(その2）C - Tsundoku 尺取り法
forとwhileの組み合わせで見ていきます。
詳細は、けんちょんさんの記事にて。
最近は出てきてない気がしますね…そろそろ出てきそうです。
問題：
ARC022 B 細長いお菓子 - 【ACコード】
ABC130 D Enough Array - 【ACコード】
yukicoder No.607 開通777年記念 - 【ACコード】
リンク先の記事については、あまり類題がない逆順からのコードのため、スニペットとして用意するなら、通常の順番であるEnough ArrayなどのACコードで用意しておいた方がいいと思います。
ちなみに、この記事作成後にしゃくとり法のDequeを使ったバグりにくい実装という記事が出来ました。
紹介した記事の書き方でバグが起きやすそうだなという方は、ぜひともこちらを参考にしてみてください。
41.ベルマンフォード法
リンク：ベルマンフォード法
リンク：pythonで青くなるブログ ABC137 E Coins Respawn
負経路が存在する場合の最短経路問題を解く場合、ベルマンフォード法を使用するのが一般的です。
有名なアルゴリズムではあるものの、全くと言っていいほど出てこないのですが…
上記サイトを参考に作成しました。誤りや不備があれば申し訳ありません。気づけた方はご指摘いただけると幸いです。
inf = float('inf')
class BellmanFord():
def __init__(self, N):
self.N = N
self.edges = []
def add(self, u, v, d, directed=False):
"""
u = from, v = to, d = cost
directed = Trueのとき、有向グラフである。
"""
if directed is False:
self.edges.append([u, v, d])
self.edges.append([v, u, d])
else:
self.edges.append([u, v, d])
def BellmanFord_search(self, start):
"""
:param s: 始点
:return: d[i] 始点sから各点iまでの最短経路
"""
# infならたどり着けず
# -infなら"通りたいパスに"負の閉路が存在する
D = [inf for i in range(self.N)]
D[start] = 0
for i in range(self.N*2):
for u,v,d in self.edges:
if D[v] > D[u] + d:
D[v] = D[u] + d
#2巡目負経路が存在する場合の動き
if i>=self.N:
D[v]=-inf
return D
問題：
ABC064 D Score Attack - 【ACコード】
ABC137 E Coins Respawn - 【ACコード】
当時の青Diffの問題も、今出たら緑Diffとなる可能性もありますね…
42.平衡二分探索木
リンク：Pythonで非再帰AVL木
AVL木とも呼びます。PythonにはSTLに順序付き集合が存在せず、コンテスト中に探しましては、よいアルゴリズムが見つからず解法が分かっているのに…と怨嗟しました。
今は見つかりましたので紹介。
長いコードですが、使い方などはしっかり書いてありますので、ぜひとも使いこなしましょう。
問題：
ABC217 D Cutting Woods - 【ACコード】
ABC228 D Linear Probing - 【ACコード】
追記：
2022年になって、tatyamさんが、Python で std::set の代替物を作ったという記事を挙げています。
上記で紹介したスニペットよりも高速で、上記のスニペットでTLEでも、こちらではACできる問題もありました。
この記事では細かく説明しませんが、詳細な使い方の記載もありますので、これから初めて取り組む方や実行速度を気にされる方は移行することをお勧めします。
使用するスニペットを移行する場合、使い方が異なることに注意してください。
43.Mo's Algorithm
リンク：PythonでMo's Algorithmを書いたよ
範囲について何度も答える問題で、更新クエリはなく、クエリの答える順番によらず答えが一定になるタイプの問題に利用できます。
使い方さえわかれば、Mo's Algorithmを使用する問題が簡単に思えてくるはずです。
MoStatusのaddとdiscardの中でその時のクエリの回答となるvalを問題の定義に合わせて増減させます。
Mo's Algorithmを使用する問題は、実行時間制限が2秒でない場合が多そうです。
Pythonは処理速度が速くないため、何らかの定数倍高速化がない場合はTLEする可能性があります。紹介されている記事のACコードを真似すると、まず問題なく回答できると思われます。
中国発祥のアルゴリズムらしく、中国の人がいとも容易く解くためG問題で出てもDiffは青くらいになるようです。
次出てくるときはF問題で出てきそうですね。
全て理解するのは難しいですが、座標圧縮するような問題で出てきても解けるようにはなっておくといいのかなと思います。
問題：
ABC174 F Range Set Query - 【TLEコード】
※ABC174Fは想定解がMo's Algorithmでないため基本的にTLEしてしまいますが、アルゴリズムの理解にはもってこいの問題です。
ABC242 G Range Pairing Query - 【ACコード】
ABC293 G Triple Index - 【ACコード】
※紹介元と解き方(増減の部分)の発想に少しだけ差があるので一応おいておきます。
44.おすすめな情報
問題を解くに当たって、ほか有益なだと思われる情報をいくつかピックアップします。
-
競技プログラミングで解法を思いつくための典型的な考え方
制約によってどのアルゴリズムを使いそうか、といった情報が載っています。 -
AtCoderで始めるPython入門AtCoderで始めるPython入門
Pythonで解く際の基本的な書き方についてまとめられています。 -
Pythonで競プロやるときによく書くコードをまとめてみた
Pythonで解く際の基本的な書き方についてまとめられています。 -
Pythonistaなら知らないと恥ずかしい計算量のはなし
理解していないとTLEしてしまいがちになる計算量の話です。 -
AtCoder での実力アップを目指そう！ ～競プロ典型 90 問～
ACコードがまだ載せられないので挙げませんでしたが、典型問題の紹介です。良問揃いです。 -
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】
上記競プロ典型 90 問作成者であるe869120さんの水コーダーを目指すためのガイドラインです。 -
unidayoさんのABCの解説
直近のABCのA～Cを解説しています。丁寧な解説のため、より効率的なコードの書き方を覚えることができます。復習にもってこいの記事です。 -
コードテストで速度測定済！PythonによるAtCoderスニペット集 (2)応用編
典型90問を例題に使用したPythonスニペット集です。この記事で紹介していないスニペットも存在しますので参照してみてください。
45.アルゴリズムを使用するにあたって
いくつかのアルゴリズムを紹介しました。では、実際にどのように取り出して使用しているかについて、私はCliborというソフトを使用しています。
競プロ界隈で、使用している人は見かけませんが、非常に使い勝手が良いです。
よく使うスニペットを定型文に登録することで、すぐにそのスニペットを取り出すことができます。
定型文の一行目はコメントで何のアルゴリズムであるか記載しておくと見つける際に楽です。
上記で紹介したスニペットの他、↓のようなスニペットを登録して、入力時間の短縮を図っています。
N = int(input())
A = list(map(int, input().split()))
N,K = map(int, input().split())
ans = True
if ans:
print('Yes')
else:
print('No')
コピペに関する作業が一気に効率化されるため、業務でも使用しています。本当にお勧めです。
お勧めの設定は↓こんな感じです。
困ることがあるとすれば、デフォルトのショートカットキーがCtrlを二連打なので、Apexを遊ぶ時は機能を止めないとしゃがむ動作でゲームが閉じられてしまうことです...
46.おわりに
上澄みをすくう記事で申し訳ないですが、Pythonのアルゴリズムについて、まとまった情報がなかなか見つかりにくいと感じたので作ってみました。
自分で考えるのは凄く大事ですが、あるものも使うのもよいことだと思います。
大人になるとね、熟考するより、stuck over flowで同じ問題抱えた人の投稿見つける方が大事だったりするんだ…
紹介した方のサイトのようにしっかり考えて作る人には感服するばかりです。
私が言うのはおこがましいですが、この記事を日々の精進に使用したり、本番前の確認に使用していただけたら幸いです。
この記事が誰かのお役に立つといいなと思います。
量の多い紹介となったため、チェックはしましたが、ミスが残っていると思われます。
説明の誤り、誤字脱字等が見つかればご連絡いただけると幸いです。不備があれば申し訳ありません。
また、説明内容に分からない点があれば、お気軽に質問していただけると幸いです。出来る限りお答えしたいと思います。
47.よければのお話
今回紹介したアルゴリズムの紹介先がよい記事であったり、素敵な問題であれば、ぜひともその記事や問題に対してスターや、LGTM、いいねを付けていただけたらと思います。
また、AtCoder以外のサイトやツールについても、AtCoder ProblemsのスポンサーやMojaCoderのスポンサー、yukicoderへのアマギフ提供などが行えます。
競プロの発展に多大な貢献をしていただいている方々に、金銭的な支援を行っていただけたら幸いです。