pythonで競技プログラミング（AtCoder）の問題を解くとき、注意すべき落とし穴

pythonで競技プログラミング（AtCoder）を始めて2年ほど経ち、やっと緑パフォーマンスが安定するようになってきた趣味プログラマーです。この記事では自分が過去にpythonで問題を解く上でハマった落とし穴について書いていきます。
pythonの基本文法やforループや条件分岐を使いこなせるようになり、ABCのAB問題が安定して解けるようになり、アルゴリズム・データ構造の学習を本格的に始めたくらいの人に読んでもらうことを想定しています。
この記事で出てくる落とし穴は知っていれば回避は簡単ですが、知らなければ一見して原因が分かりにくく、どういったワードでググればいいか手がかりが掴みづらいです。この記事が、自分と同じところで詰まった方々の助けになれば幸いです。
実際に自分がハマったミスを挙げているので、「こんなミスするのお前くらいだろ！」ってツッコミがあるかもしれませんがご容赦ください。

##PyPyを使え！
pythonで競技プログラミングをやっている人はもう耳にタコができるほど聞いているかもしれまんせんが念のため。
素のpythonは非常に遅いため、代わりにより早い実装のPyPyを使うべきです。全く同じコードでもpythonで提出するとTLE(時間切れ)、PyPyならAC（正解）ということがよくあります。
再帰関数に関してだけは素のpythonのほうが早いらしいですが、基本的にはPyPyで提出したほうがいいです。

##最大再帰回数制限
再帰関数に関してもう一つ注意することがあります。再帰関数は関数の中でその関数自身を呼び出すような関数です。競技プログラミングでは深さ優先探索の実装などで使われます。終了条件を満たすまで何度も同じ関数を適用するループの一種と考えることができます。
ところで終了条件がない再帰関数は無限ループになります。ためしに無限ループさせてみましょう。

無限ループする再帰関数

def recur(i):
    print(i)
    recur(i+1)
recur(0)

実行するとRecursionError: maximum recursion depth exceeded while calling a Python objectというエラー、つまり再帰の深さが限界に達して止まるのですが、エラーが出る直前までの結果は出力されます。自分の環境では0から976までの数値が出力されています。
なんか……少なくない？
AtCoderの問題の制約ではでは$10^6$というような数値も平気で出てくるのに1000程度で深さの限界に達するのは頼りないです。実際、他の言語で普通に再帰関数で通せる問題も、pythonでそのまま通そうとするとこの再帰エラーが出て弾かれてしまいます。
###対策
実はpythonはデフォルトで最大再帰の深さを1000に設定してあります。通常の用途では問題なくても競プロでは物足りないです。対策はシンプルに再帰関数の制限を変更すれば良いです。これはsys.setrecursionlimit()で設定できます。あまり数値を大きくしすぎると怒られて別のエラーが出るので注意しましょう。また、手元のpython環境で再帰関数制限を増やして実行すると、環境によってはメモリを使いすぎてスタックオーバーフローするかもしれないので気を付けてください。

最大再帰回数制限の変更

import sys
sys.setrecursionlimit(999999999)

##存在判定のin
pythonにはinキーワードというものがあり、要素 in リストのような形で「リストの中に要素が含まれるか」という存在判定を行うことができます。便利なのですが、あまりに簡単すぎてin自体にかかる計算時間について意識が向きづらくなります。（自分はなりました）
リスト$L$の中に、ある要素$a$が含まれるか判定するには、リストの中身を端から端まで順番にひとつずつ見て行かないといけないので、基本的にはリストの長さ分だけの時間がかかります。つまり$O(n)$です。
幅優先探索などで「すでに訪れた場所」を管理する場面が競プロではよくありますが、もし要素 in リストを使って存在判定を行ってしまうと毎回リストの長さ分だけのチェックを行うので簡単にTLE（時間切れ）になってしまいます。
###対策
リストの代わりにセットを使いましょう。セットは重複なしで要素を保管するpythonの基本データ構造です。s = set()で変数sにセットを代入でき、s.add("要素")という形で要素を追加できます。
要素 in リストが一冊の小説の中にあるひとつの単語が含まれているか探すようなものだとすると、要素 in セットは国語辞典の中に「不可能」という単語の項目があるか調べるようなものです。全てのページを隅から隅まで読まなくともふから始まるページだけ調べれば済みます。（実際はもっと高度なことをやってるらしいです。ハッシュとか……）

