2023.11.05

記事内に商品プロモーションを含む場合があります

AtCoderの問題をPythonで解いてハマったこと（キュー処理、再帰処理等）

tadanori

Contents

はじめに

pythonでAtCoderに参戦すると、処理の遅さが問題になります。pythonが動的型付言語（インタプリタ）なので処理速度が遅いのはしょうがないですが、C++などの他の言語と比べて速度も気をつけないとTLEになりやすいです。

ここでは、AtCoderの問題をpythonで記述する場合にハマりやすいいくつかのポイントについて紹介します。

その他のAtCoderに役立つ記事の一覧は以下にあります。

pythonでキューを実装する場合、何も考えなければリストを使うのが簡単です。

ただ、pythonの場合、キューの先頭を削除する操作が少し遅いです。このため、リストでキューを実装するとTLE（時間超過）することがあります。これに関してはpypyを使っても同じです。

a = []
# キューに１と２を追加
a.append(1)
a.append(2)
print(a)
# キューの先頭を削除
a = a[1:]
print(a)

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)

AtCoderでは提出時にPythonとPyPyを選ぶことができます。pythonよりPyPyの方が基本的には処理速度が速いので、PyPyを選びがちです。

ただ、PyPyは関数呼び出しが少し遅いみたいで、再帰処理などではpythonの方が速いことがあります。実際に、PyPyで提出してTLEしたあと、Pythonで提出するとACしたということもあります。

アルゴリズム的に、自身がある場合はpythonで提出しなおしてみることをおすすめしますします。

Pythonは速度的に少し不利です。必要ならnumpyなどの高速なライブラリを使う方法もありますが、間に合いそうにない場合に備えて、他の言語も習得するというも良いかと思います。

私はGo言語をメインで、Pythonをサブで使っていて、Goで面倒な時はPythonで提出していたりします。こんな感じで言語は柔軟に利用すれば良いかと思います。

個人的には、一応、C++も使える（というかC++をメインで使ってきたのでC++歴が長いです。最近は使わないので、忘れかけていますが）のでそれを使っても良いのですが、C++の環境を設定するのが面倒で使ってない感じです。