はじめに
以前、PythonでAtCoderを解く時にちょっと得するメモというタイトルで、PythonとAtCoderに関する内容を書きました。それの続きになります。
以下に書く内容は、思いついた順番です。
その1(逆順)
sample_list = ["a", "b", "c", "d", "e", "f", "g"]
sample_txt = "abcdefg"
# 逆順にする方法1
sample_list.reverse()
print(sample_list)
>>> ["g", "f", "e", "d", "c", "b", "a"]
print(sample_txt.reverse())
>>> AttributeError: 'str' object has no attribute 'reverse'
# 逆順にする方法2
print(sample_list[::-1])
>>> ["g", "f", "e", "d", "c", "b", "a"]
print(sample_txt[::-1])
>>> gfedcba
Pythonで逆順にする方法にはreverse()が用意されています。しかしこちらは、list型のみ逆順にすることが可能であり、str型ではエラーを返されてしまいます。
一方で、[::-1]というスライスを使うことで、str型でもlist型でも逆順にすることが可能です。こちらの方が使い勝手が良く、楽だと思います。
このスライスの具体的な説明としては、range()と一緒に見てみるとわかりやすいと思います。
# range
for i in range(0, 7, 2):
print(i, end=" ")
>>> 0 2 4 6
# slice
nums = [0, 1, 2, 3, 4, 5, 6, 7]
print(nums[0:7:2])
>>> [0, 2, 4, 6]
スライスを使う時の引数はrange()と全く同じで、第一引数からそれぞれstart, stop, stepとなります。Pythonでスライスを使う際は[:]というように、startとstopを指定しなければ全選択になります。そのスライスの第三引数のみを-1にすることで、逆順にすることが可能になります。
その2(スワップ)
a, b = 100, -1
a, b = b, a
print(a, b)
>>> -1 100
nums = [100, -1, 2]
nums[0], nums[1] = nums[1], nums[0]
print(nums)
>>> [-1, 100, 2]
変数やlistに格納されている内容をスワップする際に、Pythonの場合は変数宣言の要領でスワップができます。これはPythonというより、動的な言語全般の特徴だと思います。
わざわざ、スワップするために他の変数を用意したりしなくて良い点が好みです。
その3(ソートの詳細設定)
nums = [4, -3, -1, 5, -2]
print(sorted(nums))
>>> [-3, -2, -1, 4, 5]
print(sorted(nums, key=abs))
>>> [-1, -2, -3, 4, 5]
Pythonのsort()やsorted()の引数にkeyがあります。これを使うことで、単純に数の大きさでソートする以外のソート方法が選べます。
他にも色々な使い方があります。
str_nums = ["01", "12345", "1", "6543"]
print(sorted(str_nums, key=len))
>>> ['1', '01', '6543', '12345']
xy_pos = [(1, 3), (5, 2), (4, 1), (9, -100)]
print(sorted(xy_pos, key=sum))
>>> [(9, -100), (1, 3), (4, 1), (5, 2)]
その4(lambda)
xy_pos = [(1, 3), (5, 2), (4, 1), (9, -100)]
print(sorted(xy_pos, key=lambda x: x[1]))
>>> [(9, -100), (4, 1), (5, 2), (1, 3)]
sort()やsorted()にkeyという引数があることは説明しましたが、ここに無名関数と呼ばれるlamndaを使うことができます。
上記のコードでは、xという無名関数を定義しています。その定義はx[1]であり、xy_posという二次元配列の1番目(0から数えて)の要素でソートするようにしています。その結果、二次元配列のそれぞれの要素の1番目が小さい順にソートできています。
lamndaは他にもAtCoderで使いたくなる場面が出てくると思います。
# 二次元のdefaultdictを作るとき
from collections import defaultdict
dic = defaultdict(lambda: defaultdict(str))
dic[0][0] = "二次元defaultdict"
print(dic[0][0])
>>> 二次元defaultdict
# 特別なソートのルールを定義したいとき
rule = ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"]
rule_weight = {rule[i]: i for i in range(len(rule))}
print(rule_weight)
>>> {'1': 0, '2': 1, '3': 2, '4': 3, '5': 4, '6': 5, '7': 6, '8': 7, '9': 8, '10': 9, 'J': 10, 'Q': 11, 'K': 12}
cards = ["K", "1", "5", "2", "Q", "9", "8", "3", "6", "4", "7", "10", "J"]
print(sorted(cards, key=lambda x: rule_weight[x]))
>>> ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']
二次元のdefaultdictを作る際には、lamndaが必要になります。
また、今回はトランプをイメージしましたが、数字の大きさが数字だけじゃない特殊なソートを実施したい場合などの場面でも、lamndaを使うことでコーディングの量を減らした実装ができると思います。
その5(複数の比較演算)
H, W = 10, 5
xy_pos = [(0, 0), (2, 2), (6, 1), (2, 11)]
for x, y in xy_pos:
if 0 <= x < W and 0 <= y < H:
print("Yes")
else:
print("No")
>>> Yes
>>> Yes
>>> No
>>> No
Pythonでは比較演算を複数同時に実行することができます。こちらも動的な言語ならではの特徴だと思います。「0以上Wより小さい」として条件を1つ書くか、「0以上」&&「Wより小さい」と2つ書くか、という細かい話です。
AtCoderで二次元配列をはみ出すか否かを判定する際に、コード量が少なくて済むので助かります。
その6(f-strings)
num = 1000000
print(f"{num:,}")
>>> 1,000,000
Pythonで文字列を出力する際に、昔は.format()を使っていたと思いますが、イマドキはf-stringsですよね。そのf-stringsですが、変数(じゃなくても可)を書き込む{}の中で、:.という記号の後に,(カンマ)を入れてあげると、3桁区切りでカンマを打ってくれます。
(AtCoderと関係なくなりますが)f-stringsの:.は結構使えると思います。カンマ以外には以下のような使い方があります。個人的には、小数の桁を落とす時に使うことが多いです。
# 色々な表記の小数点以下を2桁にする
print(f"{1.2345:.2f}")
>>> 1.23
print(f"{12.345:.2%}")
>>> 1234.50%
print(f"{123.45:.2e}")
>>> 1.23e+02
その7(n進数→10進数, 10進数→n進数)
print(int("1010", 2))
>>> 10
print(int("13", 7))
>>> 10
Pythonでn進数を10進数に変換する方法は、実はよく使うであろう int()でできます。int()は、int型でない型をint型に変換する時に使うと思いますが、第二引数がbaseになっていて、第一引数の文字列をbaseの進数に適した結果を返すようになっています。
import numpy as np
print(np.base_repr(10, 2))
>>> 1010
print(np.base_repr(10, 7))
>>> 13
逆に、10進数をn進数にする場合は、numpyに頼る必要があります。ですが、AtCoderはnumpyに対応しているので、何の問題もないと思います。
その8(ゼロ埋め)
num1 = "1"
print(num1.zfill(4))
>>> 0001
num2 = "10"
print(num2.zfill(4))
>>> 0010
str型の数字をゼロ埋めする時には zfill()を使うことで、ゼロ埋めをすることができます。
個人的によく使う場面としては、ビット全探索を実行するときです。足りない桁の箇所をゼロ埋めすることで、ビット全探索を実装します。
気分によっては、itertoolsのcombinationsを使ってビット全探索をするときもありますが、ちょっと実装がめんどくさいので、近頃はゼロ埋めをして実装することが多いです。ゼロ埋めするやり方の方が、名前の通り、ビット全探索っぽいので。
その9(辞書のkeyを取り出す)
dic = {1: "apple", 2: "orange", 3: "banana"}
for k in dic:
print(k, dic[k])
>>> 1 apple
>>> 2 orange
>>> 3 banana
for k in dic.keys():
print(k, dic[k])
>>> 1 apple
>>> 2 orange
>>> 3 banana
Pythonの辞書型で、for文を使って辞書の全てのkeyを取り出すときには、keys()を使わずとも取り出せます。
別にkeys()で取り出せば良いということはわかっているのですが、たまにkey? keys? keys()?といった具合に、複数形だったか丸括弧必要だったか、という細かいことを忘れてしまうんですよね。調べたら解決する内容ですが、AtCoderで1秒でも早くACが欲しいコンテスト本番では、そんなことで迷って時間が掛かるくらいなら、いっそのことkeys()の呪縛から解放されたくなります。
その10(累乗の**とpow())
print(2**10)
>>> 1024
print(pow(2, 10))
>>> 1024
Pythonで累乗を計算する際には、**でもpow()でも、どちらでも計算することができます。特に**による計算方法は、Pythonならではの特徴的な文法ですよね。正直、累乗の計算をするだけならどっちでも良いと思います。
ですがAtCoderでは、何回も累乗を計算して、その余りを求める問題を見かけます。そのときには、 pow()の方が高速に計算を実施することができます。あくまで、「余りを求める」という条件下です。いわゆる繰り返し二乗法というやつです。
pow()では、第三引数にmodを設定することができ、この第三引数に余りを求めるための商を記述するだけで、繰り返し二乗法がはやくなります。
実際に、$7^{10000}$ mod $998244353$ を1000回繰り返すプログラムを書いて、その実行時間を**とpow()で比較してみました。
検証したコードはこちら
"""notebookを無理やりねじ込みました"""
import matplotlib.pyplot as plt
import japanize_matplotlib
import time
from tqdm.notebook import tqdm
MOD = 998244353
N = 10**3
n = 10**4
# **
num = 7
times1 = []
for _ in tqdm(range(N)):
num **= n
num %= MOD
times1.append(time.time())
start = times1[0]
times1 = [t-start for t in times1]
# pow
num = 7
times2 = []
for _ in tqdm(range(N)):
num = pow(num, n, MOD)
times2.append(time.time())
start = times2[0]
times2 = [t-start for t in times2]
plt.figure(figsize=(8,6))
x = [i for i in range(N)]
plt.plot(x, times1, c="r", label="**")
plt.plot(x, times2, c="b", label="pow()")
plt.xlabel("計算回数(回)")
plt.ylabel("実行時間(s)")
plt.title("基数=7, 指数=10000")
plt.grid()
plt.legend()
plt.show()
そして、得られたグラフが以下のようになりました。
僕も初めて検証したのですが、ここまで大きく差が出るものだとは思いませんでした。
AtCoderでは繰り返す回数がもっと多いことがあるので、よりpow()を使う方が良いということがわかるかと思います。
おわりに
辞書のkeyを取り出すときには、迷わずkeys()を使えるようにします。
不備や訂正箇所があれば、ご指摘お願いしますmm