はじめに
Python3で競技プログラミングを始めようと思い立って16日が経ちました。Python経験者ではじめて競技プログラミングにチャレンジする人向けに、TIPSや自分がやったことのメモ。
※さすがに古くなったので書き直しました
環境編
Versionが違うことを片隅に置く
- Python最新(例3.9) ≠ AtCoderのPython3 ≠ AtCoderのPypy3
python3 = python3.8.2
pypy3 7.2.0 = python3.6.9
この記事を書いた当初はバージョンの差が大きく、競技プログラミングでよく使う構文に差がありました。しかし、2021年現在、強く意識をしなければならないほどの差はありません。執筆時点、AtCoderのPython/Pypyは以下のVersionです。
最もコンパイルエラーが出そうなのは、型アノテーション周りだと思います。3.6頃から本格的に登場しバージョンの差異があるので注意します。普段の業務でPythonを使っている方は注意です。
Pypyを使う
Pypyのほうが5倍程度高速に動作するといわれています。私はこれを知らずに、コンテストに初めて参加したとき、Python3で提出してTLEを出しました。しかし、コンテスト終了後に全く同じコードをPypy3で提出したらACし、悔しい目にあいました。AtCoderの場合、まず、PyPy3で提出する、としても問題はないです。
エディタはGUI IDEを使う
大学の授業や研究室では、「プログラミングにはviやemacsだ！」とテキストエディタを薦められるケースがあります。しかし、これらにプラグインを入れて仕上げるより各種補完や構文エラーが最初からオールインワンで入っているIDEを使うのが良いです。
私はJetBrainsのPyCharmを使っています。TwitterではVisual Studio Codeを使っている方も多く見かけます。
周りに競プロを始めている友達や先輩がいるなら、何を使っているか聞いて同じものを使うのが良いです。エディタには知っているととても便利な機能がたくさんあります。技を聞いたり、盗んだりできるツールでまずは始めるのはよいでしょう。
AtCoder Unittestを入れてサンプルチェックを簡単に！
AtCoderでは、問題とともにサンプルが記載されています。解法を書いたらサンプル通りであることを確認して提出します。でも、意外と面倒ですよね。
AtCoder Unit Test を使って、動作確認を簡単に！を入れましょう。問題ページからUnittestが作成できます。使う前にインストールしたプラグインのオプションで、言語をPythonに替えておきましょう。
def resolve():
s = input（）
...
print("Yes")
のように普段通りに書いて実行するだけで、入力例のテストが行われます。提出するときは、
s = input（）
...
Print("Yes")
のように、resolve()の中のインデントを下げて提出します。私はコードを選択した後に"Shift-Tab -> Ctrl+C -> Tab"とした後、提出画面にペーストしています。
AtCoder Unittestをカスタムする
AtCoder Unittestは便利なのですが、自分なりの利用の仕方に応じてカスタムできます！
どうせ提出したコードはみんなに公開されるので、ライブラリなど含めて
Forkして自分なりにカスタムしてしまいましょう。なお私は、
- オリジナルだとUnittestのtestcase名に日本語が入りPyCharmで1 caseずつテストできなかった
- 毎回def resolve(): 書くのが面倒だった
ため、上記のように手を加えています。
お役立ちリンク: AtCoder Problems
https://kenkoooo.com/atcoder/
このサイトは自分がどの問題を解いたか(あるいはWAか)を一覧で見られます。右受けから"Login"しましょう。
AtCoder Problems + AtCoder Unittest を活用する(移動時間などで)
最初はABC問題のA,B問題を解くのをお勧めします。その際、AtCoder ProblemsのTable表示で一気にタブを開いて起き、1問解いたらAtCoder Unittestで問題のUnittestを作成して解くとすると、集中して問題を解くことができます。また、一度タブを開いておけば問題も見られます。
競技プログラミングを始めようと思い立った２日後から飛行機で出張だったのですが、空港でA問題のタブを40個くらい開いてフライト中に練習できてなかなか良い時間の過ごし方でした。長い移動の時間など、おすすめです。
コーディング編
さくさく解けてもA,B問題を解く
プログラムを早く書ける人でもA,B問題のノックをやる価値はあると思います。以下の理由です。
- AtCoder的な入出力に慣れる。
list(map(int, input().split()))など毎回打つ呪文に迷うことがなくなります。(もちろん、よくあるパターンを自分なりに関数化しても良いです) - 競技プログラミング/AtCoder的な文章に慣れる。シンプルなことを言っていても難しく書いていると混乱する。などに慣れる。
- 「自分が勝手に思い込みをする」癖などが分かる。A問題は簡単！と思っていると意外と勝手に思い込んでいるケースもあります。
「自分が」分かりやすく書く
問題には解き方がたくさんあります。自分なりに自由に取り組んで楽しみましょう。
N以下の平方数のうち、最大のものを求めてください。
例えばこれは、平方根 > その小数点の切り捨て > その二乗であることに注目して、かっこよく、
n = int(input())
n = int(math.sqrt(n))
n = pow(n, 2)
print(n)
とすることもできますが、
for i in range(100000):
if n < i*i:
print( (i - 1) * (i - 1) )
と書いてもACはACです。
[慣れた人向け] Pythonは遅い？入出力を工夫しよう！
AtCoderのABC問題では、Pythonで時間的に間に合わない問題は(ほぼ)ないです。ただし、稀に、入力行数が多く、入力が間に合わないことがあります。(経験的に$10^6$行以上だと普通に読み込むと間に合わないです)
STEP1: readlineを使う
import sys
input = sys.stdin.readline
と入れるだけで格段に入出力の速度が変わります。input()と同じように使ってよいです。ただし、文字列を扱う場合、最後に改行が入るので注意してください。
STEP2: 一気に読み込む
詳細はコードを見てください。最初にすべての文字を読み込み、あとでそれをばらします。Pythonの入力が遅い理由の大半は複数行を読み込むからです。このため、改行を無視してread()ですべて読み込んでからパースすると、超高速で動作します。
def main():
import sys
read = sys.stdin.read
n, *indata = map(int, read().split())
dat = []
offset = 0
for i in range(n):
a, t = indata[offset + 2*i],indata[offset + 2*i+1]
dat.append( (a, t) )
offset = 2 * n