二次元リストの作り方

pythonでリストを作るとき、例えば全てをの要素を0で初期化したいとき、リストを乗算することで簡単に全要素が0のリストを作ることができます。
###問題

リストの乗算

lst = [0] * 100
#「0」の要素が100個並んだリストが作られる

短く書けて楽なのでよく使います。
となるともちろん、例えば高さH幅Wのマス目が与えられるような問題で二次元リストを作るときにも使いたくなります。
二次元リストとはつまりリストのリストです。リスト乗算を使えば[[0] * 3] * 3というような形で作れそうです。
試しにTic Tac Toe(〇×ゲーム)の盤面をリスト乗算で作ってみよう。

〇×ゲーム

board = [["."]*3]*3
for line in board:
    print(line)

#出力
#['.', '.', '.']
#['.', '.', '.']
#['.', '.', '.']

一見ちゃんと三目並べの盤面が作られているように見えるが……。
盤の真ん中、つまりboard[1][1]に「o」を描きこんでみると……

〇×ゲーム（続き）

#盤の真ん中に「o」を描きこむ
board[1][1] = "o"

for line in board:
    print(line)
#出力
#['.', 'o', '.']
#['.', 'o', '.']
#['.', 'o', '.']
#[1][1]に１つだけ〇を描いたつもりが、縦に3個〇が並んでしまう。

縦に〇が並んで1手で決着がついてしまいました。何故こんなことになるのでしょうか。
実はリスト乗算でリストのリストを作ると、['.','.','.']というリストを3つ作るのではなく、1つのリストへの参照が3つ作られます。つまり、実体は1個しかないのに、3台のカメラで別々に映しているような状態です。
そのため、2行目の要素１つを変更すると、同じリストを映している1行目と3行目も同じように変更されてしまうわけです。
###対策
二次元以上のリストを作るときはリストの乗算を使わない。例えばforループを使ってリストに1個ずつ根気よく要素を加えていけばリストの乗算を使わなくても二次元リストは作れるでしょう。しかし、このやり方だと１つの二次元リストを作るのに何行もコードを書くことになり冗長になります。
代替としてpythonの機能であるリスト内包表記が使えます。リスト内包表記は[ ]内にforやifといったキーワードを埋めこんで、forループや条件分岐を一行で表現してリストを作ることができるという記法です。
例えば0から9までの数値のリストは[i for i in range(10)]で作れます。これは

lst = []
for i in range(10):
    lst.append(i)

とほぼ同じ意味です。詳しくは公式ドキュメントを読んでください（丸投げ）

3×3の盤面を作りたければ

board = [["." for i in range(3)] for j in range(3)]

とすれば作れます。自分はこの作り方をすることが多いです。

board = [["."]*3 for i in range(3)]
#board = []
#for i in range(3):
#    board.append(["."]*3)
#とほぼ同じ

というリストの乗算とリスト内包表記を合わせた形でもOKです。

##多次元リストへのインデックスの順番に注意！

多次元リストに関してもうひとつ。以下の300×300×300の3次元リストを作り、すべての要素に＋1するコードを見てください。

lst = [[[0 for k in range(300)] for j in range(300)] for k in range(300)] 

for i in range(300):
  for j in range(300):
    for k in range(300):
      lst[i][j][k] += 1

実際にAtCoderのコードテスト画面で実行してみると600ms程度でこのプログラムは終了します。コンテスト問題の時間制限はだいたい2000msなので余裕ですね。
ほとんど同じですが次のコードを見てください。リストのインデックスの順番が**lst[i][j][k]からlst[k][j][i]**に変わっているだけです。

lst = [[[0 for k in range(300)] for j in range(300)] for k in range(300)] 

for i in range(300):
  for j in range(300):
    for k in range(300):
      lst[k][j][i] += 1 #インデックスの順番が[i][j][k]から[k][j][i]に変わっている

三次元リストのインデックスの順番が変わっているだけ、つまり見ていく順番が変わっているだけでやっていることは同じです。結局は三次元リストの全ての要素に＋1して終了します。
ところがこのコードを実行すると今度は2500ms程度の時間がかかります。つまり、コンテストでこのコードを提出すると**TLE（時間切れ）**で1回分のペナルティをくらいます。同じことをやっているのに、なぜ「余裕でAC」とTLEに分かれるほど実行時間に差がでるのでしょうか？

