このページの目的

競技プログラミングの問題を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記事にする)

引用に不都合があればお手数ですがコメントください。記事から内容を削除します。