gteu/atcoder

cheatsheet

Closed this issue · 0 comments

gteu commented

Coding Technique (Python)

  • 出力時
a = [1,2,3]
print(*a) # リストをスペース区切りで出力
print(*a, sep="\n") # リストを改行区切りで出力
  • 再帰の深さで RE を吐くことがある。以下のように上限を設定可能。ただし、例えばDFSの場合は再帰が深すぎると遅くなるのでNが大きい場合はスタックで書いた方が良い。
import sys
sys.setrecursionlimit(200001)
  • queueやstackを使うなら collenctions.deque。スタックは普通のリストでもOK。
q = deque([])
q.append(10) # 追加
q.popleft() # 取り出し(キュー)
q.pop() # 取り出し(スタック)

  • 優先度付きqueueを使う時はheapqを使う

    • 最小値を取り出す時
    heapq.heapify(a) # リストを優先度付きキューに
heapq.heappush(a, 10) # 追加
heapq.heappop(a) # 取り出し
    • 最大値を取り出す時、heapq._heappush_maxが実装されていないから配列に -1 をかけることで対処
    a = map(lambda x: int(x)*(-1), a) 
# あとは同じ

  • 要素数のカウントなら collections.Counter が便利

>>> a = [1,1,2,3,1,1,0]
>>> Counter(a)
Counter({1: 4, 2: 1, 3: 1, 0: 1})
  • 文字列の逆引きがしたい時。つまり、文字→indexが知りたい時
>>> from collections import defaultdict
>>> index = defaultdict(list)
>>> S = "socks"
>>> for i,s in enumerate(S):
...     index[s].append(i)
>>> index
defaultdict(<class 'list'>, {'s': [0, 4], 'o': [1], 'c': [2], 'k': [3]})
  • itertoolsまとめ
permutations(iterable, r=None) # 順列(len()を取れば階乗が求まる)
product(iterable, repeat) # 重複順列
combinations(iterable, r) # 組み合わせ
combinations_with_replacement(iterable, r) # 重複組み合わせ
  • product()を使ってp進全探索する例
for idxs in product(range(p), repeat=N):
    for i, j in enumerate(idxs):
        # ...
  • 組み込み関数 pow() は繰り返し二乗法で実装されているから O(logN) で計算可能。
pow(base, exp[, mod])

  • 文字列連結は "".join(seq) を使う

  • 最大公約数はmath.gcd。3個以上の値に適用する際は以下のように関数を定義。

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  • 最小公倍数はmath.gcdを用いて自分で定義。
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)
  • 文字→ascii: ord() ascii→文字: chr()
# 数字の2を文字のcに変えたいとき(つまり0-indexed)
chr(2 + ord("a"))
  • 10進数→p進数変換は、10進数をnとすると、「nをpで割った余りを求め、nをn//pに置換」を繰り返すのが自分的には考えやすい。
n = 123
ans = []
while(n>=1):
    ans.append(n%p)
    n //= p
# ansを逆順にしたものが、p進数の数。もし11進数以上の場合は上のchrやordを使って変換。
  • 度→ラジアン: math.radians() ラジアン→度: math.degrees()
  • 二分探索で、最初から配列が与えられるような場合にはbisectを使うと良い。
# 例えば、条件が"以上"か"より大きい"かでbisect_leftからbisect_rightが変わる。
# 5以上の値の数を求めるとき
ans = len(a) - bisect_left(a, 5)
# 5より大きい値の数を求めるとき
ans = len(a) - bisect_right(a, 5)

Mathematical Knowledge

  • Fermat の小定理。p を素数、a を p の倍数でない任意の整数としたとき、
    • ap-1 ≡ 1 (mod p)
  • 逆元の求め方
# 1/a (mod p)
a_inv = pow(a,p-2,p)
  • nC0 + …. + nCn = 2n