このページの目的
競技プログラミングの問題をpythonで解きたいが、
pythonはまだ勉強中の為、競プロで使いがちなテクニックをまとめる。
pythonの技術についての話
リストの反転
S=['a','b','c'] # これに対して
S.reverse() # こうすると「破壊的」にリストを反転する
print(S)
S=['a','b','c'] # これに対して
print(S[::-1]) # こうすると「非破壊的」にリストを反転する
print(S) # (Sは元のまま)
print("xyz"[::-1]) # こちらのやり方は文字列に対しても可能
['c', 'b', 'a'] # reverseされたS(元のSは破壊された)
['c', 'b', 'a'] # S[::-1]の結果
['a', 'b', 'c'] # 元のS(破壊されていない)
'zyx'
アルファベットのリスト
import string
print(string.ascii_lowercase) # アルファベット小文字
print(string.ascii_uppercase) # アルファベット大文字
'abcdefghijklmnopqrstuvwxyz'
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
桁数埋め
"1".zfill(3) # 0埋め
"1".rjust(3,"9") # 0以外で埋める場合はこちら
'001'
'991'
小数部第n位での四捨五入
roundを使用するとうまくいかない場合がある。
(コンピュータ内では数値を2進数で保持している為。)
その為、decimalモジュールを使用する。
from decimal import Decimal,ROUND_HALF_UP
d = Decimal("1.2345")
d = d.quantize(Decimal(".001"), rounding=ROUND_HALF_UP) # 小数部第4位の四捨五入
print(d)
1.235
quantizeの第一引数で有効桁数、第二引数で切り上げ・四捨五入などのモードを指定する。
なお、quantizeは「数値化する」という意味。
整数部第n位での四捨五入
from decimal import Decimal,ROUND_HALF_UP
d = Decimal("12345")
d = d.quantize(Decimal("1e1"), rounding=ROUND_HALF_UP) # 整数部第1位での四捨五入
print(d,int(d))
1.235E+4 12350
どういう原理かは詳しく調べていないが、
3行目の"1e1"は"10"ではダメ。数値の10でもダメ。
10進数<->N進数変換
10進数<->2進数変換
print(format(10, "b")) # 10進数-> 2進数
print(int("1010",2)) # 2進数->10進数
'1010' # これは文字列
10 # これは数値
10進数<->16進数変換
print(format(10, "X")) # 10進数->16進数
print(int("A",16)) # 16進数->10進数
'A' # これは文字列
10 # これは数値
16進数変換時、Xを大文字にするのがポイント。
(xにすると、Aではなくaになる。)
10進数<->7進数変換(何進数でも可)
import numpy as np
print(np.base_repr(10, 7)) # 10進数-> 7進数
print(int("13",7)) # 7進数->10進数
'13' # これは文字列
10 # これは数値
要素分析(何が何個あるか？)
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クラスは他にも有用なメソッドをいくつか持っているので、
# 使う時がきたら追記する。
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)
順列・組み合わせ
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))) # 重複組み合わせ
[('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')]
行列の転置
S=[['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']]
print(list(zip(*S))
[('a', 'd', 'g'), ('b', 'e', 'h'), ('c', 'f', 'i')]
行列の回転(時計まわり)
S=[['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']]
print(list(zip(*S[::-1])))
[('g', 'd', 'a'), ('h', 'e', 'b'), ('i', 'f', 'c')]
二分探索
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))
5 # 11の右側を探すイメージ
4 # 11の左側を探すイメージ
競プロならではの話
pop(0)は使わない
pop(0)は先頭の項目を削除するが、
扱っているリストのサイズが大きかったり、
pop(0)を複数回行うとTLEになることがある。
リストを逆順ソートし、pop()を使用する方が良い。
ダメなケース
S=['a','b','c']
print(S.pop(0))
print(S)
'a'
['b', 'c']
良いケース
S=['a','b','c']
S.reverse()
print(S.pop())
print(S)
'a'
['c', 'b'] # reverse()している為逆になっていることに注意
重複があるリストは重複を削除した方が良い
重複を削除するコストはあまり高くない。
それよりも重複がある状態で処理する方がコストが高い。
A=[...] # 重複があるリスト これをそのまま処理するより、
B=list(set(A)) # として重複を削除した方が良い。
スライス(S[i:j])での文字列再生成はあまり使わない
数回使用する程度であれば問題ないが、ループの中で使用するとTLEになることがある。
pythonにはいろんな種類がある
こちらの記事に記載してある通り、pythonには5種類ある。
どれを使うんだという話だが、結論はPython (PyPy 3.10-v7.3.12)を使用する。
これが多くのケースで一番早いらしい。
が、ABCの初期のコンテストではMLEになってしまう。
その場合、Python (CPython 3.11.4)を使用すると同じコードでも
ACになることがある。
再帰回数を調整する
再帰処理で回答した場合、再帰回数の上限エラーによりREになることがある。
その場合、再帰回数の上限を増やすことでREが解消することがある。
ただし、欲張って増やしすぎるとSampleですらREになるので注意。
下記の通り、100万程度であれば問題ない。
import sys
sys.setrecursionlimit(1000000)
(主にDPで使う)2変数データ管理について
DP[(i,j)]のようにタプルで管理する方法もあるが、どうやらこれは遅いらしい。
他の言語と同様に、二次元リスト(DP[i][j])のように管理した方が良い。
ランレングス圧縮
from itertools import groupby
A="aabbbcbbaaacc"
rle=[(k,len(list(g))) for k,g in groupby(A)]
[('a', 2), ('b', 3), ('c', 1), ('b', 2), ('a', 3), ('c', 2)]
ヒープ(優先度付きキュー)
与えらえたリストを、ある条件により変化させる必要がある場合に使用。
こちらの記事を参照。
参考にさせていただいたサイト様(なるべくQiita記事にする)
引用に不都合があればお手数ですがコメントください。記事から内容を削除します。