このページの目的
競技プログラミングの問題を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')]
競プロならではの話
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()している為逆になっていることに注意
pythonでは解けない問題がある
まず最初に競プロでは、実行時間及びメモリに制限がある。
pythonでは標準入力をinput()で読み込むだけで、70MBほど
使用するらしく、メモリ制限が64MBの問題は解けない。
(MLE (Memory Limit Exceeded)になる。)
ただ、最近はメモリ制限がほとんど1024MBになっているので、
基本的に気にする必要はない。
※ABC001～ABC005くらいまでは64MBの制限があり、
pythonでは解けなかった。(ので、awkで解いた。)
参考にさせていただいたサイト様(なるべくQiita記事にする)
引用に不都合があればお手数ですがコメントください。記事から内容を削除します。