Pythonで競プロをするときに良く使うコードやtips

※ 日々更新中

標準入力を別のファイルにする。

vscodeでデバッグは通るし、そのまま提出もいける。

#python hoge.py abc.txt

import sys
if (len(sys.argv) == 2):
    sys.stdin = open(sys.argv[1])

標準入力を受け取る

# 文字列を受け取る
S = input()

# 数字を受け取る
N = int(input())

# 列をリストで受け取る
A = input().split()

# 列をリストの数字で受け取る
A = list(map(int, input().split()))

# N行をリストで受け取る
A = [input() for i in range(N)]

便利な数学系組み込み関数

max(1, 3) # 3
min(1, 3) # 1
abs(-10)  # 10

mathライブラリ

import math

math.sqrt(9) # 3.0

itertools

※ 順列(重複あり)の適当な名前が

from itertools import product
from itertools import permutations
from itertools import combinations

product(list, repeat=2) # 順列(重複あり)
permutations(list, 2)   # 順列
combinations(list, 2)   # 組み合わせ

collections

# 初期値ありの辞書
from collections import defaultdict
d = defaultdict(lambda: 0)
print(d[1)) # 0

書式フォーマット

# 詰める
print('left   : {:<10}'.format(100))   # "100       "
print('right  : {:0>10}'.format(100))  # "0000000100"

# X進数に変換
print(format(14, 'b')) # 1110
print(format(30, 'x')) # 1e

# 少数の5桁まで表示
"{:.5f}".format(5.234567) # 5.23456

bit全探索

N個の要素を自由に選べるときに使用する。各アイテムは「選ぶ」か「選ばない」の二通なのでbitの0(選ばない)と1(選ぶ)で表現する。ループ数が2^Nで増加するため、要素数が25~30くらいまでが実行速度の観点から限界。

N = 4
l = [1, 2, 3, 4]
for bit in range(2 ** N):
    items = []
    for i in range(0, N):
        if bit >> i & 1:
            items.append(l[i])
    print(items)

繰り返し二乗法、結果の余りなど

# aのb乗
def pow(a, b):
    ans = 1
    while n:
        if b % 2:
            ans *= a
        a *= a
        b >>= 1
    return ans

# aのb乗をmで割った余り
def modpow(a, b, m):
    p, ans = a, 1
    for i in range(30):
        if b & (1 << i):
            ans *= p
            ans %= m
        p *= p
        p %= m
    return ans

デバッグする

python3.7からはbreakpoint()がビルトインとして追加され、これをコード上に置くだけで通過時点での対話を起動できる。主な操作は以下。

# コードの中に以下を追加するとその時点での対話モードに進める。
breakpoint()

# breakpoint()を無効にする。

tips

• 処理は関数で書いておく。

  • 競プロは変数名が適当なことが多いので同じ処理を書くときに変数名ミスが発生することを防止するため。
  • エッジケースが通らなかった場合などで、テストケースを乱数で作成し、非一致のケースを出力できたりする。

• indexは0から管理する

  • 配列などで添え字が1から始まる場合もあるが、統一しておくと楽。