PythonでAtCoderを解くときにちょっと得するメモ

はじめに

これからPythonでAtCoderを始めてみよう！となったときに、知っておくとちょっと得する小技の紹介です。
少しPythonコードかけるかな. っていう方向けです。

その1(出力)

sample.py

"""求める出力"""
1 2 3 4 5
#一般的
nums = [1, 2, 3, 4, 5]
str_nums = []
for num in nums:
    str_nums.append(str(num))
print(" ".join(str_nums))
>>> 1 2 3 4 5
#楽な方法
nums = [1, 2, 3, 4, 5]
print(*nums)
>>> 1 2 3 4 5

(一般的かどうかはさておき...)
AtCoderの出力でありがちな空白区切りの複数出力。Pythonにあるjoin関数を用いることで適切な出力になりますが、 join関数はリストの要素が全てstr型(文字列型)でなければエラーになります。 そのため、もしも出力が数字である場合は、(面倒ですが)一度str型に変更しなければなりません。しかも、AtCoderの多くは数字の出力です。そんなときに、 アスタリスク(=*)をリスト型の変数の直前に置いてprintすることで空白区切りになってくれます。 これはリストの要素がint型であれstr型であれ関係なく実行できます。

余談ですが、このアスタリスクによる出力は Python3系 から出ないと使えません。Python2系の方は残念ながらjoin関数に縛られなくてはなりません...(これのためにタグにPython3をつけたと言っても過言ではないです)

その2(最大値の初期値)

sample.py

"""上限値の設定"""
mx = 10**9 #手動
mx = float("inf") #自動

(手動や自動という単語は語弊が生じますが、言いたいことが伝わっていれば問題ないです...)
「最小値を求めよ」という問いに対して、多くの場合は事前に最大値を設定することで、min(mx, 現在の値)と言ったように求めることがあります。しかし、手動で設定した値よりも大きな値が入力で与えられる場合が発生すると誤答になってしまいます。それを避けるために、無理やり大きな数字を設定するよりも float("inf") とした方が僅かなミスが減ると思います。当然、この場合の設定した最大値はfloat型ですが、Pythonという言語の特性上、int型で上書きしても何の問題もありません。

その3(set)

sample.py

nums = [1, 2, 3, ..., 99, 100] #1から100までのリスト
set_nums = set([1, 2, 3, ..., 99, 100]) #1から100までのハッシュテーブル
"""数字があるかの判定"""
#リストの場合
print(50 in nums)
>>> True
#set(ハッシュテーブル)の場合
print(50 in set_nums)
>>> True

リスト型かset型かの些細な違いですが、set型はハッシュテーブルと呼ばれる特殊な形状をしていて、実は存在するかの判定が O(1) でできちゃいます。リスト型だとO(N) になります。例えば要素数が$10^7$個といった大きな場合に探すとなると、計算量が大きく削減できるのでset型は便利です。ちなみにですが、set型に要素を追加する場合は.appendではなく.addを使います。

その4(2次元のset)

sample.py

#エラーになる(list型なので)
nums = set([1,2], [3,4], [5,6])
#正常に実行する(tuple型なので)
nums = set((1,2), (3,4), (5,6))
print((3,4) in nums)
>>> True

AtCoderを解く上で、2次元の組み合わせが存在するかを判定する場合があります。このときに、set型に リスト型で要素を与えてはエラーになります。 set型に2次元で要素を与える場合は tuple型と呼ばれる丸括弧で要素を囲んで与えましょう。 そうすると求めたい組み合わせの要素の判定が O(1) でできます。このとき、 存在判定をする要素もtuple型にしないといけません。

その5(初期値付き辞書)

sample.py

#通常の辞書(エラーver)
dict = {} #初期値なし
dict[0] += 1 #KeyError
#defaultdictによる辞書
from collections import defaultdict
dict_int = defaultdict(int) #初期値が0
dict_int[0] += 1
"""他の使い方もできるよ"""
dict_list = defaultdict(list) #初期値が空リスト(=[])
dict_string = defaultdict(str) #初期値が空文字列(="")