詳しくは【C言語】配列へのアクセス順序による処理速度の違い【キャッシュ】などを見てもらえば分かるのですが（丸投げ）、プログラミング言語にはキャッシュという機能があり、あるメモリを見たときに**「多分次に使われるだろうな」ということで近くにあるメモリもついでに高速にアクセスできるように準備してくれます。同じリストの中の要素はメモリ上でも近くにあることが多いので、リストのある要素を見た直後は、同じリスト内の別の要素には高速にアクセスできるというわけです。
1番目のコードではlst[i][j][k]を見た後はlst[i][j][k+1]を見ます。これは同じリスト内で横に移動しているだけなので近くのメモリを見るキャッシュ機能が働き高速に行えます。
ところが、2番目のコードではlst[k][j][i]を見た後にlst[k+1][j][i]を見ることになります。ということはおそらくはlst[k][j][i]から300個の要素が入ったリスト300個分**以上離れた場所のメモリを見ることになりそうです。キャッシュ機能は働かず、より時間がかかります。

###対策
forループのループ変数とリストのインデックスの順番は合わせよう。
二次元リストくらいなら大して気にしなくても大丈夫なことが多いですが、三次元リストくらいになると致命傷になります。
特に**動的計画法(DP)**を使う問題では、インデックスの数が3個以上になることも多く、また、それぞれのインデックスの数値が示す意味を自由に決められるため、無意識のうちに順番が違ってしまいがちなので特に注意する必要があります。

##切り捨て除算
pythonにはint()関数というものがあり、これに小数を入れると整数にして（小数点以下を切り捨てて）返してくれます。

print(int(3.5))
#出力
#3

自分は**intを使えば、返ってくるのが整数だと分かりやすいな？**という考えで、切り捨て除算にもint()を使うことにしました。例えばint(5/2)とすると、5/2は2.5なの2が返ってきます。
この「切り捨て除算」は次のようなコードで破綻します。

print(int(11111111111111/1))
#出力
#11111111111111110656

なぜこんなことになるのか？
これは競プロを初めてみんながハマる小数の誤差によるものです。コンピュータは2進数で計算を行います。2進数の世界では小数点以下の桁は1/2,1/4,1/8などを表すのですが、これは十進数の小数すべてを正確に表せません。そのために誤差が生まれて十進数に直したときに誤った値になってしまうのです。int()に与える値がすでに誤差で誤った値になっているので、間違った結果になってしまうわけですね

###対策
除算には//を使う。
実はpythonには初めから切り捨て除算専用の演算子//があるのでint()を切り捨て除算に使う必要はないです。終わり！
ちなみに小数の誤差をテーマに扱った問題はちょくちょく出てきます。対処法は「文字列として扱う（小数点.より左側と右側で分けて考える）」「乗算して整数にする」「方程式の変形で割り算や√が出てこない形にする」などがあります。

##インデントなし（グローバルスコープ）で直接処理を書くと遅い

これはpypyの代わりにpythonを使っているときくらいでしか問題にならないと思いますが、インデントなし、つまりグローバルスコープで処理を書くときと、関数の中に処理を書いてから関数を実行するのとでは速度に意外と差が出ます。グローバルスコープに直接書くほうが遅いです。

#インデントなしで直接書く（グローバルスコープ）
a = 0
b = 0
print(a + b)

#関数スコープの中で書く
def main():
    a = 0
    b = 0
    print(a + b)
main()

そもそもグローバル変数を扱うのがローカル変数より遅いのが原因らしいです。

###対策
main関数を作ってそこに処理を書く。もしくはpythonではなくpypyを使って、細かいことは気にしない。

##文字列の累算代入
pythonには累算代入演算子というものがあります。これは例えばa = a + 1と書かなければいけないところを、a += 1と書くことで、加算と代入を簡単に表現できるというものです。すでに存在する変数に対して、いくつかの数を加算するので、自分はこの演算子のことを、すでに存在する変数に何かを追加する演算子だと思っていました。

この演算子は整数だけでなく文字列にもあります。

s = "abc"
s += "cdf"
print(s)
#出力
#abcdef

