競プロでよく使うけど空で書けないフレーズ

はじめに

よく使うけどうろ覚えなものをまとめました．
よく使う関数版も併せてどうぞ（未完成ですが，，）

順列・組合せ・重複列挙

リストからいくつか選んだ順列or組合せor重複組合せを列挙する．

from itertools import permutations, combinations, product
L = [1,2,3,4]; k = 2
for p in permutations(L,k):
    print(p,end=' ')
#(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3) 
for c in combinations(L,k):
    print(c, end=' ')
#(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
N = 3
for pro in product((0,1), repeat=N):
    print(pro, end=' ')
# (0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1) 

dict

# 初期化
D = dict()
D = {}

# 存在しないキー参照でエラーになる対策
D[k] # Error
D.get(k) # None
D.get(k,0) # 0

# 配列の逆引き辞書を作る
A = [3,1,2]
D = {a:i for i,a in enemurate(A)} # {3: 0, 1: 1, 2: 2}

Counter

配列の何の要素が何個あるかのリストを作る．
3個以上あるkeylistが欲しいときは
L = [k for k,v in c.items() if v>2]
とかできてとても便利

L = [1,1,0,0,2,2,2]

import collections
c = collections.Counter(L)

print(c) # Counter({2: 3, 1: 2, 0: 2})
print(c.keys()) # dict_keys([1, 0, 2])
print(c.values()) # dict_values([2, 2, 3])
print(c.items()) # dict_items([(1, 2), (0, 2), (2, 3)])
# valueが大きい順にソート
print(c.most_common()) # [(2, 3), (1, 2), (0, 2)] 

# このように使える
for k,v in c.items():
    print(k,v)

defaultdict

valuesの型を指定する．
存在しないキーを参照してもデフォルトの値を返す．
デフォルト値はint: 0，str: 空文字列，set: ()，list: []

from collections import defaultdict
D = defaultdict(int)
D = defaultdict(str)
D = defaultdict(set)
D = defaultdict(list)
D = defaultdict(lambda: -1) # デフォルトで-1を返す
# 二次元もとれる
D = defaultdict(lambda: defaultdict(int))
d['key']['a'] += 3

文字列の結合

int型ではエラーがでるので注意
文字列の結合にはO(N)かかるので最後にまとめて結合するのがよい

L = [1,2,3]
L = [str(l) for l in L]
s = ''.join(L)
print(s) # 123

2個目の要素だけでsort

L = [[1,2], [2,1]]
L.sort(key=lambda x:x[1])
print(L) # [[2,1], [1,2]]

enumerate

indexを使えるようになる
めっちゃ使う

# 0から始まる
L = [4,5,6]
for i, name in enumerate(L):
    print(i, name)
# [0, 4], [1, 5], [2, 6]

# 1から始まる
for i, name in enumerate(L, 1):
    print(i, name)
# [1, 4], [2, 5], [3, 6]

累積和

accmulateを通した後はlistをつける点に注意
0から始まるのが欲しかったら
B = [0] + BでOK

from itertools import accumulate
A=[1,4,3,4,6,5]

# 前から
B = list(accumulate(A))
print(B) #[1, 5, 8, 12, 18, 23]

# 後ろから
B = list(accumulate(A[::-1]))[::-1]
print(B) #[23, 22, 18, 15, 11, 5]

deepcopy

D,Eのやり方もあるよ

from copy import deepcopy
A = [1,2,3]
B = A
C = deepcopy(A)
D = [a for a in A]
E = A[:]

A[0] = 100
print(B,C,D,E) # [100, 2, 3] [1, 2, 3] [1, 2, 3] [1, 2, 3]

10進数 ->2,8,16進数

i = 255

int(bin(i)[2:]) # 11111111
int(oct(i)[2:]) # 377
hex(i)[2:] # ff

int(format(i, 'b'))# 11111111
int(format(i, 'o'))# 377
format(i, 'x') # ff

