atcoder/python.code-snippets

atcoder-python.code-snippets

{
	// Place your atcoder workspace snippets here. Each snippet is defined under a snippet name and has a scope, prefix, body and 
	// description. Add comma separated ids of the languages where the snippet is applicable in the scope field. If scope 
	// is left empty or omitted, the snippet gets applied to all languages. The prefix is what is 
	// used to trigger the snippet and the body will be expanded and inserted. Possible variables are: 
	// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. 
	// Placeholders with the same ids are connected.
	// Example:
	// "Print to console": {
	// 	"scope": "javascript,typescript",
	// 	"prefix": "log",
	// 	"body": [
	// 		"console.log('$1');",
	// 		"$2"
	// 	],
	// 	"description": "Log output to console"
	// }

	// INPUT
	"input()": {
		"prefix": "inp",
		"body": "input()"
	},
	"input().split()": {
		"prefix": "insp",
		"body": "input().split()"
	},
	"int(input())": {
		"prefix": "intin",
		"body": "int(input())"
	},
	"map(int, input().split())": {
		"prefix": "mapint",
		"body": "map(int, input().split())"
	},
	"map(str, input().split())": {
		"prefix": "mapstr",
		"body": "map(str, input().split())"
	},
	"list(map(int, input().split()))": {
		"prefix": "listint",
		"body": "list(map(int, input().split()))"
	},
	"list(map(str, input().split()))": {
		"prefix": "liststr",
		"body": "list(map(str, input().split()))"
	},
	"map(lambda x:int(x)-1,input().split())": {
		"prefix": "mapintlam",
		"body": "map(lambda x:int(x)-1,input().split())"
	},
	"lambda x:int(x)-1": {
		"prefix": "lam",
		"body": "lambda x:int(x)-1"
	},
	"list(map(lambda x:int(x)-1,input().split()))": {
		"prefix": "listintlam",
		"body": "list(map(lambda x:int(x)-1,input().split()))"
	},

	// OUTPUT
	"print('Yes')": {
		"prefix": "yes",
		"body": "print('Yes')"
	},
	"print('No')": {
		"prefix": "no",
		"body": "print('No')"
	},

	// Standard
	"abc": {
		"prefix": "abc",
		"body": "abc = 'abcdefghijklmnopqrstuvwxyz'"
	},
	"ABC": {
		"prefix": "ABC",
		"body": "ABC = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'"
	},
	"MOD": {
		"prefix": "MOD",
		"body": "MOD = 1000000007"
	},
	"INF": {
		"prefix": "INF",
		"body": "INF = float('inf')"
	},
	"for i in range(start, stop, step)": {
		"prefix": "for",
		"body": "for $1 in range($2)"
	},
	// enumerate
	"for i in enumerate(iterable)": {
		"prefix": "forenum",
		"body": "for $1, $2 in enumerate($3)"
	},
	// zip
	"for i in zip(*iterables)": {
		"prefix": "forzip",
		"body": "for $1 in zip($2)"
	},

	// Library
	"libraries": {
		"prefix": "libs",
		"body": [
			"from bisect import *",
			"from collections import Counter, defaultdict, deque",
			"from heapq import *",
			"from itertools import product, permutations, combinations", 
			"from math import sqrt, floor, ceil",
			"import networkx as nx",
			"from functools import cache",
			"import sys", "sys.setrecursionlimit(10**6)"
		]
	},
	// bisect
	"bisect": {
		"prefix": "howtobisect",
		"body": ["bisect_left(a, x)", "bisect_right(a, x)", "insort_left(a, x)", "insort_right(a, x)"]
	},
	// collections.deque (Queue)
	"deque": {
		"prefix": "howtodeque",
		"body": ["queue=deque([])", "queue.append()", "queue.popleft()"]
	},
	// collections.deque (Stack)
	"stack": {
		"prefix": "howtostack",
		"body": ["stack=deque([])", "stack.append()", "stack.pop()"]
	},
	// heapq
	"heapq" :{
		"prefix": "howtoheap",
		"body": ["heap=[]", "heapq.heapify(heap)", "heapq.heappop(heap)", "heapq.heappush(heap, item)"]
	},
	// itertools.product
	"product" :{
		"prefix": "howtoprod",
		"body": "product(*args, repeat=1)"
	},
	// itertools.permutations
	"product" :{
		"prefix": "howtoperm",
		"body": "permutations(iterable, r)"
	},
	// itertools.combinations
	"product" :{
		"prefix": "howtocomb",
		"body": "combinations(iterable, r)"
	},

	// Handmade
	// GCD
	"GCD": {
		"prefix": "gcd",
		"body": "def gcd(x, y):\n\treturn x if y==0 else gcd(y, x%y)"
	},
	// LCM
	"LCM": {
		"prefix": "lcm",
		"body": "def lcm(x, y):\n\treturn x*y*gcd(x, y)"
	},
	// isPrime
	"isPrime": {
		"prefix": "isprime",
		"body": "def isPrime(x):\n\tif x<2: return False\n\telif x==2: return True\n\tif x%2==0: return False\n\ti=3\n\twhile i*i<=x:\n\t\tif x%i==0: return False\n\t\ti+=2\n\treturn True"
	},
	// digsum
	"digsum": {
		"prefix": "digsum",
		"body": "def digsum(n):\n\tr=0\n\twhile n>0:\n\t\tr+=n%10\n\t\tn//=10\n\treturn r"
	},
	// enum_div
	"enum_div": {
		"prefix": "enum_div",
		"body": "def enum_div(n):\n\tr=[]\n\ti=2\n\twhile i*i<=n:\n\t\tif n%i==0:\n\t\t\tr.append(i)\n\t\t\tif i!=1 and i*i!=n:\n\t\t\t\tr.append(n//i)\n\t\ti+=1\n\treturn r"
	},
	// bfs
	"bfs": {
		"prefix": "bfs",
		"body": "from collections import deque\nQue=deque([])#[(x,y,d)]\ndef bfs(grid):\n\tispassed=[[False for _ in range(len(grid[0]))] for _ in range(len(grid))]\n\tdxdy=[(1,0),(0,1),(-1,0),(0,-1)]\n\t#dxdy=[(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]\n\twhile len(Que)>0:\n\t\tx,y,d=Que.popleft()\n\t\t'''\n\t\t現在地(x,y), 深さd\n\t\t現在地がゴールか・探索範囲かの判定はここで\n\t\t'''\n\t\tfor dx,dy in dxdy:\n\t\t\tnx,ny=x+dx,y+dy\n\t\t\tif nx>=len(grid[0]):continue\n\t\t\tif nx<0: continue\n\t\t\tif ny>=len(grid):continue\n\t\t\tif ny<0: continue\n\t\t\tif ispassed[ny][nx]:continue\n\t\t\tispassed[ny][nx]=True\n\t\t\tQue.append((nx,ny,d+1))"
	},
	// UNION-FIND
	"UnionFind": {
		"prefix": "unionfind",
		"body": "from collections import defaultdict\nclass UnionFind():\n\tdef __init__(self, n):\n\t\tself.n = n\n\t\tself.parents = [-1] * n\n\n\tdef find(self, x):\n\t\tif self.parents[x] < 0:\n\t\t\treturn x\n\t\telse:\n\t\t\tself.parents[x] = self.find(self.parents[x])\n\t\t\treturn self.parents[x]\n\n\tdef union(self, x, y):\n\t\tx = self.find(x)\n\t\ty = self.find(y)\n\n\t\tif x == y:\n\t\t\treturn\n\n\t\tif self.parents[x] > self.parents[y]:\n\t\t\tx, y = y, x\n\n\t\tself.parents[x] += self.parents[y]\n\t\tself.parents[y] = x\n\n\tdef size(self, x):\n\t\treturn -self.parents[self.find(x)]\n\n\tdef same(self, x, y):\n\t\treturn self.find(x) == self.find(y)\n\n\tdef members(self, x):\n\t\troot = self.find(x)\n\t\treturn [i for i in range(self.n) if self.find(i) == root]\n\n\tdef roots(self):\n\t\treturn [i for i, x in enumerate(self.parents) if x < 0]\n\n\tdef group_count(self):\n\t\treturn len(self.roots())\n\n\tdef all_group_members(self):\n\t\tgroup_members = defaultdict(list)\n\t\tfor member in range(self.n):\n\t\t\tgroup_members[self.find(member)].append(member)\n\t\treturn group_members\n\nuf=UnionFind(n)"
	},
	// https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
	"SortedSet": {
		"prefix": "sortedset",
		"body": "import math\nfrom bisect import bisect_left, bisect_right\nfrom typing import Generic, Iterable, Iterator, TypeVar, Optional, List\nT = TypeVar('T')\n\nclass SortedSet(Generic[T]):\n\tBUCKET_RATIO = 50\n\tREBUILD_RATIO = 170\n\n\tdef _build(self, a=None) -> None:\n\t\t'Evenly divide `a` into buckets.'\n\t\tif a is None: a = list(self)\n\t\tsize = self.size = len(a)\n\t\tbucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))\n\t\tself.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]\n\t\n\tdef __init__(self, a: Iterable[T] = []) -> None:\n\t\t'Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)'\n\t\ta = list(a)\n\t\tif not all(a[i] < a[i + 1] for i in range(len(a) - 1)):\n\t\t\ta = sorted(set(a))\n\t\tself._build(a)\n\n\tdef __iter__(self) -> Iterator[T]:\n\t\tfor i in self.a:\n\t\t\tfor j in i: yield j\n\n\tdef __reversed__(self) -> Iterator[T]:\n\t\tfor i in reversed(self.a):\n\t\t\tfor j in reversed(i): yield j\n\t\n\tdef __len__(self) -> int:\n\t\treturn self.size\n\t\n\tdef __repr__(self) -> str:\n\t\treturn 'SortedSet' + str(self.a)\n\t\n\tdef __str__(self) -> str:\n\t\ts = str(list(self))\n\t\treturn '{' + s[1 : len(s) - 1] + '}'\n\n\tdef _find_bucket(self, x: T) -> List[T]:\n\t\t'Find the bucket which should contain x. self must not be empty.'\n\t\tfor a in self.a:\n\t\t\tif x <= a[-1]: return a\n\t\treturn a\n\n\tdef __contains__(self, x: T) -> bool:\n\t\tif self.size == 0: return False\n\t\ta = self._find_bucket(x)\n\t\ti = bisect_left(a, x)\n\t\treturn i != len(a) and a[i] == x\n\n\tdef add(self, x: T) -> bool:\n\t\t'Add an element and return True if added. / O(√N)'\n\t\tif self.size == 0:\n\t\t\tself.a = [[x]]\n\t\t\tself.size = 1\n\t\t\treturn True\n\t\ta = self._find_bucket(x)\n\t\ti = bisect_left(a, x)\n\t\tif i != len(a) and a[i] == x: return False\n\t\ta.insert(i, x)\n\t\tself.size += 1\n\t\tif len(a) > len(self.a) * self.REBUILD_RATIO:\n\t\t\tself._build()\n\t\treturn True\n\n\tdef discard(self, x: T) -> bool:\n\t\t'Remove an element and return True if removed. / O(√N)'\n\t\tif self.size == 0: return False\n\t\ta = self._find_bucket(x)\n\t\ti = bisect_left(a, x)\n\t\tif i == len(a) or a[i] != x: return False\n\t\ta.pop(i)\n\t\tself.size -= 1\n\t\tif len(a) == 0: self._build()\n\t\treturn True\n\t\n\tdef lt(self, x: T) -> Optional[T]:\n\t\t'Find the largest element < x, or None if it does not exist.'\n\t\tfor a in reversed(self.a):\n\t\t\tif a[0] < x:\n\t\t\t\treturn a[bisect_left(a, x) - 1]\n\n\tdef le(self, x: T) -> Optional[T]:\n\t\t'Find the largest element <= x, or None if it does not exist.'\n\t\tfor a in reversed(self.a):\n\t\t\tif a[0] <= x:\n\t\t\t\treturn a[bisect_right(a, x) - 1]\n\n\tdef gt(self, x: T) -> Optional[T]:\n\t\t'Find the smallest element > x, or None if it does not exist.'\n\t\tfor a in self.a:\n\t\t\tif a[-1] > x:\n\t\t\t\treturn a[bisect_right(a, x)]\n\n\tdef ge(self, x: T) -> Optional[T]:\n\t\t'Find the smallest element >= x, or None if it does not exist.'\n\t\tfor a in self.a:\n\t\t\tif a[-1] >= x:\n\t\t\t\treturn a[bisect_left(a, x)]\n\t\n\tdef __getitem__(self, x: int) -> T:\n\t\t'Return the x-th element, or IndexError if it does not exist.'\n\t\tif x < 0: x += self.size\n\t\tif x < 0: raise IndexError\n\t\tfor a in self.a:\n\t\t\tif x < len(a): return a[x]\n\t\t\tx -= len(a)\n\t\traise IndexError\n\t\n\tdef index(self, x: T) -> int:\n\t\t'Count the number of elements < x.'\n\t\tans = 0\n\t\tfor a in self.a:\n\t\t\tif a[-1] >= x:\n\t\t\t\treturn ans + bisect_left(a, x)\n\t\t\tans += len(a)\n\t\treturn ans\n\n\tdef index_right(self, x: T) -> int:\n\t\t'Count the number of elements <= x.'\n\t\tans = 0\n\t\tfor a in self.a:\n\t\t\tif a[-1] > x:\n\t\t\t\treturn ans + bisect_right(a, x)\n\t\t\tans += len(a)\n\t\treturn ans\n\n"
	},
	// https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
	"SortedMultiset": {
		"prefix": "sortedmultiset",
		"body": "import math\nfrom bisect import bisect_left, bisect_right, insort\nfrom typing import Generic, Iterable, Iterator, TypeVar, Optional, List\nT = TypeVar('T')\n\nclass SortedMultiset(Generic[T]):\n\tBUCKET_RATIO = 50\n\tREBUILD_RATIO = 170\n\n\tdef _build(self, a=None) -> None:\n\t\t'Evenly divide `a` into buckets.'\n\t\tif a is None: a = list(self)\n\t\tsize = self.size = len(a)\n\t\tbucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))\n\t\tself.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]\n\t\n\tdef __init__(self, a: Iterable[T] = []) -> None:\n\t\t'Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)'\n\t\ta = list(a)\n\t\tif not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):\n\t\t\ta = sorted(a)\n\t\tself._build(a)\n\n\tdef __iter__(self) -> Iterator[T]:\n\t\tfor i in self.a:\n\t\t\tfor j in i: yield j\n\n\tdef __reversed__(self) -> Iterator[T]:\n\t\tfor i in reversed(self.a):\n\t\t\tfor j in reversed(i): yield j\n\t\n\tdef __len__(self) -> int:\n\t\treturn self.size\n\t\n\tdef __repr__(self) -> str:\n\t\treturn 'SortedMultiset' + str(self.a)\n\t\n\tdef __str__(self) -> str:\n\t\ts = str(list(self))\n\t\treturn '{' + s[1 : len(s) - 1] + '}'\n\n\tdef _find_bucket(self, x: T) -> List[T]:\n\t\t'Find the bucket which should contain x. self must not be empty.'\n\t\tfor a in self.a:\n\t\t\tif x <= a[-1]: return a\n\t\treturn a\n\n\tdef __contains__(self, x: T) -> bool:\n\t\tif self.size == 0: return False\n\t\ta = self._find_bucket(x)\n\t\ti = bisect_left(a, x)\n\t\treturn i != len(a) and a[i] == x\n\n\tdef count(self, x: T) -> int:\n\t\t'Count the number of x.'\n\t\treturn self.index_right(x) - self.index(x)\n\n\tdef add(self, x: T) -> None:\n\t\t'Add an element. / O(√N)'\n\t\tif self.size == 0:\n\t\t\tself.a = [[x]]\n\t\t\tself.size = 1\n\t\t\treturn\n\t\ta = self._find_bucket(x)\n\t\tinsort(a, x)\n\t\tself.size += 1\n\t\tif len(a) > len(self.a) * self.REBUILD_RATIO:\n\t\t\tself._build()\n\n\tdef discard(self, x: T) -> bool:\n\t\t'Remove an element and return True if removed. / O(√N)'\n\t\tif self.size == 0: return False\n\t\ta = self._find_bucket(x)\n\t\ti = bisect_left(a, x)\n\t\tif i == len(a) or a[i] != x: return False\n\t\ta.pop(i)\n\t\tself.size -= 1\n\t\tif len(a) == 0: self._build()\n\t\treturn True\n\n\tdef lt(self, x: T) -> Optional[T]:\n\t\t'Find the largest element < x, or None if it does not exist.'\n\t\tfor a in reversed(self.a):\n\t\t\tif a[0] < x:\n\t\t\t\treturn a[bisect_left(a, x) - 1]\n\n\tdef le(self, x: T) -> Optional[T]:\n\t\t'Find the largest element <= x, or None if it does not exist.'\n\t\tfor a in reversed(self.a):\n\t\t\tif a[0] <= x:\n\t\t\t\treturn a[bisect_right(a, x) - 1]\n\n\tdef gt(self, x: T) -> Optional[T]:\n\t\t'Find the smallest element > x, or None if it does not exist.'\n\t\tfor a in self.a:\n\t\t\tif a[-1] > x:\n\t\t\t\treturn a[bisect_right(a, x)]\n\n\tdef ge(self, x: T) -> Optional[T]:\n\t\t'Find the smallest element >= x, or None if it does not exist.'\n\t\tfor a in self.a:\n\t\t\tif a[-1] >= x:\n\t\t\t\treturn a[bisect_left(a, x)]\n\t\n\tdef __getitem__(self, x: int) -> T:\n\t\t'Return the x-th element, or IndexError if it does not exist.'\n\t\tif x < 0: x += self.size\n\t\tif x < 0: raise IndexError\n\t\tfor a in self.a:\n\t\t\tif x < len(a): return a[x]\n\t\t\tx -= len(a)\n\t\traise IndexError\n\n\tdef index(self, x: T) -> int:\n\t\t'Count the number of elements < x.'\n\t\tans = 0\n\t\tfor a in self.a:\n\t\t\tif a[-1] >= x:\n\t\t\t\treturn ans + bisect_left(a, x)\n\t\t\tans += len(a)\n\t\treturn ans\n\n\tdef index_right(self, x: T) -> int:\n\t\t'Count the number of elements <= x.'\n\t\tans = 0\n\t\tfor a in self.a:\n\t\t\tif a[-1] > x:\n\t\t\t\treturn ans + bisect_right(a, x)\n\t\t\tans += len(a)\n\t\treturn ans\n"
	},
	"Dijkstra": {
		"prefix": "dijkstra",
		"body": "import heapq\ndef dijkstra(graph, start, end):\n\tcost = {node: float('inf') for node in range(len(graph))}\n\tcost[start] = 0\n\tqueue = [(0, start)]\n\twhile queue:\n\t\tcurr_cost, curr_node = heapq.heappop(queue)\n\t\tif curr_node==end:\n\t\t\treturn cost[end]\n\t\tif cost[curr_node]<curr_cost:\n\t\t\tcontinue\n\t\tfor next_node, d_cost in graph[curr_node]:\n\t\t\tnext_cost = curr_cost+d_cost\n\t\t\tif next_cost<cost[next_node]:\n\t\t\t\tcost[next_node] = next_cost\n\t\t\t\theapq.heappush(queue, (next_cost, next_node))\n\treturn None\n\nGraph = [[] for _ in range(N)] # [[(next_node, cost)]]"
	},
	// 
	"SegmentTree": {
		"prefix": "segtree",
		"body": ["# セグメント木\nclass SegTree:\n\t'''\n\tinit(init_val, ide_ele): 配列init_valで初期化 O(N)\n\tupdate(k, x): k番目の値をxに更新 O(logN)\n\tquery(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)\n\t'''\n\tdef __init__(self, init_val, segfunc, ide_ele):\n\t\t'''\n\t\tinit_val: 配列の初期値\n\t\tsegfunc: 区間にしたい操作\n\t\tide_ele: 単位元\n\t\tn: 要素数\n\t\tnum: n以上の最小の2のべき乗\n\t\ttree: セグメント木(1-index)\n\t\t'''\n\t\tn = len(init_val)\n\t\tself.segfunc = segfunc\n\t\tself.ide_ele = ide_ele\n\t\tself.num = 1 << (n - 1).bit_length()\n\t\tself.tree = [ide_ele] * 2 * self.num\n\t\t# 配列の値を葉にセット\n\t\tfor i in range(n):\n\t\t\tself.tree[self.num + i] = init_val[i]\n\t\t# 構築していく\n\t\tfor i in range(self.num - 1, 0, -1):\n\t\t\tself.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])\n\n\tdef update(self, k, x):\n\t\t'''\n\t\tk番目の値をxに更新\n\t\tk: index(0-index)\n\t\tx: update value\n\t\t'''\n\t\tk += self.num\n\t\tself.tree[k] = x\n\t\twhile k > 1:\n\t\t\tself.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])\n\t\t\tk >>= 1\n\n\tdef query(self, l, r):\n\t\t'''\n\t\t[l, r)のsegfuncしたものを得る\n\t\tl: index(0-index)\n\t\tr: index(0-index)\n\t\t'''\n\t\tres = self.ide_ele\n\n\t\tl += self.num\n\t\tr += self.num\n\t\twhile l < r:\n\t\t\tif l & 1:\n\t\t\t\tres = self.segfunc(res, self.tree[l])\n\t\t\t\tl += 1\n\t\t\tif r & 1:\n\t\t\t\tres = self.segfunc(res, self.tree[r - 1])\n\t\t\tl >>= 1\n\t\t\tr >>= 1\n\t\treturn res\n# 最小:min(x,y) 最大:max(x,y) 区間和:x+y 区間積:x*y 最大公約数 math.gcd(x,y)\ndef segfunc(x, y):\n\t# return \nINF=float('inf')\n# 最小:INF 最大:-INF 区間和:0 区間積:1 最大公約数 0\nide_ele = \n"]
	},
}