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

# はじめに
よく使うけどうろ覚えなものをまとめました．
よく使う[関数版](https://qiita.com/do_an/items/c220656ae2276db94e3c)も併せてどうぞ（未完成ですが，，）

# 順列・組合せ・重複列挙
リストからいくつか選んだ順列or組合せor重複組合せを列挙する．
```python
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
```python
# 初期化
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] `
とかできてとても便利
```python
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: []`
```python
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)かかるので最後にまとめて結合するのがよい
```python
L = [1,2,3]
L = [str(l) for l in L]
s = ''.join(L)
print(s) # 123
```
# 2個目の要素だけでsort
```python
L = [[1,2], [2,1]]
L.sort(key=lambda x:x[1])
print(L) # [[2,1], [1,2]]
```

# enumerate
indexを使えるようになる
めっちゃ使う
```python
# 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

```python
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のやり方もあるよ
```python
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進数
```python
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桁右詰めで右埋め
```python
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/
```python
print(int('10'))
print(int('10', 2))
print(int('10', 8))
print(int('10', 16))
```
# n進数<->10進数
これなら任意に変換できる
https://qiita.com/ether2420/items/061c19a000c52adf7f3e
```python
# 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
```
```python
# 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で競プロをするときの注意点まとめ【競技プログラミング】](https://qiita.com/kemuniku/items/1f1537e1df2ac8180d9b)
### 再帰上限
dfsでは深さの制限を解除しないとエラーがでる
デフォルトは`1000`
```python
import sys
sys.setrecursionlimit(10 ** 8)
```
### 4300桁制限
pythonのintは桁数を気にしなくてもよいと思っていたけど，
実は4300桁の制限があるらしい．
引数に`0`を指定すると制限を解除できる．
```python
import sys
sys.set_int_max_str_digits(0)
```
# 入力のおまじない

```python
import sys
input = sys.stdin.readline
```

# deque
前と後ろから要素を出し入れできる．
ランダムアクセスがO(N)
O(1)に改良したお話が[こちら](https://prd-xxx.hateblo.jp/entry/2020/02/07/114818)
```python
from collections import deque
q = deque()
```
https://docs.python.org/ja/3/library/collections.html#collections.deque

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

```python
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)
```
https://qiita.com/ell/items/fe52a9eb9499b7060ed6

# Bisect
ソート済みのリストに新たな要素の挿入場所を返す．
値が等しいときは`_left`と`_right`で返り値を調整できる．
[「探索したい数値未満のうち最大の数値を探索」などをしたい場合](https://qiita.com/seigot/items/5091499d75a11cc77e41)
```python
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の方が速い[(参考)](https://qiita.com/kemuniku/items/1f1537e1df2ac8180d9b)

```python
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)

```
# メモ化再帰
同じ引数を用いる場合キャッシュから返り値を返すので計算が早くなる．フィボナッチ数列とかに有効
```python
from functools import lru_cache
@lru_cache(maxsize = 10**8)
def f(x):
    pass
```
https://qiita.com/alchemist/items/c75174c41b0bcd31ecc6

# zip
[zip()の使い方](https://hibiki-press.tech/python/zip-iterable/3834)
複数の配列を頭から同時に参照できる．
これを使うと行列の転置が楽になる．
引数の長さが異なる場合短い長さに調整される．

```python
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する
```python
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の回数を減らせる．
```python
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
一つ目はスニペットに登録しています．
二つ目はデバッグに重宝します．
```python
# 条件分岐を含める
miss = True
print('Yes' if not miss else 'No') # No

# f文字列
a = -1
print(f"私は{a}歳")
```
# 文字列の判定
[Pythonで大文字・小文字を操作する文字列メソッド一覧](https://note.nkmk.me/python-capitalize-lower-upper-title/#_2)
[朝飯前に学べる！便利なPythonのヒント100選【後編】](https://qiita.com/baby-degu/items/532bea7be058c35f61a8)
すべてＯＯか判定する．
```python
# すべてアルファベットまたは数字なら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
```

すべての文字を大文字，小文字に変換する
```python
s = 'ATCODER'
s = s.lower() # atcoder
t = 'atocder'
t = t.upper() # ATCODER

# 反転もできる
u = 'Atcoder'
u = u.swapcase() # aTCODER
```
# リストの要素がbool値のとき
[［解決！Python］all／any関数を使って、リストなどの要素が全て真か／偽か、真な要素があるか／偽な要素があるかを調べるには](https://atmarkit.itmedia.co.jp/ait/articles/2305/30/news027.html)
```python

# 要素がすべて真なら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](https://qiita.com/kemuniku/items/1f1537e1df2ac8180d9b#round%E3%81%AF%E5%9B%9B%E6%8D%A8%E4%BA%94%E5%85%A5%E3%81%98%E3%82%83%E3%81%AA%E3%81%84)
[参考2](https://note.nkmk.me/python-round-decimal-quantize/)
```python
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で割ったあまりを求めよ．」
```python
mod = 998244353
p = pow(3,-1,mod) # 1/3 の逆元
print(p) # 332748118
```