Why Choose Python for Algorithm Problems#
Undoubtedly, Python has the most concise syntax among mainstream programming languages. Coupled with its rich built-in functions, proficiency in Python can significantly reduce code volume and development time when solving algorithm problems.
Students targeting ICPC/CCPC competitions often choose C++ for performance reasons. However, programming problems encountered in ordinary competitions or interviews do not typically constrain language runtime— as long as the algorithm’s time complexity meets requirements, it will pass. Therefore, once you become accustomed to using Python for algorithm problems, you can improve efficiency and appreciate Python’s elegance.
Common Techniques#
Counter#
c = Counter(list)
for k, v in c.items():
print(k, v)
for k in c.keys():
print(k, c[k])
for v in c.values():
print(v)
for i in c.elements():
print(i)
dict = defaultdict(list) # default to empty list
dict = defaultdict(int) # default to 0
for k, v in dict:
print(k, v)Comprehensions#
# List comprehension
newnames = [name.upper() for name in names if len(name) > 3]
multiples = [i for i in range(30) if i % 3 == 0]
# Dictionary comprehension
newdict = {key: len(key) for key in listdemo}
dic = {x: x**2 for x in (2, 4, 6)}
# Set comprehension
newset = {i**2 for i in (1, 2, 3)}
a = {x for x in 'abracadabra' if x not in 'abc'}Custom Sorting#
data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
data.sort(key=lambda r: r[1])
# Custom sort function
def custom_sort_key(item):
# Generate sort key based on some property of item
return item['priority'] # Assume we sort by priority
# Example data
items = [
{'name': 'A', 'priority': 2},
{'name': 'B', 'priority': 1},
{'name': 'C', 'priority': 3},
]
# Use sorted() for sorting
sorted_items = sorted(items, key=custom_sort_key)
print(sorted_items) # Output sorted list
# Use list.sort() for in-place sorting
items.sort(key=custom_sort_key)
print(items) # Output in-place sorted listMemoization#
from functools import cache
# Use @cache decorator before function to enable memoizationBinary Search Functions#
import bisect
my_list = [1, 3, 5, 5, 7, 9]
# Use bisect_left to find insertion position (leftmost)
left_index = bisect.bisect_left(my_list, 5)
print("Insertion position (leftmost):", left_index)
# Use bisect_right to find insertion position (rightmost)
right_index = bisect.bisect_right(my_list, 5)
print("Insertion position (rightmost):", right_index)
# Output:
# Insertion position (leftmost): 2
# Insertion position (rightmost): 4
# Detailed usage:
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
Finds the first index in [lo, hi) of list a where element >= x
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
Finds the first index in [lo, hi) of list a where element > x
# Custom comparison rule
my_list = [1, 3, 5, 7, 9]
index = bisect.bisect_left(my_list, 5, key=lambda x: x * x)
# Application example: Grade classification
def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
i = bisect.bisect(breakpoints, score)
return grades[i]
[grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']General Template#
This template is for ICPC/CCPC competitions. If you have performance requirements for Python code, consider using the encapsulated IO module in the template.
import sys, os, math
from math import gcd, sqrt
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations, product
from heapq import nsmallest, nlargest, heapify, heappop, heappush
BUFSIZE = 8192
def solve():
n = 1
def main():
tt = 1
tt = II()
for _ in range(tt):
solve()
def qmi(a, b, p):
res = 1 % p
while b:
if b & 1:
res = (res * a) % p
a = a * a % p
b >>= 1
return res
def comb(n, r):
return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0
def I():
return input()
def II():
return int(input())
def MII():
return map(int, input().split())
def LMII():
return list(map(int, input().split()))
def YES(t = 1): print("YES" if t else "NO")
def NO(t = 1): YES(t ^ 1)
def Yes(t = 1): print("Yes" if t else "No")
def No(t = 1): Yes(t ^ 1)
def yes(t = 1): print("yes" if t else "no")
def no(t = 1): yes(t ^ 1)
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin = IOWrapper(sys.stdin)
input = lambda: sys.stdin.readline().rstrip()
if __name__ == "__main__":
main()