自分の言葉でメモっておいた方が記憶に残るので、記事としてはn番煎じですがまとめていきます。
アルゴリズムまでは いかない細かいテクニックはこちらです。
aoki-shiraki21.hatenablog.com
探索
ビット全探索
n個のものからある要素を取るか、取らないかを全部列挙して探索する方法。
for分だと何回繰り返せば良いか分からない時に応用が効かないのでビット全探索か再帰関数で対応する。
O（n2）探索するので範囲が小さい時にしか使えないのは注意。
# よくある形
for i in range(1<<n): # 左シフトで2**nを作る
cnt = 0
for j in range(n): # 全ての選択肢について取る/取らないをチェックする
flg = True
if i >> j & 1: # ビットに復元して、その要素が含まれるかをチェックする
cnt += 1
if ~~ # 要素が含まれた時に満たすべき条件を書く
flg = False
break
if not flg:
break # 条件に当てはまらないときはフラグを使って二重ループを抜ける
if flg:
# 満たすべき条件がokだった時に最終的な処理をする
参考
bit 全探索 - けんちょんの競プロ精進記録
とにかく下に下に探索していく。下位構造が上位を決定しているようなときに便利。
1. グラフを行列で表す
2. 最初の頂点をスタックに積む
3. スタックに要素がある間、繰り返し
- スタックのトップを訪問する（訪問時の処理をする）
- 次の未訪問要素があればスタックに積む
- なければ訪問した要素をスタックから削除する（終了時の処理をする）
# デックにデータを格納しながら処理。popをどちらから行うかでDFSとBFSを切り替えられるのが楽
def search(G,s):
"""
グラフGに対し、頂点sを始点とする探索（デック）
"""
N = len(G)
todo = deque() # BFSならキュー、DFSならスタックとして使用
seen = [False]*N # 発見チェック（seen:True & not in todo => 訪問済み)
# 初期状態
seen[s] = True
todo.append(s)
# todoが空になるまで探索を行う
while todo:
v = todo.popleft() # DFSならpop()
for x in G[v]:
if seen[x]: # 発見済み
continue
seen[x] = True
todo.append(x)
# 再帰を使った処理。記述が簡潔、行きがけ/帰りがけの処理を書きやすい。
def dfs(G,v):
"""
頂点vから辿れる頂点を全て訪問する（再帰）
"""
# 訪問時の処理
seen[v] = True
# 再帰的に探索
for next_v in G[v]:
if seen[next_v]:
continue
dfs(G, next_v) # 再帰的に探索
# 帰りがけの処理
N,M = map(int,input().split())
G = [[] for i in range(N)] # 隣接リスト
for i in range(M):
a,b = map(int, input().split())
a -= 1
b -= 1
G[a].append(b)
print(G)
seen = [False]*N
for v in range(N): # 全頂点から探索
if seen[v]:
continue
dfs(G,v)
デックを使って順番を管理し、先頭から取り出して処理をする。処理途中で深さが発生する場合は、デックに追加しておくことで後から処理をできるようにする。
浅いところから順番に見て行くので、根からの最短経路を求めるのに向いている。
def BFS(G, s):
"""
グラフGに関して,頂点sからの最短路長を求める
input: グラフG, 探索の視点s
data: sからの距離dist配列(!=-1なら発見済み), 探索予定をキューとして格納するque
output: sから各頂点への最短路長を表すdist配列
"""
# 初期設定
N = len(G)
dist = [-1]*N
que = deque()
dist[s] = 0
que.append(s)
# 探索
while que:
v = que.popleft()
for x in G[v]:
if dist[x] != -1:
continue
dist[x] = dist[v] + 1
que.append(x)
return dist
N,M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
a,b = map(int, input().split())
a -= 1
b -= 1
G[a].append(b)
dist = BFS(G,0)
二分探索
短調増加（減少）の指標に対して中間地点をとってそれより大きいか小さいかで範囲を絞る。1回ごとに半分になるためlogスケールになり高速。
最大、最小系の問題は解を仮置きして二分探索に帰着させると計算量を抑えられる。
def is_ok(arg):
# 条件を満たすかどうか？問題ごとに定義
pass
def meguru_bisect(ng, ok):
'''
初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
まずis_okを定義すべし
ng ok は とり得る最小の値-1 とり得る最大の値+1
最大最小が逆の場合はよしなにひっくり返す
'''
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
計算
最大公約数
ユークリッドの互除法。
xをyで割ったあまりをrとすると、x,yの最大公約数とy,rの最大公約数は同じになる（証明はリンク先より）から割り切れるまで繰りかえり処理を行うことで求める。
def gcd(x, y): # ユークリッドの互除法
if y > x:
y,x = x,y
while y > 0:
r = x%y
x = y
y = r
return x
【ユークリッドの互除法】やり方＆証明を解説！センター試験にも役立つ！ | Studyplus（スタディプラス）
（実運用上は、mathモジュールに入っているのでそれで良いが。）
import math
math.gcd(x,y)
最小公倍数
最大公約数*最小公倍数=a*bというシンプルで綺麗な定理を使うとすぐに求められる。
a*b//bcd(a,b)
最大公約数と最小公倍数の積の性質の２通りの証明 | 高校数学の美しい物語
いもす法
Nコのデータに対するM回の処理共通範囲を求める処理をO(MN)からO(N+M)に減らす。始点と終点だけメモしておいて、最後に累積和をとる。
imos = [0]*(n+2)
for i in range(m):
a,b = i_map()
imos[a] += 1
imos[b+1] -= 1
imos = list(itertools.accumulate(imos))
単純な素数判定
nに対してsqrt(n)まで調べれば良い。
def isPrime(n):
if n == 2:
return True
if n%2 == 0 or n == 1:
return False
m = math.floor(math.sqrt(n))+1
for p in range(3,m,2):
if n%p == 0:
return False
return True
エラトステネスの篩
ある数までに含まれる素数を列挙する。sqrt(n)までに合成数は篩落とされるので高速。
def primes(n):
is_prime = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1):
if not is_prime[i]:
continue
for j in range(i * 2, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]], is_prime
素数でない限り、sqrt(n)より大きい素因数が発生することはないので、O(n1/2)で十分
def prime_decomposition(n):
i = 2
table = []
while i * i <= n: # sqrt(n)で計算が済む
while n % i == 0:
n //= i
table.append(i)
i += 1
if n > 1:
table.append(n)
return table
データ構造
キュー
FIFOで処理をする待ち行列。順番に処理をして、またその処理結果を順番に処理すると繰り返したいときに便利。
from collections import deque
q = deque([1,2,3,4,5,6,7,8,9])
for _ in range(k):
x = q.popleft()
q.append(x*10 + x0 - 1)
優先度付きキュー
要素の挿入、最大値（最小値）の抽出を繰り返したい時に使用する。
最小値しか取り出せないので、最大値を管理したい時にはマイナスをかけておいて、取り出した後マイナスをかけて復元処理をする。
import heapq
h = []
heapq.heappush(h, -i)
heapq.heappop(h)
UnionFind木
素集合データ構造を作成するクラス。経路圧縮と深さのランクづけで高速化を行なっている。
Python:Union-Find木について - あっとのTECH LOG
class UnionFind:
def __init__(self, n):
self.par = [i for i in range(n+1)]
self.rank = [0] * (n+1)
self.size = [1] * (n+1) # 親に集約される
# 検索
def find(self, x):
if self.par[x] == x:
return x
else:
self.par[x] = self.find(self.par[x])
return self.par[x]
# 併合
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.rank[x] < self.rank[y]:
self.par[x] = y
self.size[y] += self.size[x]
self.size[x] = 0
else:
self.par[y] = x
self.size[x] += self.size[y]
self.size[y] = 0
if self.rank[x] == self.rank[y]:
self.rank[x] += 1
# 同じ集合に属するか判定
def same(self, x, y):
return self.find(x) == self.find(y)
# すべての頂点に対して親を検索する
def all_find(self):
for n in range(len(self.par)):
self.find(n)
経路
ワーシャルフロイド法
全ての頂点間の最短距離を更新しながら求める方法。ぱっと見ただの三重ループの綺麗な形になっているのがすごい。計算量はそのままO(n3)。
素人によるワーシャルフロイド法 - Qiita
for k in range(10): # 経由
for i in range(10): # 始点
for j in range(10): # 終点
c[i][j] = min(c[i][j], c[i][k] + c[k][j])
# AtCoder用ライブラリ
"""
初期操作
"""
# 立ち上げ時のコピペ内容
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
import itertools
import bisect
import re
import numpy as np
from collections import Counter,deque,defaultdict
def iinput(): return int(input())
def imap(): return map(int, input().split())
def ilist(): return list(imap())
def irow(N): return [iinput() for i in range(N)]
def sinput(): return input().rstrip()
def smap(): return sinput().split()
def slist(): return list(smap())
def srow(N): return [sinput() for i in range(N)]
def main():
if __name__=="__main__":
main()
"""
配列操作
"""
# 組み合わせ系
## 順列
list(itertools.permutations(list, n))
## 組み合わせ
list(itertools.combinations(list, n))
## 出現回数
l = Counter(list)
l.most_common()
## nCrのmod計算
def fur(n,r):
p,q = 1, 1
for i in range(r): # p=(n-r+1)!,q=r!を作る
p = p*(n-i)%MOD
q = q*(i+1)%MOD
return (p * pow(q,MOD-2,MOD)) % MOD # qの逆元を作ってp/qを処理する
## 普通のnCr
def comb(n, r):
if n-r>=0:
return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
else:
return 0
"""
数値計算
"""
## 単純な素数判定
def isPrime(n):
if n == 2:
return True
if n%2 == 0 or n == 1:
return False
m = math.floor(math.sqrt(n))+1
for p in range(3,m,2):
if n%p == 0:
return False
return True
## エラトステネスの篩（素数列挙）
def primes(n):
if n <= 0:
return []
is_prime = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1):
if not is_prime[i]:
continue
for j in range(i * 2, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
## 最大公約数
gcd(a,b)
## 最小公倍数
a*b//gcd(a,b)
## 素因数分解(一次元配列)
def prime_decomposition(n):
i = 2
table = []
while i * i <= n: # sqrt(n)で計算が済む
while n % i == 0:
n //= i
table.append(i)
i += 1
if n > 1:
table.append(n)
return table
## 素因数分解（素因数、指数の二次元配列）
def prime_decomposition_2dim(n):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
## 約数列挙
def make_divisors(n):
lower_divisors , upper_divisors = [], []
i = 1
while i*i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n//i)
i += 1
return lower_divisors + upper_divisors[::-1]
## 公約数列挙
def common_divisors(n, m):
n = gcd(n,m)
lower_divisors , upper_divisors = [], []
i = 1
while i*i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n//i)
i += 1
return lower_divisors + upper_divisors[::-1]
## 10進数からn進数への変換
def Base_10_to_n(X, n):
if (int(X/n)):
return Base_10_to_n(int(X/n), n)+str(X%n)
return str(X%n)
"""
2次元配列操作
"""
## 転置行列
l_2 = [list(x) for x in zip(*l)]
## 8方向への移動
dx=[0,1,0,-1,1,1,-1,-1]
dy=[1,0,-1,0,1,-1,1,-1]
"""
幾何
"""
### 2点を通る直線
def line(x0,y0,x1,y1): # (x0,y0),(x1,y1)を通る直線ax+by+c=0を求める
x = (d-b)
y = -c+a
z = b*(c-a) - a*(d-b)
return x,y,z
### 点と直線の距離
def dist(x0,y0,a,b,c): # (x0,y0)から直線ax+by+c=0までの距離を求める
up = abs(a*x0 + b*y0 + c)
down = math.sqrt(a**2 + b**2)
return up/down