0埋め

8桁右詰めで右埋め

print(format(i, '08b')) # 11111111
print(format(i, '08o')) # 00000377
print(format(i, '08x')) # 000000ff

n進数 -> 10進数

n<=36までしか対応していないらしい
https://note.nkmk.me/python-bin-oct-hex-int-format/

print(int('10'))
print(int('10', 2))
print(int('10', 8))
print(int('10', 16))

n進数<->10進数

これなら任意に変換できる
https://qiita.com/ether2420/items/061c19a000c52adf7f3e

# n進数->10進数
def base_10(num_n,n):
    num_10 = 0
    for s in str(num_n):
        num_10 *= n
        num_10 += int(s)
    return num_10

# 10進数->n進数
def base_n(num_10,n):
    str_n = ''
    while num_10:
        if num_10%n>=10:
            return -1
        str_n += str(num_10%n)
        num_10 //= n
    return int(str_n[::-1])

上限

【AtCoder】Pythonで競プロをするときの注意点まとめ【競技プログラミング】

再帰上限

dfsでは深さの制限を解除しないとエラーがでる
デフォルトは1000

import sys
sys.setrecursionlimit(10 ** 8)

4300桁制限

pythonのintは桁数を気にしなくてもよいと思っていたけど，
実は4300桁の制限があるらしい．
引数に0を指定すると制限を解除できる．

import sys
sys.set_int_max_str_digits(0)

入力のおまじない

import sys
input = sys.stdin.readline

deque

前と後ろから要素を出し入れできる．
ランダムアクセスがO(N)
O(1)に改良したお話がこちら

from collections import deque
q = deque()

heapq

log(N)で要素を出し入れできる
push,popのとき値を-1倍すると最大値を扱える

from heapq import heapify,heappush,heappop
a = [1, 6, 8, 0, -1]
heapify(a)  # リストを優先度付きキューへ
print(a)
# 出力: [-1, 0, 8, 1, 6] (優先度付きキューとなった a)

print(heappop(a))  # 最小値の取り出し
# 出力: -1 (a の最小値)
print(a)
# 出力: [0, 1, 8, 6] (最小値を取り出した後の a)

heappush(a, -2)  # 要素の挿入
print(a)
# 出力: [-2, 0, 1, 8, 6]  (-2 を挿入後の a)

Bisect

ソート済みのリストに新たな要素の挿入場所を返す．
値が等しいときは_leftと_rightで返り値を調整できる．
「探索したい数値未満のうち最大の数値を探索」などをしたい場合

a = [2, 3, 5, 7, 11, 13, 17, 19]

import bisect
print(bisect.bisect_left(a, 10)) # 4
print(bisect.bisect_right(a, 10)) # 4
print(bisect.bisect(a, 10)) # 4

print(bisect.bisect_left(a, 11)) # 4
print(bisect.bisect_right(a, 11)) # 5
print(bisect.bisect(a, 11)) # 5

Decimal

小数の精度を上げる
精度が高い平方根，分数への変換に使う
Decimal型変換するときはstrを経由する．
※ PyPyよりCPythonの方が速い(参考)

from decimal import Decimal, getcontext
getcontext().prec = 1000

a = 2.5
a = Decimal(str(a))
c = (a).sqrt() # print(c) #1000桁のroot2.5

b = 0.1
b = Decimal(b) # 0.1000000000000000055511151231257827021181583404541015625
print(b) # float型だとうまくできない

c = 3.14
Decimal(str(c)).as_integer_ratio() #(-157, 50)

メモ化再帰

同じ引数を用いる場合キャッシュから返り値を返すので計算が早くなる．フィボナッチ数列とかに有効

from functools import lru_cache
@lru_cache(maxsize = 10**8)
def f(x):
    pass

zip

zip()の使い方
複数の配列を頭から同時に参照できる．
これを使うと行列の転置が楽になる．
引数の長さが異なる場合短い長さに調整される．