Pythonの通常の辞書型には初期値がありません。これを言い換えると、 Pythonの通常の辞書では存在しないkeyに対してはエラーを吐く のです。try-exceptで抜けても問題ないとは思いますが、スマートにする方法として初期値を持つdefaultdictが便利です。
通常の辞書でKeyErrorを避ける方法は、一度dict[0] = 0などとして初期値を与えてあげることですが、これをfor文の繰り返し処理内で記述すると毎回初期値にリセットされることになります。一方でdefaultdictを使うことで簡単にカウントの処理などが実装できます。もちろん、defaultdictは通常と同じ辞書型に分類されます。

その6(切り上げ)

sample.py

#一般的
import math
num = math.ceil(5/2)
print(num)
>>> 3
#AtCoder
num = -(-5//2)
print(num)
>>> 3

どちらも同じ切り上げの処理ですが、 math.ceilによる切り上げは稀に間違えます。 嘘じゃないです、本当です。大抵は適切に動作しますが、AtCoderでは1つでも誤答があればダメなのです。そこで工夫した切り上げになります。
aとbという2つのint型の切り上げを計算するなら、 -(-a//b) という形式にすることで切り上げが可能になります。
ここで僕の実体験でも載せておきますね(以下の2つの提出コードは17行目以外全く同じです)。
math.ceilによるWA(僕の提出コード)
-(-a//b)によるAC(僕の提出コード)

その7(アルファベットの羅列)

sample.py

#面倒な方法(手入力)
chars = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
#楽な方法
chars = []
for i in range(97,123):
    chars.append(chr(i))
print(chars)
>>> ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]

アルファベットを用意する場面も何回か出てきます。そのときに手で入力しても構いませんが面倒ですので、chr関数を使いましょう。 chr(97)="a", chr(122)="z" になっていて、その間にfor文等の繰り返し処理を加えてあげることで、簡単に 小文字のアルファベット を用意できます。97と123という数字さえ思い出せれば便利です。
もし大文字のアルファベットが必要なら、小文字アルファベット.upper()を使って大文字化してあげましょう。以下のような感じ。

lower_to_upper.py

upp_chars = []
for i in range(97,123):
    low_char = chr(i) #小文字アルファベット
    upp_char = low_char.upper() #大文字アルファベット
    upp_chars.append(upp_char)
print(upp_chars)
>>> ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]

その8(平方数)

sample.py

#通常
import math
N = 9
sqrt_num = math.sqrt(9)
print(sqrt_num)
>>> 3
#ちょいと楽
N = 9
sqrt_num = N**0.5 #指数を0.5にする
print(sqrt_num)
>>> 3

平方数を求める際に、わざわざimport mathをするのが面倒だと個人的に思っています。そんなときは、 指数を0.5にしちゃえばいい だけの話です。$0.5 = \frac{1}{2}$ですからね。

その9(最小公倍数)

sample.py

import math
a = 4
b = 12
gcd = math.gcd(a,b) #最大公約数
print(gcd)
>>> 4
lcm = a*b // gcd #最小公倍数
print(lcm)
>>> 12

現時点(2022年)ではAtCoderにおけるPythonバージョンは3.8です(こちらにソース載せます)。実はPython3.8では 最大公約数は関数がありますが、最小公倍数は関数がありません。 そのため最小公倍数を求める場合は、 aとbの2つのint型に対して a*b // math.gcd(a,b) として求めてあげましょう。
というのも、Python3.9になればmath.lcmという最小公倍数を求める関数が存在するのです。さらに、Python3.8では2つの数字の最大公約数しか求められませんが、Python3.9になると、math.gcdとmath.lcmは3つ以上の複数の数字に対して求めることができるようになります。Python3.9便利ですね。

その10(集合)

sample.py

#リスト型
nums1 = [9, 7, 10, 1, 5, 8, 2, 3, 4, 6]
nums2 = [1, 6, 9, 2, 5, 6, 10, 4, 3, 7]
print(nums1 == nums2)
>>> False
#set型
nums1 = set([9, 7, 10, 1, 5, 8, 2, 3, 4, 6])
nums2 = set([1, 6, 9, 2, 5, 6, 10, 4, 3, 7])
print(nums1 == nums2)
>>> True

set型は集合演算として使うことができます。 リスト型による比較では、順番が揃っていなければ同じと見なされません。しかしset型にすることで、順番関係なく要素が揃っていれば同じとみなしてくれます。

おわりに

僕が経験的にPythonならではかもしれないな〜と思ったことを殴り書きました。少しでも誰かに貢献できれば嬉しいですね。