pythonテクニックまとめ(随時更新)

# このページの目的
競技プログラミングの問題をpythonで解きたいが、
pythonはまだ勉強中の為、競プロで使いがちなテクニックをまとめる。

# pythonの技術についての話

## リストの反転
```python
S=['a','b','c']     # これに対して
S.reverse()         # こうすると「破壊的」にリストを反転する
print(S)
S=['a','b','c']     # これに対して
print(S[::-1])      # こうすると「非破壊的」にリストを反転する
print(S)            # (Sは元のまま)
print("xyz"[::-1])  # こちらのやり方は文字列に対しても可能
```
```python
['c', 'b', 'a']  # reverseされたS(元のSは破壊された)
['c', 'b', 'a']  # S[::-1]の結果
['a', 'b', 'c']  # 元のS(破壊されていない)
'zyx'
```

## アルファベットのリスト
```python
import string
print(string.ascii_lowercase) # アルファベット小文字
print(string.ascii_uppercase) # アルファベット大文字
```
```python
'abcdefghijklmnopqrstuvwxyz'
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
```

## 桁数埋め
```python
"1".zfill(3)      # 0埋め
"1".rjust(3,"9")  # 0以外で埋める場合はこちら
```
```python
'001'
'991'
```

## 小数部第n位での四捨五入
`round`を使用するとうまくいかない場合がある。
(コンピュータ内では数値を2進数で保持している為。)
その為、`decimal`モジュールを使用する。
```python
from decimal import Decimal,ROUND_HALF_UP
d = Decimal("1.2345")
d = d.quantize(Decimal(".001"), rounding=ROUND_HALF_UP) # 小数部第4位の四捨五入
print(d)
```
```python
1.235
```
`quantize`の第一引数で有効桁数、第二引数で切り上げ・四捨五入などのモードを指定する。
なお、`quantize`は「数値化する」という意味。

## 整数部第n位での四捨五入
```python
from decimal import Decimal,ROUND_HALF_UP
d = Decimal("12345")
d = d.quantize(Decimal("1e1"), rounding=ROUND_HALF_UP) # 整数部第1位での四捨五入
print(d,int(d))
```
```python
1.235E+4 12350
```

どういう原理かは詳しく調べていないが、
3行目の"1e1"は"10"ではダメ。数値の10でもダメ。

## 10進数<->N進数変換
### 10進数<->2進数変換
```python
print(format(10, "b")) # 10進数-> 2進数
print(int("1010",2))   #  2進数->10進数
```
```python
'1010' # これは文字列
10     # これは数値
```

### 10進数<->16進数変換
```python
print(format(10, "X"))  # 10進数->16進数
print(int("A",16))      # 16進数->10進数
```
```python
'A'  # これは文字列
10   # これは数値
```

:::note info

16進数変換時、`X`を大文字にするのがポイント。
(`x`にすると、`A`ではなく`a`になる。)
:::

### 10進数<->7進数変換(何進数でも可)
```python
import numpy as np

print(np.base_repr(10, 7))  # 10進数-> 7進数
print(int("13",7))          #  7進数->10進数
```
```python
'13'   # これは文字列
10     # これは数値
```

## 要素分析(何が何個あるか？)
```python
from collections import Counter
people = ["C", "B", "A", "A", "A", "B", "B", "B", "A", "A", "A", "A", "A", "C", "C"]
c = Counter(people)
# (1)
print(c)
# (2)cはCounter型だが、辞書のように扱える
print(c["A"])
# (3)というか辞書を継承しているので、全部使える
print(c.items())
# (4)要素のリストを取得したい場合はこちら。
# 基本的にはlist(c.items())と同じ。ただしmost_common()はsortして出力する。
print(c.most_common())
# Counterクラスは他にも有用なメソッドをいくつか持っているので、
# 使う時がきたら追記する。
```
```python
Counter({'A': 8, 'B': 4, 'C': 3})           # (1)
8                                           # (2)
dict_items([('C', 3), ('B', 4), ('A', 8)])  # (3)
[('A', 8), ('B', 4), ('C', 3)]              # (4)
```

## 順列・組み合わせ
```python
from itertools import permutations,combinations,combinations_with_replacement
print(list(permutations("abc",2)))                   # 順列
print(list(combinations("abc",2)))                   # 組み合わせ
print(list(combinations_with_replacement("abc",2)))  # 重複組み合わせ
```
```python
[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]
[('a', 'b'), ('a', 'c'), ('b', 'c')]
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]
```

## 行列の転置
```python
S=[['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']]
print(list(zip(*S))
```
```python
[('a', 'd', 'g'), ('b', 'e', 'h'), ('c', 'f', 'i')]
```

## 行列の回転(時計まわり)
```python
S=[['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']]
print(list(zip(*S[::-1])))
```
```python
[('g', 'd', 'a'), ('h', 'e', 'b'), ('i', 'f', 'c')]
```