パッ見た感じ、すでにある"abc"という文字列に、"cdf"を追加しているように見えます。実際自分もこの演算子の本質は追加にあるのだと思い込んでいました。
ところで今度は1000万文字の文字列に1文字を1000回追加してみましょう。
元の文字列がが1000万であっても、追加するのは一度に1文字、しかもたったの100回なので大した計算量にはならないはずです。余裕で終わりそうですね。

1文字を1000回追加するだけ

s = "a" * 10000000
for i in range(1000):
  s += "a"

実際にAtCoderのコードテストで実行してみるとだいたい2500ms前後になります。余裕でTLEですね。

なぜ1文字ずつ追加するだけでこんなに時間がかかってしまうのでしょう？

実を言うと、そもそも**+=がすでに存在している文字列に新しい文字列を追加**しているというのが勘違いでした。
このことを確かめるためにid()関数を使います。id()関数はその名前の通り、実行中のコードのオブジェクトのID、他と区別できる固有の番号を調べることができる関数です。もし実行中のコードで同じ番号が出てきたら、それは同じオブジェクトを指していることになり、違った番号が出てきたら違うオブジェクトということになります。(同じコードでも、実行するたびに割り振られるIDは変わることに注意してください)

s = "abc"
print(id(s))
#出力
#139875117261506
#ただし、IDはコードを実行するたびに別のものが割り振られる。

s += "def"
print(id(s))
#出力
#139875117261538

試してみると、最初は変数sが指す文字列のIDは139875117261506だったのが、"def"を追加した後は139875117261538に変わっていました。これはつまり、最初にあった文字列"abc"の後ろに"def"が追加されたのではなく、"abc"と"def"をつなぎ合わせて全く新しい文字列"abcdef"のオブジェクトが作られたということになります。
もし、これを1000万文字の文字列でやると、一度に加えるのがたった1文字でも、毎回1000万文字＋αの文字列が新しく書き写されていくことになります。しかも文字を加えるたびに元となる文字列が長くなっていくので、新しく書き写し時間もそれに応じてどんどん長くなってしまいます。

###対策
文字の追加は文字列ではなくリストとして行う。
pythonの文字列はイミュータブル（変更不能）なオブジェクトなので、文字を追加しようとするとどうしても新しい文字列を１から作ることになります。一方、ミュータブル(変更可能)なリストならば、一部を変更しても元となるリストを再利用し続けるので、無限に新しい文字列が生まれるということもありません。

リストとして扱う

s = ["a"] * 10000000
for i in range(1000):
  s.append("a")

この形なら、500ms程度で終了します。文字列として扱いたいときは最後に文字列メソッドのjoinを使って１つの文字列につなぎなおします。リストのメソッドではなく文字列のメソッドだということに注意してください。つまり
"文字列".join(リスト)という形で使う必要があります。これは**"文字列"**でリスト内の要素をつないでひとつの文字列にして返すという意味になります。","やスペースでつなぐこともできますが、今回はただ文字列をつなぎたいだけなので空文字列でつなぎます。

(続き)joinメソッドで文字列に変換

s = "".join(s)
print(s)
#出力
#aaaaaaaaaaaaaaaaaaaaa...

余談ですが、今回使ったリストも万能ではなく、リストの末尾に追加する場合はすぐに行えるのですが、リストの最初、つまり0番目に要素を挿入すると、リストの長さ分だけの時間がかかります。これは、0番目に要素を入れることで、それ以降の要素のインデックスがすべてひとつずつずらす必要が出るからです。
もしリストの先頭に要素を追加したいときは、リストではなく、collectionsの**deque(デック)**を使ったほうがいいかもしれません。dequeは先頭・末尾への追加・削除が早く、**O(1)**で行えるデータ構造です。

from collections import deque
d = deque() #変数dにdequeをセット
d.append("right") #右端に"right"を挿入
d.appendleft("left")  #左端に"left"を挿入
d.pop() #右端の要素を返して削除する
d.popleft() #左端の要素を返して削除する

ただし、dequeにもインデックス指定のアクセスはリストより遅いという弱点があります。問題に合わせて、適切なデータ構造を選択してください。

##終わりに
読んでくれてありがとうございます。変なことを言ってたり、間違ってる箇所、誤字脱字があればやさしくツッコミを入れてくれるとうれしいです。