目的
AtCoder等の競技プログラミング問題において、考察または実装を短縮できるような知識だが、ライブラリ化する程でもないものを備忘録として記録しておく
LCM, GCD
- 実装
def gcd(x, y):
while y > 0:
x, y = y, x%y
return x
def lcm(x, y):
return x*y//gcd(x, y)
LCM(least common multiple)は最小公倍数、GCD(greatest common divisor)は最大公約数を表す。覚えておくと自慢できる
トポロジカルソート
def topological_sort(graph):
n = len(graph)
graph_inv = [set() for _ in range(n)]
for i in range(n):
for j in graph[i]:
graph_inv[j].add(i)
todo = [i for i in range(n) if len(graph_inv[i]) == 0]
li = []
while todo:
t = todo.pop()
li.append(t)
for i in graph[t]:
graph_inv[i].remove(t)
if len(graph_inv[i]) == 0:
todo.append(i)
if len(li) == n: return li
else: return None
- トポロジカルソートできる場合はソート後リスト、できない場合は
Noneを返り値とする
素数列挙
def enumerate_prime(n):
is_prime_list = [True]*(n+1)
is_prime_list[0], is_prime_list[1] = 0, 0
for i in range(2, int(n**(1/2))+1):
if is_prime_list[i] == False: continue
for j in range(i*i, n+1, i):
is_prime_list[j] = False
prime_list = [i for i in range(n+1) if is_prime_list[i]]
return prime_list
戻り値はn以下の素数リスト
マージソート
def merge_sort(li, key=lambda x: x):
todo = [(0, len(li))]
seen = set()
while todo:
l, r = todo[-1]
if (l, r) in seen or r-l <= 2:
mid = (l+r)//2
cursor = mid
tmp = []
for i in range(l, mid):
while cursor < r and key(li[cursor]) <= key(li[i]):
tmp.append(li[cursor])
cursor += 1
tmp.append(li[i])
tmp.extend(li[cursor:r])
li[l:r] = tmp
todo.pop()
else:
todo.append(((l+r)//2, r))
todo.append((l, (l+r)//2))
seen.add((l, r))
- あまり速くない
XOR基底
def find_xor_base(a_list):
base_list = []
for a in a_list:
for base in base_list:
a = min(a, a^base)
if a > 0:
for i in range(len(base_list)):
base_list[i] = min(base_list[i], base_list[i]^a)
base_list.append(a)
return sorted(base_list)
Mo's Algorithm
def mo_algorithm(n, query_list, add, sub, get):
q = len(query_list)
sq = int(q**(1/2)+1)
bucket_list = [[] for _ in range(sq)]
for i in range(q):
l, r = query_list[i]
ind = l * sq // n
bucket_list[ind].append((l, r, i))
for i in range(sq):
if i & 1: bucket_list[i].sort(key=lambda x: -x[1])
else: bucket_list[i].sort(key=lambda x: x[1])
cl, cr = 0, 0
ans_list = [-1]*q
for bucket in bucket_list:
for l, r, ind in bucket:
while l < cl:
cl -= 1
add(cl)
while cr < r:
add(cr)
cr += 1
while cl < l:
sub(cl)
cl += 1
while r < cr:
cr -= 1
sub(cr)
ans_list[ind] = get()
return ans_list
Suffix Array
強連結成分分解
ハフマン符号化
p_listは、各文字の出現比
from heapq import heappush, heappop, heapify
def huffman_encoding(p_list):
n = len(p_list)
todo = [(p, i) for i, p in enumerate(p_list)]
heapify(todo)
tree = [None]*n
while len(todo) > 1:
p1, t1 = heappop(todo)
p2, t2 = heappop(todo)
tree.append(None)
p3, t3 = p1+p2, len(tree)-1
tree[t1] = (t3, "0")
tree[t2] = (t3, "1")
heappush(todo, (p3, t3))
s_list = []
for i in range(n):
li = []
cursor = i
while tree[cursor]:
cursor, x = tree[cursor]
li.append(x)
s_list.append("".join(li))
return s_list
単語⇄辞書順index変換
patternsには単語に出現する文字を入力
class WordIndexConverter:
def __init__(self, patterns, MAX_INDEX=10**19):
self.patterns = patterns
self.patterns_dict = {u: i for i, u in enumerate(self.patterns)}
self.MAX_INDEX = MAX_INDEX
self.cycle_list = [1]
self.start_list = [1]
while self.start_list[-1] < MAX_INDEX:
self.cycle_list.append(self.cycle_list[-1]*len(self.patterns))
self.start_list.append(self.start_list[-1] + self.cycle_list[-1])
def word_to_idx(self, word):
idx = 0
if len(word) > len(self.cycle_list): return float('inf')
for i, w in enumerate(word[::-1]):
x = self.patterns_dict[w]+1
idx += x*self.cycle_list[i]
if idx > self.MAX_INDEX: return float('inf')
else: return idx
def idx_to_word(self, idx):
if idx > self.MAX_INDEX: raise Exception("idx must not be higher than MAX_INDEX")
w_list = []
for cycle, start in zip(self.cycle_list[::-1], self.start_list[::-1]):
x = (idx - start) // cycle
if x < 0: continue
w = self.patterns[x]
w_list.append(w)
idx -= (x+1) * cycle
word = "".join(w_list)
return word