競プロ備忘録

# 目的

AtCoder等の競技プログラミング問題において、考察または実装を短縮できるような知識だが、ライブラリ化する程でもないものを備忘録として記録しておく

# LCM, GCD

- 実装

```Python
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)は最大公約数を表す。覚えておくと自慢できる

# トポロジカルソート

```Python
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`を返り値とする

# 素数列挙

```Python
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`以下の素数リスト

# マージソート

```Python
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基底

- 問題例
    - https://atcoder.jp/contests/abc283/tasks/abc283_g

- 実装

```Python
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

```Python
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

[ここに書いてあることが全て](https://tjkendev.github.io/procon-library/python/string/sa_sa-is.html)

# 強連結成分分解

[ここに書いてあることが全て](https://manabitimes.jp/math/1250)

# ハフマン符号化

`p_list`は、各文字の出現比

```Python
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`には単語に出現する文字を入力

```Python
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
```