gteu / atcoder Goto Github PK

• priority_queueでダイクストラ実装
  参考) https://tjkendev.github.io/procon-library/python/graph/dijkstra.html
• ベルマンフォード実装
• DPコンテスト
• クラスカル法実装
  参考) https://kamojirobrothers.hatenablog.com/entry/2018/11/02/144638
• ダブリング(ABC167D, 他は？)

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 の倍数でない任意の整数としたとき、
  • a^p-1 ≡ 1 (mod p)
• 逆元の求め方

# 1/a (mod p)
a_inv = pow(a,p-2,p)

• _nC₀ + …. + _nC_n = 2ⁿ

雑多なメモ

• Binary Indexed Treeは「指定した要素に値を加える」「指定した部分列の和を求める」をそれぞれO(logN)で可能。単に部分列の和を知りたい場合は普通に累積和でOK。
• 累積和は、前処理がO(N)、各クエリがO(1)。クエリの数が多いと結局計算量がかさむ。
• 尺取り法は条件を満たすような部分列をすべて求めることが可能。
• 「小さい順に K番目の値を求めよ」は「x以下がK個以上ある最小のxを求めよ」と同じ。つまり二分探索で調べることができる(ABC155D)
• 「xxという条件を満たすn以下の個数を求めよ」みたいな状況の場合、nが大きくなければ全て調べてしまうと楽かもしれない(ABC152D)
• ワーシャルフロイド、ダイクストラはscipy実装が使える。自分で実装する場合はpypyで出した方がいいかも。
• ワーシャルフロイドは「自分から(他の頂点を経由した)自分への距離」も計算する。これが必要じゃない場合もあるので注意(ABC151D)
• 尺取法(ABC130D)
• ある数列や行列において、自分の左右、または四方について計算するときは、各方向についてO(N)で計算した値を持っておくと効率がいい場合あり。(ABC125C, ABC129D)
• 重複を考えなくてはいけない場合、数え方が複数ある時は一意に数え方を決めてしまえばいい場合がある。Sを部分列に持つ文字列を考える時がその例。https://qiita.com/drken/items/a207e5ae3ea2cf17f4bd (ABC171F)
• 部分列DPでは、i番目以降で最初に文字("a"など)が使われるindexを持っておくと楽に部分列を調べられることがある。(上の記事や、ABC138E)
• 桁DP。dp[i][smaller][j]とすると、初期値dp[0][0][0]=1(それ以外0)に設定できる。i = 0は、本来の桁数より1つ上に0があるイメージを持つ。またDP全般に言えることだが遷移図をちゃんと書く。(ABC154E)

template

• 21 = 2^4 + 2^2 + 2^0 みたいな計算 → pow_sum