【AtCoder】文系大学生がアルゴリズム・ヒューリスティックで青色になるまで（色変記事）🚶♂️🏔
ABC265で念願の青色を達成しました🎉#AtCoder #ABC265 pic.twitter.com/5amuhTkgL1
— cozy_sauna (@cozy_sauna) August 21, 2022
自己紹介 🥴
- cozy_sauna（サウナが大好きです🧖）
- Doer（同志社大学プログラミングサークル）在籍
- 文系学部（国際系）4回生
- Pythonで参加🐍
- コンテスト初参加・Python学習スタート【2021/1/9 (ARC111)】
- ヒューリスティック青色達成🎉【2022/2/26(AHC008)】
- アルゴリズム青色達成🎉【2022/8/21(ABC265)】
- ICPCアジア地区大会2022参加予定🍨
- AtCoder【cozy_sauna】
競プロを始めるまでは
- プログラミング未経験🧑💻
→ Pythonって…ニシキヘビ？🐍🐍
→ JavaScript？なんじゃそりゃ…（語感踏みなら、讃岐うどんだな…)
→ HTML, CSSを少しだけ授業で習った - 高校数学（数Ⅲまで）は分かる！大学数学（行列など）は全く…🔢
History 🚶♂️
やったこと🏋️♀️
基本的には...
■ 習うより慣れろ!問題をガツガツ解くぞ!スタイル⚔️
→ AtCoderProblemsを使用しました
→ 競プロ本は使用していません（書籍での学習は苦手です...📚）
■ コンテストにはできる限り参加する🖥
→ 競プロを始めた日にもARCに参加していました😇
■ 問題を解く→復習→問題を解く…をひたすら繰り返す♻️
灰色🐘茶色🐿
■ Pythonの入力受け取りを覚える
→【参考記事】https://qiita.com/jamjamjam/items/e066b8c7bc85487c0785
■ 動画で、Pythonの文法を覚える
→ 競プロYouTuberのcatupperさんのYouTubeで学習を行いました
→ 本当に分かりやすく、始めたての頃は一日中動画を見ていた記憶があります
→【参考動画】catupperさん
■ 問題を解く⇔復習
→問題を解く⇔動画で復習 or 人のコードを見る、これをひたすら繰り返しました
緑色🍀
■ 問題を解く中で出会ったアルゴリズムをライブラリ化をしました
■ AtCoderのスニペットを整理しました
→ご自由にお使いください 😝
AtCoderスニペット🔥🔥🔥
from sys import setrecursionlimit, stdin
from collections import defaultdict, deque, Counter
from itertools import permutations, combinations, product
from functools import lru_cache
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from copy import copy, deepcopy
from decimal import Decimal
# from pypyjit import set_param
# set_param('max_unroll_recursion=-1')
setrecursionlimit(1 << 20)
readline = stdin.readline
INF = 10 ** 18
MOD = 998244353
# MOD = 1000000007
DYDX = [(-1, 0), (1, 0), (0, -1), (0, 1)]
ALP = 26
''' Input '''
def I(): return int(readline())
def ST(): return readline()[:-1]
def LI(): return list(map(int, readline().split()))
def LII(): return list(map(lambda x: int(x) - 1, readline().split()))
def LF(x, func): return [func() for _ in [0] * x]
def SPI(): return map(int, readline().split())
def SPII(): return map(lambda x: int(x) - 1, readline().split())
def FIE(x): return [readline()[:-1] for _ in [0] * x]
''' Array '''
def cmin(dp, i, x):
if x < dp[i]: dp[i] = x
def cmax(dp, i, x):
if x > dp[i]: dp[i] = x
''' Alphabet '''
def id_a(s): return ord(s) - ord('a')
def id_A(s): return ord(s) - ord('A')
def st_a(i): return chr(ord('a') + i)
def st_A(i): return chr(ord('A') + i)
''' Other'''
def ranges(*args): return [(i, j) for i in range(args[0]) for j in range(args[-1])]
def nynx(y, x, ly = INF, lx = INF): return [(y + dy, x + dx) for dy, dx in DYDX if 0 <= y + dy < ly and 0 <= x + dx < lx]
def gen(x, *args):
if len(args) == 1: return [x] * args[0]
if len(args) == 2: return [[x] * args[1] for _ in [0] * args[0]]
if len(args) == 3: return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]]
if len(args) == 4: return [[[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]] for _ in [0] * args[0]]
''' Output '''
def puts(E):
for e in E: print(e)
def pprint(E):
print()
for e in E: print(e)
def Yes(): print("Yes")
def No(): print("No")
def YES(): print("YES")
def NO(): print("NO")
def yn(x): print("Yes" if x else "No")
def YN(x): print("YES" if x else "NO")
###############################################################################################
print("ここからコードを書き始めます")
水色🐳
■ バーチャルコンテストに参加する
→ レートが頭打ちになったため、コンテストで難しい問題を解く方針ではなく、簡単な問題を速く解いてレートを上げる方針に変更しました。
→ 簡単な問題に慣れるため、可能であれば毎日下記バーチャルコンテストに参加しました。
| コンテスト名 | 詳細 |
|---|---|
| ☕あさかつ | 毎朝7時半〜8時半に開催されています |
| 🌽まよコン | 毎日夜9時〜10時40分に開催されています |
（※バーチャルコンテストはAtCoderProblemsから参加することができます）
青色🫐
■ 約1年半で青色達成しました🎉 青色を目標にしていたので、とても嬉しいです
学習したアルゴリズム一覧
■ アルゴリズムをクリックするとPythonでの実装コードを確認できます↓
vscode ユーザースニペット🆚👩💻
■ ユーザスニペットに下記を設定すると、_アルゴリズム名と打つだけで、アルゴリズムコードがでてきます！
■ また_mainと打つとmainのAtCoderのスニペットが登場します。
ユーザースニペット🔥🔥
{
// main
"main": {
"prefix": "_main",
"body": [
"from sys import setrecursionlimit, stdin",
"from collections import defaultdict, deque, Counter",
"from itertools import permutations, combinations, product",
"from functools import lru_cache",
"from bisect import bisect_left, bisect_right",
"from heapq import heappush, heappop",
"from copy import copy, deepcopy",
"from decimal import Decimal",
"# from pypyjit import set_param",
"# set_param('max_unroll_recursion=-1')",
"",
"setrecursionlimit(1 << 20)",
"readline = stdin.readline",
"INF = 10 ** 18",
"MOD = 998244353",
"# MOD = 1000000007",
"DYDX = [(-1, 0), (1, 0), (0, -1), (0, 1)]",
"ALP = 26",
"''' Input '''",
"def I(): return int(readline())",
"def ST(): return readline()[:-1]",
"def LI(): return list(map(int, readline().split()))",
"def LII(): return list(map(lambda x: int(x) - 1, readline().split()))",
"def LF(x, func): return [func() for _ in [0] * x]",
"def SPI(): return map(int, readline().split())",
"def SPII(): return map(lambda x: int(x) - 1, readline().split())",
"def FIE(x): return [readline()[:-1] for _ in [0] * x]",
"''' Array '''",
"def cmin(dp, i, x):",
" if x < dp[i]: dp[i] = x",
"def cmax(dp, i, x):",
" if x > dp[i]: dp[i] = x",
"",
"''' Alphabet '''",
"def id_a(s): return ord(s) - ord('a')",
"def id_A(s): return ord(s) - ord('A')",
"def st_a(i): return chr(ord('a') + i)",
"def st_A(i): return chr(ord('A') + i)",
"",
"''' Other'''",
"def ranges(*args): return [(i, j) for i in range(args[0]) for j in range(args[-1])]",
"def nynx(y, x, ly = INF, lx = INF): return [(y + dy, x + dx) for dy, dx in DYDX if 0 <= y + dy < ly and 0 <= x + dx < lx]",
"def gen(x, *args):",
" if len(args) == 1: return [x] * args[0]",
" if len(args) == 2: return [[x] * args[1] for _ in [0] * args[0]]",
" if len(args) == 3: return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]]",
" if len(args) == 4: return [[[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]] for _ in [0] * args[0]]",
"''' Output '''",
"def puts(E):",
" for e in E: print(e)",
"def pprint(E): ",
" print()",
" for e in E: print(e)",
"def Yes(): print(\"Yes\")",
"def No(): print(\"No\")",
"def YES(): print(\"YES\")",
"def NO(): print(\"NO\")",
"def yn(x): print(\"Yes\" if x else \"No\")",
"def YN(x): print(\"YES\" if x else \"NO\")",
"###############################################################################################",
"",
""
],
"description": "main"
},
// geometry
"line_equation": {
"prefix": "_line_equation",
"body": [
"# Equation which passes through the two points (x1, y1), (x2, y2)",
"# (a, b, c) (ax + by + c = 0)",
"def line_equation(x1, y1, x2, y2): ",
" a = y1 - y2 ",
" b = x2 - x1 ",
" c = y1 * (x1 - x2) - x1 * (y1 - y2)",
" return a, b, c ",
""
],
"description": "line_equation"
},
"point_line_distance": {
"prefix": "_point_line_distance",
"body": [
"# distance of ax + by + c = 0 and (x, y)",
"def point_line_distance(a, b, c, x, y):",
" return abs(a * x + b * y + c) / (a ** 2 + b ** 2) ** .5",
""
],
"description": "point_line_distance"
},
"rot": {
"prefix": "_rot",
"body": [
"def rot(A): return [*map(list, zip(*A[::-1]))]",
""
],
"description": "rot"
},
"rot_degree": {
"prefix": "_rot_degree",
"body": [
"from math import pi, sin, cos",
"",
"def rot_degree(x, y, d):",
" rad = d * pi / 180",
" _x = x * cos(rad) - y * sin(rad)",
" _y = y * cos(rad) + x * sin(rad)",
" return (_x, _y)",
""
],
"description": "rot_degree"
},
"rot_radian": {
"prefix": "_rot_radian",
"body": [
"from math import sin, cos",
"",
"def rot_radian(x, y, rad):",
" _x = x * cos(rad) - y * sin(rad)",
" _y = y * cos(rad) + x * sin(rad)",
" return (_x, _y)",
""
],
"description": "rot_radian"
},
"three_point_circle": {
"prefix": "_three_point_circle",
"body": [
"# (center_x, center_y), radius",
"def three_point_circle(x1, y1, x2, y2, x3, y3):",
" i = 2 * (x1 - x2)",
" j = 2 * (y1 - y2)",
" k = 2 * (x1 - x3)",
" l = 2 * (y1 - y3)",
" m = x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2",
" n = x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2",
" deno = k * j - i * l ",
" if deno == 0: return (None, None), None",
" y = (m * k - n * i) / deno",
" x = (n * j - m * l) / deno",
" r = (x1 - x) ** 2 + (y1 - y) ** 2",
" return (x, y), r ** .5",
""
],
"description": "three_point_circle"
},
"triangle_area": {
"prefix": "_triangle_area",
"body": [
"def triangle_area(ax, ay, bx, by, cx, cy): return abs((ax - cx) * (by - cy) - (bx - cx)* (ay - cy)) / 2 ",
""
],
"description": "triangle_area"
},
// graph
"bellman_ford": {
"prefix": "_bellman_ford",
"body": [
"def bellman_ford(N, node, start = 0):",
" dist = [10 ** 18] * N",
" dist[start] = 0",
" for _ in range(N):",
" update = False",
" for x, y, c in node:",
" if dist[y] > dist[x] + c:",
" dist[y] = dist[x] + c",
" update = True",
" if not update: break",
" ",
" # find negative cycle",
" negative_flag = [0] * N",
" for _ in range(N):",
" for x, y, c in node:",
" if dist[x] == 10 ** 18: continue",
" if dist[y] > dist[x] + c:",
" dist[y] = dist[x] + c",
" negative_flag[y] = 1",
" if negative_flag[x]: ",
" negative_flag[y] = 1",
"",
" return dist, negative_flag",
""
],
"description": "bellman_ford"
},
"bit": {
"prefix": "_bit",
"body": [
"class BIT(): # 1-indexed",
" def __init__(self, N):",
" self.size = N",
" self.tree = [0] * (N + 1)",
" self.arr = [0] * (N + 1)",
" ",
" # A[i] += x",
" def add(self, i, x):",
" self.arr[i] += x",
" while i <= self.size:",
" self.tree[i] += x",
" i += i & -i",
"",
" # A[i] = x ",
" def update(self, i, x):self.add(i, x - self.arr[i])",
"",
" # A[1] + A[2] + ... + A[i]",
" def sum(self, i):",
" ret = 0",
" while i > 0:",
" ret += self.tree[i]",
" i -= i & -i",
" return ret",
"",
" # A[i]",
" def get(self, i): return self.arr[i]",
"",
" # max_i (i <= x and A[i] > 0)",
" def less_than_x(self, x):",
" base = self.sum(x)",
" if base == 0: return None ",
" ng, ok = 0, x",
" while ok - ng > 1:",
" mid = ok + ng >> 1",
" if self.sum(mid) == base: ok = mid ",
" else: ng = mid ",
" return ok ",
"",
" # min_i (i >= x and A[i] > 0)",
" def more_than_x(self, x):",
" base = self.sum(x - 1)",
" if self.get_all_sum() - base == 0: return None ",
" ng, ok = x - 1, self.size",
" while ok - ng > 1:",
" mid = ng + ok >> 1",
" if self.sum(mid) - base == 0: ng = mid ",
" else: ok = mid ",
" return ok",
"",
" def get_all_sum(self): return self.sum(self.size)",
"",
" def display_all(self): print(*self.arr[1:])",
""
],
"description": "bit"
},
"bit_2d": {
"prefix": "_bit_2d",
"body": [
"class BIT_2d:",
" # 0-indexed",
" def __init__(self, H, W):",
" self.H = H + 1",
" self.W = W + 1",
" self.arr = [0] * self.W * self.H",
" ",
" def add(self, i, j, x):",
" i += 1",
" j += 1",
" _j = j",
" arr = self.arr",
" H = self.H",
" W = self.W",
" while i < H:",
" j = _j",
" while j < W:",
" arr[i * W + j] += x",
" j += j & - j",
" i += i & -i",
"",
" def sum(self, i, j):",
" arr = self.arr",
" ret = 0",
" _j = j",
" W = self.W",
" while i:",
" j = _j",
" while j:",
" ret += arr[i * W + j]",
" j -= j & -j",
" i -= i & - i",
" return ret",
"",
" # x0 <= x < x1 and y0 <= y < y1",
" def range_sum(self, x0, x1, y0, y1):",
" return self.sum(x1, y1) - self.sum(x1, y0) - self.sum(x0, y1) + self.sum(x0, y0)",
""
],
"description": "bit_2d"
},
"dijksta": {
"prefix": "_dijkstra",
"body": [
"class Dikstra:",
" def __init__(self, N, node):",
" self.node = node ",
" self.N = N ",
" self.start_node = None",
" self.prev = [None] * N ",
"",
" def get(self, start):",
" self.start_node = start",
" dist, done = [10 ** 18] * self.N, [0] * self.N",
" hq = [(0, start)] # (cost, node)",
" dist[start] = 0",
" while hq:",
" c, v = heappop(hq)",
" if done[v]: continue",
" done[v] = 1",
" for to, cost in self.node[v]: ",
" new_cost = dist[v] + cost",
" if not done[to] and new_cost < dist[to]:",
" dist[to] = new_cost",
" self.prev[to] = v",
" heappush(hq, (dist[to], to))",
" return dist",
"",
" def init_prev(self): self.prev = [None] * self.N",
"",
" def get_path(self, start, to):",
" if self.start_node != start:",
" self.init_prev()",
" self.get(start)",
" ",
" path = []",
" while to != None:",
" path.append(to)",
" to = self.prev[to]",
"",
" return path[::-1]",
""
],
"description": "dijksta"
},
"dinic": {
"prefix": "_dinic",
"body": [
"class Dinic:",
" def __init__(self, N):",
" self.N = N",
" self.node = [[] for _ in range(N)]",
"",
" def add_edge(self, x, y, capacity): # x -> y",
" self.node[x].append([y, capacity, len(self.node[y])]) # to, capacity, rev",
" self.node[y].append([x, 0, len(self.node[x]) - 1])",
"",
" def bfs(self, start):",
" self.level = [-1] * self.N ",
" self.level[start] = 0",
" que = deque([start])",
" while que:",
" v = que.popleft()",
" for to, capacity, _ in self.node[v]:",
" if capacity > 0 and self.level[to] < 0:",
" self.level[to] = self.level[v] + 1",
" que.append(to)",
"",
" def dfs(self, s, t, flow):",
" if s == t: return flow ",
" for i in range(self.iter[s], len(self.node[s])):",
" self.iter[s] = i ",
" to, capacity, rev = self.node[s][i]",
" if capacity > 0 and self.level[s] < self.level[to]:",
" pre_flow = self.dfs(to, t, min(flow, capacity))",
" if pre_flow > 0:",
" self.node[s][i][1] -= pre_flow",
" self.node[to][rev][1] += pre_flow",
" return pre_flow",
" return 0",
"",
" def flow(self, s, t):",
" mx_flow = 0",
" while True:",
" self.bfs(s)",
" if self.level[t] < 0: break",
" self.iter = [0] * self.N ",
" while True:",
" f = self.dfs(s, t, 10 ** 18)",
" if f == 0: break ",
" mx_flow += f",
" ",
" return mx_flow",
""
],
"description": "dinic"
},
"euler_tour": {
"prefix": "_euler_tour",
"body": [
"class RMQ:",
" def __init__(self, array):",
" N = len(array)",
" self.e = 10 ** 18",
" self.num = 1 << (N - 1).bit_length()",
" self.tree = [self.e] * 2 * self.num",
" self.index = [None] * 2 * self.num ",
" for i in range(N):",
" self.tree[self.num + i] = array[i]",
" self.index[self.num + i] = i ",
"",
" for i in range(self.num - 1, 0, -1):",
" if self.tree[2 * i] <= self.tree[2 * i + 1]:",
" self.tree[i] = self.tree[2 * i]",
" self.index[i] = self.index[2 * i]",
" else:",
" self.tree[i] = self.tree[2 * i + 1]",
" self.index[i] = self.index[2 * i + 1]",
"",
" def query(self, l, r): #(mn, idx)",
" l += self.num",
" r += self.num",
" mn, idx = self.e, None",
"",
" while l < r:",
" if l & 1:",
" if mn >= self.tree[l]:",
" mn = self.tree[l]",
" idx = self.index[l]",
" l += 1",
" if r & 1:",
" if mn >= self.tree[r - 1]:",
" mn = self.tree[r - 1]",
" idx = self.index[r - 1]",
"",
" l >>= 1",
" r >>= 1",
" return mn, idx ",
"",
"class RSQ:",
" def __init__(self, array):",
" N = len(array)",
" self.e = 0",
" self.num = 1 << (N - 1).bit_length()",
" self.tree = [self.e] * 2 * self.num",
" for i in range(N): self.tree[self.num + i] = array[i]",
" for i in range(self.num - 1, 0, -1): self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]",
"",
" def query(self, l, r): # [l, r)",
" ret = self.e",
" l += self.num",
" r += self.num",
" while l < r:",
" if l & 1: ret += self.tree[l]; l += 1",
" if r & 1: ret += self.tree[r - 1]",
" l >>= 1",
" r >>= 1",
" return ret",
"",
"class EulerTour:",
" def __init__(self, N, node, start = 0):",
" self.N = N ",
" self.node = node ",
" self.info_index = [",
" {",
" 'depth':None, ",
" 'in': None, ",
" 'out': None",
" } ",
" for _ in range(N)",
" ]",
" self.step = 0",
" self._dfs_index(start)",
" self.info_step = [",
" {",
" 'now': None, ",
" 'in_v_cost': None, ",
" 'in_e_cost': None, ",
" 'depth': None",
" }",
" for _ in range(self.step)",
" ]",
" self._initialize_step()",
" self._dfs_step(start)",
"",
" # LCA",
" depths = [self.info_step[i]['depth'] for i in range(self.step)]",
" self.depth_rmq = RMQ(depths)",
"",
" #subtree_nodes_cost",
" nodes = []",
" for i in range(self.step):",
" _in_v_cost = self.info_step[i]['in_v_cost']",
" if _in_v_cost == None: _in_v_cost = 0",
" nodes.append(_in_v_cost)",
" self.nodes_rsq = RSQ(nodes)",
"",
" #subtree_edges_cost ",
" edges = []",
" for i in range(self.step):",
" _in_e_cost = self.info_step[i]['in_e_cost']",
" if _in_e_cost == None: _in_e_cost = 0",
" edges.append(_in_e_cost)",
" self.edges_rsq = RSQ(edges)",
"",
" def get_lca(self, x, y):",
" L = min(self.info_index[x]['in'], self.info_index[y]['in'])",
" R = max(self.info_index[x]['out'], self.info_index[y]['out'])",
" idx = self.depth_rmq.query(L, R)[1]",
" return self.info_step[idx]['now']",
"",
" def get_subtree_nodes_cost(self, x):",
" L = self.info_index[x]['in']",
" R = self.info_index[x]['out']",
" return self.nodes_rsq.query(L, R - 1)",
"",
" def get_subtree_edges_cost(self, x):",
" L = self.info_index[x]['in']",
" R = self.info_index[x]['out']",
" return self.edges_rsq.query(L + 1, R - 1)",
"",
" def _initialize_step(self): self.step = 0",
" def _add_step(self): self.step += 1",
"",
" def _dfs_index(self, x, p = -1, depth = 0):",
" self.info_index[x]['depth'] = depth",
" self.info_index[x]['in'] = self.step",
" self._add_step()",
" for nx, _ in self.node[x]:",
" if nx == p: continue",
" self._dfs_index(nx, x, depth + 1)",
" self._add_step()",
" ",
" self.info_index[x]['out'] = self.step",
"",
" def _dfs_step(self, x, p = -1, depth = 0, cost = 0):",
" self.info_step[self.step] = {",
" 'now': x, ",
" 'in_v_cost': x, ",
" 'in_e_cost': cost, ",
" 'depth': depth",
" }",
" self._add_step()",
" for nx, c in self.node[x]:",
" if nx == p: continue",
" self._dfs_step(nx, x, depth + 1, c)",
" self.info_step[self.step] = {",
" 'now': x, ",
" 'in_v_cost': None, ",
" 'in_e_cost': None, ",
" 'depth': depth",
" }",
" self._add_step()",
"",
" def verbose(self):",
" print('INDEX', *self.info_index, sep = '\\n')",
" print('STEP', *self.info_step, sep = '\\n')"
],
"description": "euler_tour"
},
"lca": {
"prefix": "_lca",
"body": [
"class LCA:",
" def __init__(self, node, root = 0):",
" self.node = node",
" self.root = root",
" self.N = len(node)",
" self.logn = (self.N - 1).bit_length()",
" self.depth = [-1 if i != root else 0 for i in range(self.N)]",
" self.parent = [[-1] * self.N for _ in range(self.logn)]",
" self.dfs()",
" self.doubling()",
"",
" def dfs(self):",
" que = [self.root]",
" while que:",
" u = que.pop()",
" for v in self.node[u]:",
" if self.depth[v] == -1:",
" self.depth[v] = self.depth[u] + 1",
" self.parent[0][v] = u",
" que.append(v)",
"",
" def doubling(self):",
" for i in range(1, self.logn):",
" for v in range(self.N):",
" if self.parent[i - 1][v] != -1:",
" self.parent[i][v] = self.parent[i - 1][self.parent[i - 1][v]]",
"",
" def get(self, u, v):",
" if self.depth[v] < self.depth[u]: u, v = v, u",
" du = self.depth[u]",
" dv = self.depth[v]",
"",
" for i in range(self.logn):",
" if (dv - du) >> i % 2:",
" v = self.parent[i][v]",
" if u == v: return u",
" for i in range(self.logn - 1, -1, -1):",
" pu, pv = self.parent[i][u], self.parent[i][v]",
" if pu != pv: u, v = pu, pv",
"",
" return self.parent[0][u]",
""
],
"description": "lca"
},
"lis": {
"prefix": "_lis",
"body": [
"",
"def lis(A):",
" table = [A[0]]",
" for a in A:",
" if a > table[-1]: table.append(a)",
" else: table[bisect_left(table, a)] = a",
" ",
" return len(table)",
""
],
"description": "lis"
},
"lowlink": {
"prefix": "_lowlink",
"body": [
"class LowLink:",
" def __init__(self, N, node, root = 0):",
" self.N = N ",
" self.node = node ",
" self.ord = [None] * N",
" self.low = [None] * N",
" self.k = 0",
" self.root = root ",
" self.articulation_points = []",
" self.bridges = []",
" self.dfs(root)",
"",
" def dfs(self, x, p = -1):",
" self.ord[x] = self.k",
" self.low[x] = self.k",
" self.k += 1",
" child = 0",
" ap_flag = False ",
" for nx in self.node[x]:",
" if nx == p: continue ",
" if self.ord[nx] == None:",
" self.dfs(nx, x)",
" self.low[x] = min(self.low[x], self.low[nx])",
" child += 1",
" if self.ord[x] <= self.low[nx]: ap_flag = True",
" if self.ord[x] < self.low[nx]: self.bridges.append((x, nx))",
" else:",
" self.low[x] = min(self.low[x], self.ord[nx])",
" ",
" if (x == self.root and child > 1) or (x != self.root and ap_flag):",
" self.articulation_points.append(x)",
"",
" def get_bridges(self): return self.bridges",
" ",
" def get_articulation_points(self): return self.articulation_points",
""
],
"description": "lowlink"
},
"min_cost_flow": {
"prefix": "_min_cost_flow",
"body": [
"class MinCostFlow:",
" def __init__(self, N):",
" self.N = N ",
" self.node = [[] for _ in [0] * N]",
"",
" def add_edge(self, x, y, capacity, cost): # x -> y",
" self.node[x].append([y, capacity, cost, len(self.node[y])])",
" self.node[y].append([x, 0, -cost, len(self.node[x]) - 1])",
"",
" def min_cost_flow(self, x, y, flow):",
" ret = 0",
" H = [0] * self.N",
" prev_v = [0] * self.N ",
" prev_e = [0] * self.N",
" while flow:",
" dist = [INF] * self.N ",
" dist[x] = 0",
" que = [(0, x)]",
" while que:",
" c, v = heappop(que)",
" if dist[v] < c: continue ",
" for i, (to, capacity, cost, _) in enumerate(self.node[v]):",
" new_cost = dist[v] + cost + H[v] - H[to]",
" if capacity > 0 and dist[to] > new_cost:",
" dist[to] = new_cost",
" prev_v[to] = v ",
" prev_e[to] = i",
" heappush(que, (new_cost, to))",
"",
" if dist[y] == INF: return None",
" for i in range(self.N): H[i] += dist[i]",
"",
" _flow = flow ",
" _y = y ",
" while _y != x:",
" _flow = min(_flow, self.node[prev_v[_y]][prev_e[_y]][1])",
" _y = prev_v[_y]",
"",
" flow -= _flow ",
" ret += _flow * H[y]",
" _y = y ",
" while _y != x:",
" e = self.node[prev_v[_y]][prev_e[_y]]",
" e[1] -= _flow",
" self.node[_y][e[3]][1] += _flow ",
" _y = prev_v[_y]",
" return ret ",
""
],
"description": "min_cost_flow"
},
"prim": {
"prefix": "_prim",
"body": [
"",
"def prim(node, N):",
" ans = 0",
" cnt = 0",
" que = [(0, 0)]",
" done = [0] * N",
" while que:",
" c, v = heappop(que)",
" if done[v]: continue",
" done[v] = 1",
" cnt += 1",
" ans += c",
" if cnt == N: break",
" for nx, cost in node[v]: ",
" if done[nx]: continue",
" heappush(que, (cost, nx))",
"",
" return ans"
],
"description": "prim"
},
"removable_heapq": {
"prefix": "_removable_heapq",
"body": [
"class RemovableHeapq:",
" def __init__(self):",
" self.que = []",
" self.cnt = defaultdict(int)",
"",
" def push(self, x):",
" heappush(self.que, x)",
" self.cnt[x] += 1",
"",
" def pop(self):",
" self._clean_que()",
" x = heappop(self.que)",
" self.cnt[x] -= 1",
" return x ",
" ",
" def remove(self, x): self.cnt[x] = max(0, self.cnt[x] - 1)",
"",
" def remove_all(self, x): self.cnt[x] = 0",
"",
" def min(self):",
" self._clean_que()",
" return self.que[0]",
" ",
" def is_empty(self): ",
" self._clean_que()",
" return len(self.que) == 0",
"",
" def _clean_que(self):",
" while self.que and self.cnt[self.que[0]] == 0: ",
" heappop(self.que)",
""
],
"description": "removable_heapq"
},
"rerooting": {
"prefix": "_rerooting",
"body": [
"class Rerooting:",
" def __init__(self, N, node, e):",
" self.dp = [None] * N",
" self.node = node ",
" self.e = e",
" self.ans = [0] * N",
"",
" # Abstraction",
" def merge(self, a, b): return max(a, b)",
" def fin(self, a): return a + 1",
" def build(self, start = 0, initial_cost = 0):",
" self._dfs1(start)",
" self._dfs2(start, initial_cost)",
"",
" def _dfs1(self, v, p = -1):",
" self.dp[v] = [self.e] * len(self.node[v])",
" ret = self.e",
" for i, nx in enumerate(self.node[v]):",
" if nx == p: continue",
" self.dp[v][i] = self._dfs1(nx, v)",
" ret = self.merge(ret, self.dp[v][i])",
" return self.fin(ret)",
"",
" def _dfs2(self, v, cost, p = -1):",
" size = len(self.node[v])",
"",
" for i, nx in enumerate(self.node[v]):",
" if nx == p: self.dp[v][i] = cost ",
"",
" cumL = [self.e] * (size + 1)",
" cumR = [self.e] * (size + 1)",
" for i in range(size): ",
" cumL[i + 1] = self.merge(cumL[i], self.dp[v][i])",
" for i in range(size)[::-1]:",
" cumR[i] = self.merge(cumR[i + 1], self.dp[v][i])",
" ",
" for i, nx in enumerate(self.node[v]):",
" if nx == p: continue",
" self._dfs2(nx, self.fin(self.merge(cumL[i], cumR[i + 1])), v)",
""
],
"description": "rerooting"
},
"scc": {
"prefix": "_scc",
"body": [
"class SCC:",
" def __init__(self, N, node):",
" self.N = N",
" self.node = node",
" self.inv_node = [[] for _ in range(self.N)]",
" for i in range(N):",
" for v in node[i]:",
" self.inv_node[v].append(i)",
"",
" self.order = []",
" self.done = [0] * N",
" for i in range(N):",
" if not self.done[i]: ",
" self.dfs(i)",
"",
" self.inv_done = [0] * N",
" self.group_members = {}",
" self.group = [None] * N",
" self.g = 0 # group count",
" for v in self.order[::-1]:",
" if not self.inv_done[v]: ",
" self.group_members[self.g] = []",
" self.inv_dfs(v)",
" self.g += 1",
"",
" def dfs(self, x):",
" self.done[x] = 1",
" for nx in self.node[x]:",
" if not self.done[nx]: ",
" self.dfs(nx)",
" self.order.append(x)",
"",
" def inv_dfs(self, x):",
" self.inv_done[x] = 1",
" self.group_members[self.g].append(x)",
" self.group[x] = self.g",
" for nx in self.inv_node[x]:",
" if not self.inv_done[nx]: ",
" self.inv_dfs(nx)",
"",
" def get_group(self, x): return self.group[x]",
"",
" def same(self, x, y): return self.group[x] == self.group[y]",
""
],
"description": "scc"
},
"topological_sort": {
"prefix": "_topological_sort",
"body": [
"def topological_sort(node, N):",
" incnt = [0] * N ",
" for nxs in node:",
" for nx in nxs:",
" incnt[nx] += 1",
"",
" que = deque([i for i in range(N) if not incnt[i]])",
" ret = []",
" while que:",
" v = que.popleft()",
" ret.append(v)",
" for nx in node[v]:",
" incnt[nx] -= 1",
" if not incnt[nx]:",
" que.append(nx)",
"",
" return ret",
""
],
"description": "topological_sort"
},
"tree_diameter": {
"prefix": "_tree_diameter",
"body": [
"class TreeDiameter:",
" def __init__(self, N, node):",
" self.node = node ",
" self.N = N",
"",
" def get(self):",
" _, mx_idx = self.bfs()",
" mx_d, _ = self.bfs(mx_idx)",
" return mx_d",
"",
" def bfs(self, start = 0):",
" dist = [10 ** 18] * self.N",
" q = deque([start])",
" dist[start] = 0",
" while q:",
" v = q.popleft()",
" for nx, c in self.node[v]:",
" if dist[nx] > dist[v] + c:",
" q.append(nx)",
" dist[nx] = dist[v] + c",
" ",
" mx_d = max(dist)",
" mx_idx = dist.index(mx_d)",
" return mx_d, mx_idx",
""
],
"description": "tree_diameter"
},
"union_find": {
"prefix": "_union_find",
"body": [
"class UnionFind:",
" def __init__(self, n):",
" self.n = n",
" self.P = [-1] * n # parents",
"",
" def find(self, x):",
" if self.P[x] < 0: return x",
" self.P[x] = self.find(self.P[x])",
" return self.P[x]",
"",
" def union(self, x, y):",
" x = self.find(x)",
" y = self.find(y)",
" if x == y: return",
" if self.P[x] > self.P[y]: x, y = y, x",
" self.P[x] += self.P[y]",
" self.P[y] = x",
"",
" def size(self, x): return -self.P[self.find(x)]",
"",
" def same(self, x, y): return self.find(x) == self.find(y)",
"",
" def members(self, x):",
" root = self.find(x)",
" return [i for i in range(self.n) if self.find(i) == root]",
"",
" def roots(self): return [i for i, x in enumerate(self.P) if x < 0]",
"",
" def group_count(self): return len(self.roots())",
"",
" def all_group_members(self):",
" from collections import defaultdict",
" G = defaultdict(list)",
" for member in range(self.n): G[self.find(member)].append(member)",
" return G",
"",
" def __str__(self): return '\\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())",
""
],
"description": "union_find"
},
"warshall_floyd": {
"prefix": "_warshall_floyd",
"body": [
"class WarshallFloyd:",
" def __init__(self, N, cost): # (a, b, c) dist[a][b] = c",
" self.dist = [[1 << 30] * N for _ in range(N) ]",
" for i in range(N): self.dist[i][i] = 0",
" for a, b, c in cost:",
" self.dist[a][b] = c ",
" self.dist[b][a] = c",
"",
" self.prev = [[i] * N for i in range(N)]",
" for k in range(N):",
" for i in range(N):",
" for j in range(N):",
" if self.dist[i][j] > self.dist[i][k] + self.dist[k][j]:",
" self.dist[i][j] = self.dist[i][k] + self.dist[k][j]",
" self.prev[i][j] = self.prev[k][j]",
" ",
" def get(self, a, b): return self.dist[a][b]",
"",
" def way(self, start, goal):",
" cur = goal",
" ret = [goal]",
" while cur != start:",
" cur = self.prev[start][cur]",
" ret.append(cur)",
" return ret[::-1]",
""
],
"description": "warshall_floyd"
},
// matrix
"affine": {
"prefix": "_affine",
"body": [
"class Affine:",
" def __init__(self):",
" self.mat = [[1 if i == j else 0 for i in range(3)] for j in range(3)]",
"",
" @staticmethod",
" def get(A, x, y):",
" M = mat_mul(",
" A, ",
" [",
" [x],",
" [y],",
" [1]",
" ]",
" )",
"",
" return (M[0][0], M[1][0])",
"",
" # clock wise",
" def rot90(self):",
" self.mat = mat_mul(",
" [",
" [0, 1, 0],",
" [-1, 0, 0],",
" [0, 0, 1]",
" ],",
" self.mat",
" )",
"",
" # counter clock wise",
" def rot90_rev(self):",
" self.mat = mat_mul(",
" [",
" [0, -1, 0],",
" [1, 0, 0],",
" [0, 0, 1]",
" ],",
" self.mat",
" )",
"",
" # x += t",
" def add_x(self, t):",
" self.mat = mat_mul(",
" [",
" [1, 0, t],",
" [0, 1, 0],",
" [0, 0, 1]",
" ],",
" self.mat",
" )",
" ",
" # y += t",
" def add_y(self, t):",
" self.mat = mat_mul(",
" [",
" [1, 0, 0],",
" [0, 1, t],",
" [0, 0, 1]",
" ],",
" self.mat",
" )",
"",
" # x -> -x",
" def rev_x(self):",
" self.mat = mat_mul(",
" [",
" [-1, 0, 0],",
" [0, 1, 0],",
" [0, 0, 1]",
" ],",
" self.mat",
" )",
"",
" # y -> -y",
" def rev_y(self):",
" self.mat = mat_mul(",
" [",
" [1, 0, 0],",
" [0, -1, 0],",
" [0, 0, 1]",
" ],",
" self.mat",
" )",
""
],
"description": "affine"
},
"fibonacc": {
"prefix": "_fibonacc",
"body": [
"def fibonacci(x):",
" return mat_mul(mat_pow([[1, 1], [1, 0]], x), [[1], [0]])[0][0]",
""
],
"description": "fibonacc"
},
"mat_mul": {
"prefix": "_mat_mul",
"body": [
"def mat_mul(A, B):",
" y, x = len(A), len(A[0])",
" yy, xx = len(B), len(B[0])",
" if not yy == x: ",
" raise Exception('({}, {}) and ({}, {}) cannot be multipled'.format(y, x, yy, xx))",
" mat = [[0] * xx for _ in range(y)]",
" for i in range(y):",
" for j in range(xx):",
" mat[i][j] = sum(A[i][k] * B[k][j] for k in range(x))",
" return mat ",
""
],
"description": "mat_mul"
},
"mat_pow": {
"prefix": "_mat_pow",
"body": [
"def mat_pow(A, n):",
" if not n: ",
" identity_matrix = [[1 if i == j else 0 for i in range(len(A))] for j in range(len(A))]",
" return identity_matrix",
"",
" m = mat_pow(A, n//2)",
" if n % 2:",
" return mat_mul(A, mat_mul(m, m))",
" else:",
" return mat_mul(m, m)",
""
],
"description": "mat_pow"
},
// number
"subset": {
"prefix": "_subset",
"body": [
"def subset(s):",
" t = s ",
" while t:",
" yield t ",
" t = (t - 1) & s ",
""
],
"description": "subset"
},
"base_conversion": {
"prefix": "_base_conversion",
"body": [
"# num(x) -> num(y)",
"def base_conversion(num, x, y):",
" k = int(str(num), base = x)",
" m = []",
" while k:",
" d = k % y ",
" m.append(d)",
" k //= y ",
" return ''.join(map(str, m[::-1]))",
""
],
"description": "base_conversion"
},
"catalan_number": {
"prefix": "_catalan_number",
"body": [
"def catalan_number(N, MOD):",
" F = [1, 1]",
" FI = [1, 1]",
" INV = [0, 1]",
" for i in range(2, 2 * N + 1):",
" F.append((F[-1] * i) % MOD)",
" INV.append((-INV[MOD % i] * (MOD // i)) % MOD)",
" FI.append((FI[-1] * INV[-1]) % MOD)",
" return F[2 * N] * FI[N] ** 2 * INV[N + 1] % MOD",
""
],
"description": "catalan_number"
},
"compress": {
"prefix": "_compress",
"body": [
"class Compress:",
" def __init__(self, A, indexed = 0):",
" self.compress = {}",
" self.original = {}",
" for i, e in enumerate(sorted(set(A))):",
" self.compress[e] = i + indexed",
" self.original[i + indexed] = e ",
"",
" def get_compress(self, A): ",
" if type(A) == list: return [self.compress[e] for e in A]",
" if type(A) == int: return self.compress[A]",
"",
" def get_original(self, A): ",
" if type(A) == list: return [self.original[e] for e in A]",
" if type(A) == int: return self.original[A]",
""
],
"description": "compress"
},
"crt": {
"prefix": "_crt",
"body": [
"# x == b1(mod m1) and x == b2(mod m2) 0 <= r < m1 * m2",
"def crt(b1, m1, b2, m2): ",
" d, p, q = ext_gcd(m1, m2)",
" if b1 % d != b2 % d: return 0, -1",
" m = lcm(m1, m2)",
" t = (b2 - b1) // d * p % (m2 // d)",
" r = (b1 + m1 * t) % m ",
" return r, m ",
"",
"def ext_gcd(a, b):",
" if a == 0: return (b, 0, 1)",
" g, y, x = ext_gcd(b % a, a)",
" return g, x - (b // a) * y, y",
"",
"def gcd(x, y):",
" if x == 0: return y ",
" return gcd(y % x, x)",
"",
"def lcm(a, b):",
" return a // gcd(a,b) * b",
"",
""
],
"description": "crt"
},
"cumsum": {
"prefix": "_cumsum",
"body": [
"class Cumsum:",
" def __init__(self, A):",
" t, self.cum = 0, [0]",
" for a in A: ",
" t += a",
" self.cum.append(t)",
"",
" #[l, r)",
" def get(self, l, r): return self.cum[r] - self.cum[l]",
""
],
"description": "cumsum"
},
"cumsum2d": {
"prefix": "_cumsum2d",
"body": [
"class cumsum2d:",
" def __init__(self, A):",
" H = len(A)",
" W = len(A[0])",
" self.cum = [[0] * (W + 1) for _ in range(H + 1)] ",
"",
" for i in range(H):",
" for j in range(W):",
" self.cum[i + 1][j + 1] += self.cum[i + 1][j] + A[i][j]",
"",
" for j in range(W):",
" for i in range(H):",
" self.cum[i + 1][j + 1] += self.cum[i][j + 1]",
"",
" # i <= y < ii and j <= x < jj",
" def get(self, i, ii, j, jj): return self.cum[ii][jj] - self.cum[i][j]",
""
],
"description": "cumsum2d"
},
"digital_root": {
"prefix": "_digital_root",
"body": [
"def digital_root(x):",
" if x == 9: return 9 ",
" return x % 9",
""
],
"description": "digital_root"
},
"doubling": {
"prefix": "_doubling",
"body": [
"class Doubling:",
" def __init__(self, A):",
" self.logK = 65",
" N = len(A)",
" self.db = [[0] * N for _ in range(self.logK)]",
" for i in range(N): self.db[0][i] = A[i]",
" for k in range(self.logK-1):",
" for i in range(N):",
" self.db[k+1][i] = self.db[k][self.db[k][i]]",
" ",
" # start -> A[start] -> A[A[start]] ... (loop times)",
" def move(self, start, loop):",
" now = start",
" for k in range(self.logK):",
" if loop >> k & 1: now = self.db[k][now]",
" return now",
""
],
"description": "doubling"
},
"extgcd": {
"prefix": "_extgcd",
"body": [
" # ax + by = d return (x, y, d); d = gcd(a, b)",
"def extgcd(a, b):",
" if not b: return (1, 0, a)",
" x, y, d = extgcd(b, a % b)",
" return y, x - a // b * y, d",
""
],
"description": "extgcd"
},
"factorial": {
"prefix": "_factorial",
"body": [
"def factorial(N, MOD):",
" fact = [1]",
" for i in range(1, N + 1): fact.append(fact[-1] * i % MOD)",
" return fact",
""
],
"description": "factorial"
},
"gcd": {
"prefix": "_gcd",
"body": [
"def gcd(x, y):",
" while x: x, y = y % x, x ",
" return y",
""
],
"description": "gcd"
},
"inv_number_and_factorial": {
"prefix": "_inv_number_and_factorial",
"body": [
"def inv_number_and_factorial(N, MOD):",
" inv_number = [0, 1]",
" inv_fact = [1, 1]",
" for i in range(2, N + 1):",
" inv_number.append(-inv_number[MOD % i] * (MOD // i) % MOD)",
" inv_fact.append((inv_fact[-1] * inv_number[-1]) % MOD)",
" return inv_number, inv_fact",
""
],
"description": "inv_number_and_factorial"
},
"inv": {
"prefix": "_inv",
"body": [
"class Inv:",
" def __init__(self, N, A):",
" self.size = N",
" self.tree = [0] * (N + 1)",
" if 0 in A: ",
" for i in range(N): A[i] += 1",
" self.A = A",
"",
" def add(self, i, x):",
" while i <= self.size:",
" self.tree[i] += x",
" i += i & -i",
"",
" def sum(self, i):",
" ret = 0",
" while i > 0:",
" ret += self.tree[i]",
" i -= i & -i",
" return ret",
"",
" def get(self):",
" cnt = 0",
" for i, a in enumerate(self.A):",
" self.add(a, 1)",
" cnt += i + 1 - self.sum(a)",
" return cnt",
""
],
"description": "inv"
},
"lcm": {
"prefix": "_lcm",
"body": [
"def lcm(a, b): return a // gcd(a,b) * b",
""
],
"description": "lcm"
},
"mobius": {
"prefix": "_mobius",
"body": [
"def mobius(N):",
" is_prime = [1] * (N + 1)",
" is_prime[0] = is_prime[1] = 0",
" mobius = [0] * (N + 1)",
" mobius[1] = 1",
" d = [1] * (N + 1)",
" for i in range(2, N + 1):",
" if d[i] > 1:",
" if not i % (d[i] ** 2): mobius[i] = 0",
" else: mobius[i] = - mobius[i // d[i]]",
" if not is_prime[i]: continue",
" mobius[i] = -1",
" for j in range(i ** 2, N + 1, i):",
" is_prime[j] = 0",
" d[j] = i",
" return mobius",
""
],
"description": "mobius"
},
"nCr": {
"prefix": "_nCr",
"body": [
"from operator import mul",
"from functools import reduce",
"",
"def nCr(n, r):",
" r = min(r, n - r)",
" numer = reduce(mul, range(n, n - r, -1), 1)",
" denom = reduce(mul, range(1, r + 1), 1)",
" return numer // denom",
""
],
"description": "nCr"
},
"nCr_inverse": {
"prefix": "_nCr_inverse",
"body": [
"class nCrInverse:",
" def __init__(self, N, MOD):",
" self.N = N ",
" self.MOD = MOD ",
" self.F = [1, 1]",
" self.FI = [1, 1]",
" self.INV = [0, 1]",
" for i in range(2, self.N + 1):",
" self.F.append((self.F[-1] * i) % MOD)",
" self.INV.append((-self.INV[MOD % i] * (MOD // i)) % MOD)",
" self.FI.append((self.FI[-1] * self.INV[-1]) % MOD)",
"",
" def get(self, n, r):",
" if r < 0 or n < r: return 0",
" r = min(r, n - r)",
" return self.F[n] * self.FI[r] * self.FI[n - r] % self.MOD",
""
],
"description": "nCr_inverse"
},
"nPr_inverse": {
"prefix": "_nPr_inverse",
"body": [
"class nPrInverse:",
" def __init__(self, N, MOD):",
" self.N = N ",
" self.MOD = MOD ",
" self.F = [1, 1]",
" self.FI = [1, 1]",
" self.INV = [0, 1]",
" for i in range(2, self.N + 1):",
" self.F.append((self.F[-1] * i) % MOD)",
" self.INV.append((-self.INV[MOD % i] * (MOD // i)) % MOD)",
" self.FI.append((self.FI[-1] * self.INV[-1]) % MOD)",
"",
" def get(self, n, r):",
" if r < 0 or n < r: return 0",
" return self.F[n] * self.FI[n-r] % self.MOD",
""
],
"description": "nPr_inverse"
},
"partial_sum": {
"prefix": "_partial_sum",
"body": [
"def partial_sum_cases(A, K, MOD = 998244353):",
" if K < 0: return 0",
" dp = [0] * (K + 1)",
" dp[0] = 1",
" for a in A:",
" for j in range(K, -1, -1):",
" if j + a <= K:",
" dp[j + a] += dp[j]",
" dp[j + a] %= MOD",
"",
" return dp[K]",
"",
"",
"def partial_sum_judge(A, K):",
" if K < 0: return 0",
" dp = [False] * (K + 1)",
" dp[0] = True ",
" for a in A:",
" for j in range(K, -1, -1):",
" if j + a <= K: ",
" dp[j + a] |= dp[j]",
" ",
" return dp[K]",
""
],
"description": "partial_sum"
},
"pop_cnt": {
"prefix": "_pop_cnt",
"body": [
"def pop_cnt(x):",
" c = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555)",
" c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)",
" c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)",
" c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)",
" c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)",
" c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)",
" return c",
""
],
"description": "pop_cnt"
},
"recurring_decimal": {
"prefix": "_recurring_decimal",
"body": [
"def gcd(x, y):",
" while y: x, y = y, x % y ",
" return x ",
"",
"def is_terminate_decimal(numerator, denominator):",
" div = gcd(numerator, denominator)",
" denominator //= div ",
" while denominator % 2 == 0: denominator //= 2 ",
" while denominator % 5 == 0: denominator //= 5 ",
" return denominator == 1",
"",
"def recurring_decimal(numerator, denominator):",
" # not terminate decimal",
" assert not is_terminate_decimal(numerator, denominator)",
"",
" integer, numerator = divmod(numerator, denominator)",
" decimal = []",
" idx = 0",
" checked = {}",
" quotient, remainder = divmod(numerator * 10, denominator)",
" while (quotient, remainder) not in checked:",
" checked[(quotient, remainder)] = idx ",
" decimal.append(quotient)",
" numerator = remainder",
" idx += 1",
" quotient, remainder = divmod(numerator * 10, denominator)",
"",
" repeat = decimal[checked[(quotient, remainder)]:]",
" ans = str(integer) + '.' + ''.join(map(str, decimal))",
" print(ans)",
" print(f\"Repeat:{repeat}\")"
],
"description": "recurring_decimal"
},
"to_int": {
"prefix": "_to_int",
"body": [
"def to_int(x, base): # also supports negative base",
" if not x: return ''",
" r = (x % abs(base) + abs(base)) % abs(base)",
" x = (x - r) // base",
" return to_int(x, base) + str(r)",
""
],
"description": "to_int"
},
// prime
"coprime_pairs": {
"prefix": "_coprime_pairs",
"body": [
"# gcd(x, y) = 1(l < x, y, <= r)",
"def coprime_pairs(l, r):",
" ret = (r - l) ** 2",
" R = r",
" while R > 1:",
" a, b = l // R, r // R",
" L = max(l // (a + 1), r // (b + 1))",
" ret += (L - R) * coprime_pairs(a, b)",
" R = L",
" return ret",
""
],
"description": "coprime_pairs"
},
"divs": {
"prefix": "_divs",
"body": [
"def divs(N):",
" i, d, dd = 1, [], []",
" while i * i < N:",
" if N % i == 0:",
" d.append(i)",
" dd.append(N // i)",
" i += 1",
" else:",
" if i * i == N and N % i == 0: d.append(i)",
" return d + dd[::-1]",
""
],
"description": "divs"
},
"is_prime": {
"prefix": "_is_prime",
"body": [
"def is_prime(x):",
" if x == 1 or x % 2 == 0: return x == 2",
" f = 3",
" while f * f <= x:",
" if x % f == 0: return False ",
" f += 2",
" return True ",
""
],
"description": "is_prime"
},
"prime_factorize": {
"prefix": "_prime_factorize",
"body": [
"def prime_factorize(N):",
" p = defaultdict(int)",
" while N % 2 == 0:",
" p[2] += 1",
" N //= 2",
" f = 3",
" while f * f <= N:",
" if N % f == 0:",
" p[f] += 1",
" N //= f",
" else: f += 2",
" if N != 1: p[N] += 1",
" return p",
""
],
"description": "prime_factorize"
},
"prime_factors": {
"prefix": "_prime_factors",
"body": [
"# 60 = 2 * 2 * 3 * 5 ",
"# number of prime factors: K[60] = 3",
"# kinds of prime factors: P[60] = 2, 3, 5 ",
"",
"def prime_factors(N):",
" K = [0] * (N + 1)",
" P = [[] for _ in range(N + 1)]",
" for i in range(2, N + 1):",
" if K[i]: continue",
" for j in range(i, N + 1, i): ",
" P[j].append(i)",
" K[j] += 1",
"",
" return K[N] ",
""
],
"description": "prime_factors"
},
"sieve": {
"prefix": "_sieve",
"body": [
"def sieve(N): ",
" P = []",
" check = [1] * (N + 1)",
" check[1] = 0",
" for p in range(2, N + 1):",
" if not check[p]: continue",
" P.append(p)",
" for i in range(p * p, N + 1, p): check[i] = 0",
" ",
" return P ",
""
],
"description": "sieve"
},
"totient": {
"prefix": "_totient",
"body": [
"def totient(n):",
" p = defaultdict(int)",
" while n % 2 == 0:",
" p[2] += 1",
" n //= 2",
" f = 3",
" while f * f <= n:",
" if n % f == 0:",
" p[f] += 1",
" n //= f",
" else: f += 2",
" if n != 1: p[n] += 1",
" ans = 1",
" for k, v in p.items():",
" ans *= k - 1",
" ans *= k ** (v - 1)",
"",
" return ans",
"",
"def totient_sieve(N): ",
" K = [0] * (N + 1)",
" P = [[] for _ in range(N + 1)]",
" for i in range(2, N + 1):",
" if K[i]: continue",
" for j in range(i, N + 1, i): ",
" P[j].append(i)",
" K[j] = 1",
"",
" sieve = []",
" for i, E in enumerate(P):",
" ans = i",
" for p in E:",
" ans //= p",
" ans *= p - 1",
" sieve.append(ans)",
" return sieve",
""
],
"description": "totient"
},
// string
"levenshtein_distance": {
"prefix": "_levenshtein_distance.py",
"body": [
"def levenshtein_distance(A, B): #Edit Distance",
" AL = len(A)",
" BL = len(B)",
" dp = [[10 ** 18] * (BL + 1) for _ in range(AL + 1)]",
" dp[0][0] = 0",
" for i in range(AL + 1):",
" for j in range(BL + 1):",
" if i > 0 and j > 0:",
" dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (A[i - 1] != B[j - 1]))",
" if i > 0:",
" dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)",
" if j > 0:",
" dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)",
"",
" return dp[AL][BL]",
""
],
"description": "levenshtein_distance"
},
"rolling_hash": {
"prefix": "_rolling_hash",
"body": [
"class RollingHash:",
" def __init__(self, string, base = 1237, mod = (1 << 61) - 1):",
" N = len(string)",
" self.base = base",
" self.mod = mod ",
" self.hash = [0] * (N + 1)",
" self.p = [1] * (N + 1)",
" for i, c in enumerate(string):",
" num = ord(c) - ord('a') + 1 ",
" self.hash[i + 1] = (self.hash[i] * self.base + num) % self.mod ",
" self.p[i + 1] = self.p[i] * base % self.mod",
"",
" ",
" def get_hash(self, l, r): #[l, r)",
" return (self.hash[r] - self.hash[l] * self.p[r - l]) % self.mod",
""
],
"description": "rolling_hash"
},
"run_length_encoding": {
"prefix": "_run_length_encoding",
"body": [
"def rle(S):",
" ret = []",
" cnt = 1",
" pre = S[0]",
" for e in S[1:]:",
" if e != pre:",
" ret.append([pre, cnt])",
" cnt = 0",
" cnt += 1",
" pre = e ",
" else:",
" ret.append([pre, cnt])",
" return ret",
""
],
"description": "run_length_encoding"
},
}
競プロをやっていて良かったこと😆
😊 楽しい
→ 頭を使える良い趣味の一つとなりました
📚 プログラミングを学習するきっかけになった
→ 競プロからWeb開発や機械学習にも興味を持つことができました
🗡 就職活動で武器となった
→ 特にコーディングテストで苦戦することはありませんでした
→ 面接でのネタ（強み）になりました
→ 結果、憧れ企業のエンジニア内定をいただくことができました
🙆♂️ 友達が増えた
→ 同じ趣味を持つ友達と話す時間はとても楽しいです
→ Do'erの皆に感謝 🎉