L = [[1,2,3],[4,5,6]]
list(zip(*L)) # [(1, 4), (2, 5), (3, 6)]
list(map(list,zip(*L))) # [[1, 4], [2, 5], [3, 6]]

A = [1,2,3]
B = [4,5,6]
for a,b in zip(A,B):
    print(a,b)
    # 1 4
    # 2 5
    # 3 6

print(list(map(str,L))) # ['1','2','3']
[str(l) for l in L] # ['1','2','3']

二重ループからbreak

二重ループ内のifを通ってbreakすると
外側ループのelse:continueを通らずにbreakする

for i in range(10):
    for j in range(10):
        # code
        if i*j>80:
            # ループ終了時の処理
            break
    else:continue
    break
print(i,j) # 9 9

if文中のand, or

andは前の命題が偽ならそれ以降は見ない．
orは前の命題が真ならそれ以降は見ない．
グリッド問題でifの回数を減らせる．

A = list('..#'); W = 3

i = 2
if 0<=i<W and A[i]=='#':
    print(True)
else:print(False)

i = 4
if 0<=i<W and A[i]=='#':
    print(True)
else:print(False)

# True
# False

B = []
if not B or B[1]==0:
    print(True)
# True

print

一つ目はスニペットに登録しています．
二つ目はデバッグに重宝します．

# 条件分岐を含める
miss = True
print('Yes' if not miss else 'No') # No

# f文字列
a = -1
print(f"私は{a}歳")

文字列の判定

Pythonで大文字・小文字を操作する文字列メソッド一覧
朝飯前に学べる！便利なPythonのヒント100選【後編】
すべてＯＯか判定する．

# すべてアルファベットまたは数字ならTrue
s = '1a2b3c'
s.isalnum() # True
s = 'happy&happy'
s.isalnum() # False

# 文字列が数値ならTrue
s = '2024'
s.isdigit() # True
s = '00'
s.isdigit() # True

# すべてアルファベットならTrue
s = 'abc'
s.isalpha() # True

# すべて大文字ならTrue
s = 'ATCODER'
s.isupper() # True

# すべて小文字ならTrue
t = 'atocder'
t.islower() # True

ss = 'ATCODER1234!' # 数字や記号は無視される
ss.isupper() # True

すべての文字を大文字，小文字に変換する

s = 'ATCODER'
s = s.lower() # atcoder
t = 'atocder'
t = t.upper() # ATCODER

# 反転もできる
u = 'Atcoder'
u = u.swapcase() # aTCODER

リストの要素がbool値のとき

［解決！Python］all／any関数を使って、リストなどの要素が全て真か／偽か、真な要素があるか／偽な要素があるかを調べるには

# 要素がすべて真ならTrue
seen = [True]*3
if all(seen):
    print(-1) # -1
    
# 要素に真が存在すればTrue
seen = [True, False]
if any(seen):
    print(-2) # -2

# 要素がすべて偽ならTrue
seen = [False]*3
if not any(seen):
    print(-3) # -3
    
# 要素に偽が存在すればTrue
seen = [True, False]
if not all(seen):
    print(-4) # -4

四捨五入

参考1
参考2

from decimal import Decimal,ROUND_HALF_UP
pi = 3.141592653589793

a = Decimal(str(pi)).quantize(Decimal('1'),rounding = ROUND_HALF_UP) 
b = Decimal(str(pi)).quantize(Decimal('1.0'),rounding = ROUND_HALF_UP)
c = Decimal(str(pi)).quantize(Decimal('1.00'),rounding = ROUND_HALF_UP)
d = Decimal(str(pi)).quantize(Decimal('1.000'),rounding = ROUND_HALF_UP)
print(a,b,c,d) # 3 3.1 3.14 3.142

逆元

「～の確率を998244353で割ったあまりを求めよ．」

mod = 998244353
p = pow(3,-1,mod) # 1/3 の逆元
print(p) # 332748118