LoginSignup
21
32

More than 1 year has passed since last update.

@sano192

【AtCoder】チートシート公開(コメント解説付き)【競技プログラミング】

Last updated at Posted at 2022-10-09

競技プログラミングの時に使っているよく使うコード集、いわゆるチートシートを公開します。
問題を解く時にコピペで使ってください
追加したときはこちらも更新します。

その他のABC解説、動画などは以下です。

テストケース作成

# テストケース作成
# pathにテストケースをテキストファイルで作る
path="D:\\test.txt"

# Sにテストケース内容を文字列で作る

# Sをテキストに書き込み
with open(path, mode='w') as f:
    f.write(S)

再帰回数上限変更

# 再帰回数上限を10^6へ変更(再帰関数を使うときは必須)
import sys
sys.setrecursionlimit(10**6)

itertools

itertools
itertoolsは数列の順列や組み合わせなどを作ることができるライブラリです。
「使い方」
import：import itertolls
順列：permutations(range(始まり,終わり+1))
重複なしの組み合わせ：combinations(range(始まり,終わり+1),取る個数)
重複ありの組み合わせ：combinations_with_rep(range(始まり,終わり+1),取る個数)
直積：product(range(始まり,終わり+1),range(始まり,終わり+1)):

使用例

# import：import itertolls
import itertools
 
N,K=4,2
 
# 順列：permutations(range(N))
# seq=(0,1,2,3),(0,1,3,2),(0,2,1,3),(0,2,3,1),...,(3,2,1,0)
print("[順列]")
for seq in itertools.permutations(range(N)):
    print(seq)
 
# 重複なしの組み合わせ：combinations(range(N),K)
print("[重複なしの組み合わせ]")
# seq=(0,1),(0,2),(0,3),(1,2)...,(2,3)
for seq in itertools.combinations(range(N),K):
    print(seq)
 
# 重複ありの組み合わせ：combinations_with_rep(range(N),K)
print("[重複ありの組み合わせ]")
# seq=(0,0),(0,1),(0,2),(0,3),(1,1)...,(3,3)
for seq in itertools.combinations_with_replacement(range(N),K):
    print(seq)
 
# 直積：product(range(N),range(N)):
print("[直積]")
# seq=(0,0),(0,1),(0,2),(0,3),(1,0)...,(3,3)
for seq in itertools.product(range(N),range(N)):
    print(seq)

コード内容

# itertools
import itertools
#(1,1,1),(1,1,2),---,(9,9,9)
for p in itertools.combinations_with_replacement(range(1,10),3):
# (1,2,3),(1,2,4),---,(7,8,9)
for p in itertools.combinations(range(1,10),3):
#(1,1),(1,2),(1,3),(2,1),(2,2),---(3,3)
for p in itertools.product(range(1,4),range(1,4)):
#(1,2,3),(1,3,2),(2,1,3),(2,3,1),---,(3,2,1)
for p in itertools.permutations(range(1,4)):

素因数分解

# Nの素因数分解
# N=1の場合は空のリストを返す
def PrimeFactorize(N):
    # もしN=1ならば
    if N==1:
        # 空のリストを返す
        return []        
    # 素因数を格納するリスト
    p=[]
    # i=2,3,4,...で試し割り
    i=2
    # i≤√Nすなわちi**2≤Nの範囲で試し割り
    while i**2<=N:
        # もしiで割り切れたら
        if N%i==0:
            # iを素因数に追加
            p.append(i)
            # Nをiで割る
            N//=i
        # iで割り切れなかったら
        else:
            # 次のiへ
            i+=1
    # 試し割りが終わった時Nが1でなければ
    if N!=1:
        # 素因数にNを追加
        p.append(N)
    # 素因数のリストを返す
    return p

nCrをpで割った余り

# nCrをpで割った余り(pは素数)
# pが省略された場合は余りを取らない
def nCr(n,r,p=0):
    # 分子(numerator)
    num=1
    # i=(n-r+1)~n
    for i in range(n-r+1,n+1):
        # 掛け算
        num*=i
        # p=0(デフォルト値)でなければ
        if p!=0:
            # 余りを取る
            num%=p
    # 分母(denominator)
    den=1
    # i=1~r
    for i in range(1,r+1):
        # 掛け算
        den*=i

        # p=0(デフォルト値)でなければ
        if p!=0:
            # 余りを取る
            den%=p    
    # p=0(デフォルト値)でなければ
    if p!=0:
        # 分母の逆元を取る
        den=pow(den,-1,p)
        # 掛け算して余りを取る
        return num*den%p
    # p=0(デフォルト値)ならば
    else:
        # そのまま割り算
        return num//den