## 二分探索
```python
from bisect import bisect_left,bisect_right
A=[2, 3, 5, 7, 11, 13, 17, 19]
# xx以下の数値がいくつあるか？
print(bisect_right(A,11))
# xx未満の数値がいくつあるか？
print(bisect_left(A,11))
```
```python
5 # 11の右側を探すイメージ
4 # 11の左側を探すイメージ
```

# 競プロならではの話(速度短縮系)
## `pop(0)`は使わない
`pop(0)`は先頭の項目を削除するが、
扱っているリストのサイズが大きかったり、
`pop(0)`を複数回行うと`TLE`になることがある。
リストを逆順ソートし、`pop()`を使用する方が良い。

### ダメなケース
```python
S=['a','b','c']
print(S.pop(0))
print(S)
```
```python
'a'
['b', 'c']
```

### 良いケース
```python
S=['a','b','c']
S.reverse()
print(S.pop())
print(S)
```
```python
'a'
['c', 'b']  # reverse()している為逆になっていることに注意
```

## 重複があるリストは重複を削除した方が良い
重複を削除するコストはあまり高くない。
それよりも重複がある状態で処理する方がコストが高い。
```python
A=[...]        # 重複があるリスト これをそのまま処理するより、
B=list(set(A)) # として重複を削除した方が良い。
```

## スライス(`S[i:j]`)での文字列再生成はあまり使わない
数回使用する程度であれば問題ないが、ループの中で使用すると`TLE`になることがある。

## (主にDPで使う)2変数データ管理について
`DP[(i,j)]`のようにタプルで管理する方法もあるが、どうやらこれは遅いらしい。
他の言語と同様に、二次元リスト(`DP[i][j]`)のように管理した方が良い。

## 順序がある`set`の先頭を取得する場合
`list`に変換して0番目を取得すれば良いが、
`for`ループで要素を取得し、すぐに`break`する方が早い。
※`set`のサイズが大きい場合、`list`への変換に時間がかかっている模様。
(`ABC294-D`がこれが原因で`TLE`した。)

## 要素を頻繁に削除する場合
配列やリストでは要素の削除に時間がかかる。
`set`でデータを保持しておき`remove`で要素を削除する方が早い。
(これも`ABC294-D`の`TLE`の要因。)

## 最小値を常に把握しておきたい場合
```python
from heapq import heappush,heappop
heap=[]
heappush(heap, 3) # 要素の追加
heappush(heap, 1)
heappush(heap, 4)
heappush(heap, 2)

print(heap)
# [1, 2, 4, 3]

mn=heappop(heap) # 最小値の取得と削除
print(mn)
# 1

mn2=heap[0] # 最小値を参照するだけ
print(mn2)
# 2 (最小値1は既に削除された為)
```

# 競プロならではの話(速度短縮系以外)
## `python`にはいろんな種類がある
[こちらの記事](https://qiita.com/kemuniku/items/1f1537e1df2ac8180d9b)に記載してある通り、`python`には5種類ある。
どれを使うんだという話だが、結論は`Python (PyPy 3.10-v7.3.12)`を使用する。
これが多くのケースで一番早いらしい。
が、ABCの初期のコンテストでは`MLE`になってしまう。
その場合、`Python (CPython 3.11.4)`を使用すると同じコードでも
`AC`になることがある。

## 再帰回数を調整する
再帰処理で回答した場合、再帰回数の上限エラーによりREになることがある。
その場合、再帰回数の上限を増やすことでREが解消することがある。
ただし、欲張って増やしすぎるとSampleですらREになるので注意。
下記の通り、100万程度であれば問題ない。
```python
import sys

sys.setrecursionlimit(1000000)
```

## ランレングス圧縮
```python
from itertools import groupby
A="aabbbcbbaaacc"
rle=[(k,len(list(g))) for k,g in groupby(A)]
```

```python
[('a', 2), ('b', 3), ('c', 1), ('b', 2), ('a', 3), ('c', 2)]
```

## ヒープ(優先度付きキュー)
与えられたリストを、ある条件により変化させる必要がある場合に使用。
[こちらの記事](https://qiita.com/T_Wakasugi/items/dac6eb77a3cace54f95e)を参照。

# 参考にさせていただいたサイト様(なるべくQiita記事にする)
引用に不都合があればお手数ですがコメントください。記事から内容を削除します。

https://qiita.com/okkn/items/3aef4458ed2269a59d63

https://qiita.com/shirakiya/items/b1581b29869434d2a8ae

https://qiita.com/ulxsth/items/67f0673adb9c86ecd542

https://qiita.com/juchilian/items/3bc082c96fcf6524f0ef

https://qiita.com/yamadasuzaku/items/577341a2bfc23e307c7d

https://qiita.com/rudorufu1981/items/5341d9603ecb1f9c2e5c

https://qiita.com/kemuniku/items/1f1537e1df2ac8180d9b

https://qiita.com/seigot/items/5091499d75a11cc77e41

https://qiita.com/T_Wakasugi/items/dac6eb77a3cace54f95e