はじめに
AtCoderは、おおよそ週に1回程度プログラミングコンテストが開催されている日本最大規模の競技プログラミングコンテストサイトです。特に初学者には学習コストが比較的小さいためにPythonがおすすめされがちです。
本記事では、Pythonでのコーディングが楽になる、標準ライブラリや組み込み関数によるイディオムを紹介しています。あくまでイディオムを集めたものであり、アルゴリズムのPython実装は取り扱いません。
頻出度 高
逆順にする
L = [1, 2, 3, 4]
reversed_L = L[::-1]
print(reversed_L)
>> [4, 3, 2, 1]
解説
スライスを利用することで、スタート、エンド、ステップを指定することができますが、ステップに負数を指定することで、逆順を実現できます。また、以下のコードはほぼ等価です。
list(reversed(L))
<=> L[::-1]
リストの連続する２つのイテレート
L = [1, 2, 3, 4]
for l0, l1 in zip(L, L[1:]):
print(l0, l1)
>> 1 2
2 3
3 4
解説
スライスを利用することで開始位置をずらしたリストを作ることができます。組み込み関数のzipを組み合わせることで連続する要素をイテレートすることができます。また標準ライブラリのitertools.pairwiseでも実現できます。
L => [1, 2, 3, 4]
L[1:] => [2, 3, 4]
list(zip(L, L[1:])) => [(1, 2), (2, 3), (3, 4)]
応用
スライスをうまく調整することでオーバーラップをしないイテレートも実現できます。
L = [1, 2, 3, 4]
for l0, l1 in zip(L[::2], L[1::2]):
print(l0, l1)
>> 1 2
3 4
タプルとなったリストを分割
XY = [(0, 0), (1, 2), (-1, -2)]
X, Y = zip(*XY)
print(X, Y)
>> (0, 1, -1) (0, 2, -2)
解説
引数に*(アスタリスク)をつけた場合、引数が展開されて渡されます。すなわち以下の２つの式は等価になります。
zip(*[(0, 0), (1, 2), (-1, -2)])
<=> zip((0, 0), (1, 2), (-1, -2))
応用
2次元リストの転置などにも利用できます。
G = [
[1, 2, 3],
[4, 5, 6]
]
G_T = list(map(list, zip(*G)))
for g in G_T:
print(g)
>> [1, 4]
[2, 5]
[3, 6]
ランレングス圧縮
from itertools import groupby
S = 'oooxxxxxoxoxxo'
X = list((g, len(list(it))) for g, it in groupby(S))
print(X)
>> [('o', 3), ('x', 5), ('o', 1), ('x', 1), ('o', 1), ('x', 2), ('o', 1)]
解説
groupbyの返り値はkeyとgroupとなっていますが、groupはイテレータとして返ってくるため、長さを取得するには一旦リストに変換するなど一手間が必要になります。
頻出度 中
a,b,c,...,x,y,z と0,1,2,...,23,24,25の相互変換
c = "z"
print(ord(c) - ord("a")) # Alphabet to Integer
>> 25
i = 25
print(chr(i + ord("a"))) # Integer to Alphabet
>> z
解説
文字コードの上でもアルファベットがアルファベット順に連続で並んでいることを利用して整数をアルファベットの変換を行います。また次のコードもよく使います。変換内容は同様ですが、indexによる走査が行われるので少しだけパフォーマンスが低いかもしれません。
from string import ascii_lowercase as Alphabet
c = "z"
print(Alphabet.index(c)) # Alphabet to Integer
>> 25
i = 25
print(Alphabet[i]) # Integer to Alphabet
>> z
リストのコピーを作成する
def f(A):
A.append(9)
print(A)
A = [0, 1, 2]
f(A[:])
print(A)
>> [0, 1, 2, 9]
[0, 1, 2]
解説
スライスで作られるリストは、元のリストとは異なるidであることを利用したイディオムです。コピーされたリストの要素の参照先は元のリストの参照先と同じなので、そこの部分もコピーしたい場合はcopy.deepcopyを使いましょう。
頻出度 低
ネストされたイテレータを１つのfor文でイテレートする
from itertools import chain
tree = [[1, 2], [3, 5], [], [4], [], []]
for node in chain(*tree):
print(node)
>> 1
2
3
5
4
応用
二次元リストの中身を走査する際に利用したりと応用の幅は広いです。
from itertools import chain
G = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
if not any(chain(*G)): # G has only zero.
数え上げた結果をまとめる
from collections import Counter
A = Counter([1, 1, 2, 2, 3, 3, 4])
B = Counter([1, 2, 3, 4, 5])
print(A + B)
>> Counter({1: 3, 2: 3, 3: 3, 4: 2, 5: 1})
print(A - B)
>> Counter({1: 1, 2: 1, 3: 1})
print(B - A)
>> Counter({5: 1})
解説
Counterオブジェクトは、辞書オブジェクトでありながら、加算・減算のオペレータが実装されており、数え上げした結果をまとめるときに便利です。
value値が0以下になる場合、keyごとなくなってしまうのでそこだけ注意しましょう。
おわりに
他にも掲載してほしいイディオムや修正・加筆案などあればコメントいただければ幸いです。