追記(2022/7/17)
セグメントツリーを訂正しました。
目的
AtCoderをPythonを用いて解答する場合、知っておいて方がいいルールや事前に用意しておいた方がいい関数などをまとめました。AtCoderやPython初心者~緑色の方を対象に記述しています。
知らない知識がないか流し読みできるよう簡単に書いています。
もし気になる部分があれば詳細は検索してください。
前提知識
Python3は実行速度が遅いためPyPy3で提出しましょう。
また提出時にPyPy3になっていることを確認しましょう。
用意しておくと便利な関数まとめ
アルファベットのリスト
アルファベットの文字列を扱う問題が頻出します。
asciiコードを用いるのが妥当かと思われますが、最初のうちは以下のリストをコピペで使用するのが簡単です。
#文字列リスト
SAL = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
LAL = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
配列の出力
配列の前にアスタリスクを入れると半角空白を入れてリストの中身を出力できます。
#リストを空白を入れて出力
A = [1,2,3]
print(*A)
#1 2 3
再帰回数を増やす
Pythonは再帰可能な回数が設定されており、一定回数を越すとエラーを吐きます。
#10**5回の再帰を行うプログラム
def A(n):
if n == 0:
return
else:
A(n-1)
print(A(10**5))
#RecursionError: maximum recursion depth exceeded
そこで再帰回数の上限を設定することで、上記のエラーを回避できるようになります。
import sys
sys.setrecursionlimit(10 ** 5)
配列のコピー
配列をコピーしたい際にはcopy()を使用すればコピーできますが、二次元配列などのコピーには以下のcopy.deepcopy()を用います。
import copy
copy.deepcopy()
二部探索
リストの中身をO(logN)で探索するには二分探索が最適です。
リストがソート済みであることが前提となります。
使用頻度はかなり高いので細かい仕様まで学習することを推奨します。
import bisect
bisect.bisect(list,int)
セグメントツリー
区間の和や積の計算、最小値や最大値の探索などをO(log n)で行えます。
(例えば数列の3番目から6番目の値の和を求めるなど。)
少し難しいですが非常に便利で使いどころは多いです。
内部的な仕様は以下のサイトが参考になると思います。
「セグメント木を徹底解説！0から遅延評価やモノイドまで」
https://algo-logic.info/segment-tree/
Pythonでの実装は以下のサイトが参考になると思います。
「Pythonでアルゴリズム（セグメント木）（実践）」
https://qiita.com/takayg1/items/c811bd07c21923d7ec69
Binary Indexed Tree
C++のstd::setは要素の挿入、削除、指定した範囲内の最大値や最小値の検索などをO(logN)で行えます。
これを前提とした問題が出題されることがあり、Pythonでは標準で実装されていないので、Binary Indexed Treeなどを使う必要があります。
(これを使わないと基本的に上記の操作の計算量はO(n)になります。)
私は以下のサイトを参考に実装しました。
「std::setを使わない代替テクニック」
https://ikatakos.com/pot/programming_algorithm/data_structure/balancing_binary_search_tree/tree_free
Pythonに限らないのAtCoderに関する情報
ここからはPythonに限らないAtCoderを取り組む際に有益な情報を記載します。
Pythonに関する情報のみを知りたい方はブラウザバックしてくださっても大丈夫です。
AtCoderで解説を読んでも、不正解や実行時エラーの理由が分からない場合があります。
その時はテストケースを実際に入力してみることをおすすめします。
以下のサイトで、過去のABCやARCなどのテストケースが配布されています。
「atcoder_testcases」
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
同じABCのC問題でも回によって大きく難易度が変わります。
そこで以下のサイトで難易度を確認してから自分に合った難易度の問題を解くと効率よく学習できます。
「AtCoder Problems」
https://kenkoooo.com/atcoder/#/table/
水色までに出現頻度の高いアルゴリズム
累積和、動的計画法、グラフ問題はかなり頻出します。
グラフ問題ではダイクストラ法、強連結成分分析などは学習しておいて損はないと思います。