Pythonで文字列を分割・結合する—split()とjoin()の使い方ガイド
Aru
Aru's テクログ（Aruaru0）
Python初心者がAtCoderでハマりがちなポイント解説（キュー処理・再帰処理など）
Aru
PythonでAtCoderに挑戦する際、特にキュー処理や再帰処理には他の言語にはない「つまずきポイント」がいくつか存在します。この記事では、Python初心者がAtCoderに参戦する際に直面しやすい具体的なポイントを紹介し、それぞれの解決策を提案します。多くの問題はPythonでも十分に挑戦可能ですので、ぜひ諦めずにトライしてみてください。
はじめに
PythonでAtCoderに参戦すると、一番最初に問題になるのは処理速度の遅さです。これは、Pythonが動的型付言語（インタプリタ）なのでしょうがない部分ではありますが、C++などの他の言語と比べると速度超過（TLE）しやすいです。
また、処理速度以外にも、Pythonならではの「つまずきポイント」がいくつか存在します。
ここでは、AtCoderの問題をpythonで記述する場合にハマりやすいいくつかのポイントについて紹介します。
その他のAtCoderに役立つ記事の一覧
pypyを使う
Pythonで処理が間に合わない場合は、pypyを使うと解決することがあります。pypyを使うには、AtCoderのコード提出時にpypyを選択すればOKです。
多くの場合、これで間に合うようになりますが、全ての処理が早くなるわけではない（むしろ遅くなることもある）ので、これを使えばOKとなる訳ではないことに注意する必要があります。
慣れないうちは、「とりあえずpypyで」というのはありだと思います。
PyPyの方が遅いことがある
上で書いたようにAtCoderではPythonの代わりにpypyを選択することができるため、高速なpypyを選びがちです。
ただ、PyPyは関数呼び出しが少し遅いので、再帰処理などではpythonの方が速いことがあります。実際に、PyPyで提出してTLEしたあと、Pythonで提出するとACしたということも経験しました。
処理的に間に合うはずだと、自信がある場合はpythonで提出し直してみることをおすすめしますします。
キュー
リストでキューを実装した場合の問題点
Pythonでキューを実装する場合、何も考えなければリストを使うのが簡単です。
多くの問題では、キューをリストで実装しても間に合いますが、Pythonのリストは、先頭を削除する操作が少し遅いです。このため、リストを使ってキューを実装するとTLE（時間超過）することがあります（これに関してはpypyを使っても同じです）。
a = []
# キューに１と２を追加
a.append(1)
a.append(2)
print(a)
# キューの先頭を削除
a = a[1:]
print(a)高速化方法（dequeを使う）
collectionsに含まれているdequeを使うことでキューの処理を高速に行うことができます。書き方は似ていますが、宣言の仕方が違う（listの場合は空のリスト作成。dequeの場合はdeque()を呼び出し）のと、削除の再はpopleft()関数を使うところです。
pop()は末尾、popleft()は先頭から要素を削除し、削除した要素の値を返す関数です。キューは先に入れた方を削除するのでpopleft()を使えば実現できることになります。
変数へはa[0]でアクセスできるので、そのあたりはリストと似た感じで使うことができます。
ちなみに、スタックはpopleft()をpop()に入れ替えるだけで実現できます。ただ、リストをスタックとして利用する場合は、そこまで遅くないのでスタック目的でdequeを使う機会は少ないです。
from collections import deque
a = deque()
# キューに１と２と３を追加
a.append(1)
a.append(2)
a.append(3)
print(a)
# キューの先頭を削除
b = a.popleft()
print(a, b)再帰呼び出しのエラー
Pythonは標準では、再帰で繰り返し呼び出せる数が非常に少ないです。このため、再帰を使う問題でスタックオーバーフローを起こしてしまうことがあります。
これを回避するには、スタックをあらかじめ大きめに取っておくという方法があります。
以下のコードはスタックサイズを設定するものです。$10^6$くらい取っておけばとりあえず問題ないと思います。
テンプレートを用意しておくのであれば、先頭にこのコードを入れておけば、再帰の問題でスタック不足によるミスを防ぐことができます。
import sys
sys.setrecursionlimit(10**6)まとめ
Pythonは速度的に少し不利です。必要ならnumpyなどの高速なライブラリを使う方法もありますが、間に合いそうにない場合に備えて、他の言語も習得するというも良いかと思います。
私はGo言語をメインで、Pythonをサブで使っていて、Goで面倒な時はPythonで提出していたりします。こんな感じで言語は柔軟に利用すれば良いかと思います。
個人的には、一応、C++も使える（というかC++をメインで使ってきたのでC++歴が長いです。最近は使わないので、忘れかけていますが）のでそれを使っても良いのですが、C++の環境を設定するのが面倒で使ってない感じです。
ABOUT ME
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中