約数列挙

# Nの約数列挙
def DivisorList(N):
    # 約数のリスト
    d=[]
    # 初期値
    i=1
    # i≤√N⇔i^2≤Nの間
    while i**2<=N:
        # N%i=0⇔iはNの約数
        if N%i==0:
            # iを追加
            d.append(i)
            # i≠N//iならば
            if i!=N//i:
                # N//iも追加
                d.append(N//i)
        # 次のiへ
        i+=1
    # リストをソート
    d.sort()
    # リストを返す
    return d

最小公倍数

# (x,y)の最小公倍数
# gcdをインポート
from math import gcd
def lcm(x,y):
    # x*y//(x,y)の最大公約数
    return (x*y)//gcd(x, y)

切り上げ

# x/aの切り上げ
def Ceil(x,a):
    # xがaで割り切れる
    if x%a==0:
        # x//aを返す
        return x//a
    # xがaで割り切れない
    else:
        # (x//a+1)を返す
        return x//a+1

UnionFind

クラス内容の詳細な解説は『AtCoder 最速で緑になる 基礎・典型50問詳細解説』に記載しています。
詳細は下部の【広告】を御覧ください。

UnionFindはグラフの連結の管理を高速でできるデータ構造です。
「使い方」
・初期化：変数名=UnionFind(要素の数)
・連結：変数名.merge(要素番号1,要素番号2)
・連結か確認：変数名.same(要素番号1,要素番号2)
　(連結ならTrue,連結でないならFalseを返す)
・所属する連結成分のサイズ確認：変数名.size(要素番号)

UnionFindの解説動画

使用例

# 初期化：変数名=UnionFind(要素の数)
UF=UnionFind(10)

# グループ化：変数名.merge(要素番号1,要素番号2)
UF.merge(0,2)
UF.merge(1,3)
UF.merge(3,0)

# グループリーダー(根)の確認：変数名.leader(要素番号)
leaderX=UF.leader(1)

# 同一グループかの確認：変数名.same(要素番号1,要素番号2)
if UF.same(1,5)==True:
    print("同一グループ")
else:
    print("別グループ")

# 所属するグループのサイズ確認：変数名.size(要素番号)
sizeX=UF.size(1)

コード内容

# UnionFind
class UnionFind:
    # UnionFind(N)：要素数Nで初期化
    # 引数：N(要素数)　→　返り値：なし
    def __init__(self,N):
        # 要素数
        self.N=N
        # 根の番号　と　木の要素数
        # マイナスの場合:グループの要素数(自身が根)
        # プラスの場合:根の番号
        self.parent_size=[-1]*N
    # leader(a)：aの根を返す
    # 引数：a　→　返り値：aの根
    def leader(self,a):
        # aが根ならa自身を返す
        if self.parent_size[a]<0: return a
        # aが根でないなら根に向かって木をたどる＋根の更新
        self.parent_size[a]=self.leader(self.parent_size[a])
        # 根を返す
        return self.parent_size[a]
    # merge(a,b)：aとbを連結
    # 引数：a,b　→　返り値：なし
    def merge(self,a,b):
        # a,bの根をx,yへ
        x,y=self.leader(a),self.leader(b)
        # 根が同じなら終了
        if x == y: return
        # 木の要素数を比較　小さい方を大きい方につなげるため
        # x<yならばx,yを入れ替える(xを大きい方にしたい)
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        # 要素数の更新：小さい方の要素数を大きい方の要素数に足す
        self.parent_size[x] += self.parent_size[y]
        # 要素数が小さい方の根を大きい方の根につなげる
        self.parent_size[y]=x
    # same(a,b)：aとbの根が同じか確認
    # 引数：a,b　→　返り値：True(根が同じ)　False(根が違う)
    def same(self,a,b):
        # 根を比較し、同じならTrueを返す
        return self.leader(a) == self.leader(b)
    # size(a)：aが属する木の要素数
    # 引数：a　→　返り値：aが属する木の要素数
    def size(self,a):
        # 根の絶対値(=要素数)を返す
        return abs(self.parent_size[self.leader(a)])

FenwickTree

クラス内容の詳細な解説は『AtCoder 最速で緑になる 基礎・典型50問詳細解説』に記載しています。
詳細は下部の【広告】を御覧ください。

FenwickTree
FenwickTreeは数列の要素への加算、区間和計算を高速で行えるデータ構造です。
FenwickTreeについては以下の記事でとてもわかり易くまとめられています。
中身に興味があれば読んでください。

使用例

# 初期化【O(N)】：変数名=Fenwick_Tree(要素数)
FT=FenwickTree(10)

# 加算【O(logN)】：add(インデックス番号,加算する数)
FT.add(0,4)
FT.add(5,-1)
FT.add(7,3)

# 区間和の計算【O(logN)】：sum(左インデックス番号,右インデックス番号)
print(FT.sum(2,8))

# 値の参照【O(logN)】：select(インデックス番号)
print(FT.select(7))

コード内容

# FenwickTree
class FenwickTree:
    # 「FenwickTree(N)：要素数Nで初期化」
    # 引数：N→返り値：なし
    def __init__(self,N):
        self.N=N
        # F：長さNのリスト
        self.F=[0]*N
    # 「add(i,x)：i番目の要素にxを加算」
    # 引数：i,x→返り値：なし
    def add(self,i,x):
        # 1インデックスにするため1を加算
        i+=1
        # i≤Nの間
        while i<=self.N:
            # xを加算
            # iはプラス1されているのでF[i-1]に加算
            self.F[i-1]+=x
            # 次のi
            i+=i&-i
    # 「sum_r(r)：区間[0,r)の区間和を計算」
    # 引数：r→返り値：区間[0,r)の区間和
    def sum_r(self,r):
        # 合計
        s=0
        # 0<rの間
        while 0<r:
            # sに加算
            s+=self.F[r-1]
            # 次のr
            r-=r&-r
        # 合計を返す
        return s
    # 「sum(l,r)：区間[l,r]の区間和を計算」
    # 引数：l,r→返り値：区間[l,r]の区間和
    def sum(self,l,r):
        # 「区間[l,r]の区間和」=「区間[0,r+1)の区間和」-「区間[0,l)の区間和」
        return self.sum_r(r+1)-self.sum_r(l)

    # 「select(i)：i番目の要素を出力」
    # 引数：i→返り値：i番目の要素
    def select(self,i):
        # 区間[i,i]の区間和
        return self.sum(i,i)

エラトステネスの篩(N以下の素数列挙)

# エラトステネスの篩(N以下の素数列挙)
def Eratosthenes(N):
    # 素数であるかの判定リスト
    IsPrime=[True]*(N+1)
    # i=2,3,4,...
    i=2
    # i≤√Nまで⇔i^2≤Nまで
    while i**2<=N:
        # iが素数でなければ
        if IsPrime[i]==False:
            # 次のiへ
            i+=1
            continue
        # k=2,3,4,...
        k=2
        while i*k<=N:
            # iの倍数は素数でない
            IsPrime[i*k]=False
            # 次のkへ
            k+=1
        # 次のkへ
        i+=1
    # 素数リスト
    PList=[]
    # i=2~N
    for i in range(2,N+1):
        # iが素数ならば
        if IsPrime[i]==True:
            # リストへ入れる
            PList.append(i)
    # リストを返す
    return PList

【広告】

『AtCoder 最速で緑になる 基礎・典型50問詳細解説』

ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP

【booth(pdf)】
https://booth.pm/ja/items/4102300

冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843

『AtCoder　凡人が『緑』になるための精選50問詳細解説』

AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/gp/product/B09C3TPQYV/

【booth(pdf)】
https://sano192.booth.pm/items/3179185

1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf

『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV

【booth(pdf)】
https://booth.pm/ja/items/3698647

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/

【booth(pdf)】
https://sano192.booth.pm/items/3698668

『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

ABC226~250、ARC129~139 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC129~139の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS

【booth(pdf)】
https://sano192.booth.pm/items/4025713

ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF

【booth(pdf)】
https://sano192.booth.pm/items/4025737

『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW

【booth(pdf】
https://sano192.booth.pm/items/3785312

21
32
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
21
32