#CP テンプレ集 Python

お久しぶりです、モチベがなかったりモチベがなかったりAP受けてたりモチベがなかったりで更新してませんでした。

pythonで競技プログラミングに使えるテンプレ集みたいなのを作っておこうと思い立ったので作ることにします。

二分探索

def binary_search(key, a, ng, ok):
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if midが条件を満たしているかどうか: ok = mid
        else ng = mid
    return ok

使用例

atcoder.jp

しゃくとり法

for left in range(N):
    while right < N and 右に進める条件:
        # なんらかの処理
        right += 1
    # 毎回の処理
    if left == right:
        # leftがrightに追いついたときの処理(大抵はright += 1 ?)
    else:
        # 追いついてない時の処理(left += 1に伴う処理)

半開区間で[left,right)としています。だからright-leftとすればその区間の要素数になります。条件を満たすl,rの個数を調べたいときはright-leftで計算しましょう。

使用例

atcoder.jp

深さ優先探索

def dfs(v):
    Stack = []
    visit[v] = True
    while Stack:
        v = Stack.pop()
        # vを処理する
        for i in 隣接リスト[v]:
            if not visit[i]:
                visit[i] = True
                Stack.append(i)

使用例

atcoder.jp