はじめに
競技プログラミングや AtCoder についての説明はここでは割愛します。（こちらのけんちょんさんの記事が参考になります）
本記事は Python で競技プログラミング（競プロ）を始めたい人向けの内容になっています。競技プログラミングといえば C++ でやるのがメジャーですが、最近（2019年現在）は Python も C++ に次ぐ勢力にまでなりました。そこで本記事では、Python で競技プログラミングを始めたい方向けの入門として、入出力を始めとする競技プログラミングで主に用いる基本的な文法の解説をします。
問題例も載せていますが、* 印がついてるものは始めたてだと難しいので解かないで大丈夫です。それ以外のものは実際の問題を見て、わかりそうなら解いてみるのがおすすめです。
AtCoder 社長の chokudai さん曰く、初心者に Python はおすすめらしいです。
おすすめはどれ、って言われると、Java, C#, Pythonあたりになるのかなあ。
— chokudai(高橋 直大)🍆🍡 (@chokudai) December 19, 2019
Java, C#はHello Worldまでが遠いのがちょっとマイナスなのと、Main関数にstaticがついてるのが、超初心者にはマイナスなんだけど、速度があるし統合開発環境がセットで入るのが楽。
Pythonは、教材増えてきたし書きやすいし
対象者
- 競技プログラミングに興味があって、Python で始めてみたい方
- もしプログラミング自体が初めてであれば、本記事ではなく「Python入門（Python版 APG4b）」を読むことを勧めます。
- 既に C++ 等の他の言語で競技プログラミングをやっているが、Python でも書けるようになりたい方
Python で競技プログラミングを始めるために必要なこと
PyCharm などの IDE やエディタを使うのも良いですが、環境構築が面倒な方は AtCoder の各問題ページにあるコードテストや、オンライン実行環境の paiza.io を使うのもおすすめです。
また、Python には Python2 と Python3 がありますが、本記事では現在主流の Python3 について扱います。
入力
まず問題に応じた入力を受け取らないと何も始まりません。
整数
入力を整数として受け取りたいとき。
1行に1つ
入力が 1 行に整数 1 つの場合。
n = int(input())
使用問題例: ABC145 A - Circle
1行に複数
入力が 1 行に複数ある場合。
10 20
みたいなときです。
n, m = map(int, input().split())
使用問題例: ABC144 A - 9x9
整数（リスト編）
複数の整数をリストとして受け取りたいときもあります。
1行
1 2 3 4
みたいなときです。
a = list(map(int, input().split())) # [1, 2, 3, 4] になる
使用問題例: ABC142 B - Roller Coaster
複数行に1列ずつ
1
2
3
4
みたいなときです。
a = [int(input()) for i in range(n)] # [1, 2, 3, 4] になる
n は行数です。for 文を使っても良いですが、このようにリスト内包表記を使うと楽です。
使用問題例: ABC115 B - Christmas Eve Eve
複数行に複数列ずつ
1 2 3 4
5 6 7 8
9 10 11 12
みたいなときです。
a = [list(map(int, input().split())) for i in range(n)]
# [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] になる
使用問題例: ABC133 B - Good Distance
文字列
入力を文字列として受け取りたいとき。
1行に1つ
入力が 1 行に文字列 1 つの場合。
abcde
みたいなときです。
s = input()
使用問題例: ABC146 A - Can't Wait for Holiday
1行に複数
入力が 1 行に複数ある場合。
abcd efghi
みたいなときです。
s, t = input().split()
使用問題例: ABC078 A - HEX
文字列（リスト編）
複数の文字列をリストとして受け取りたいときもあります。
1行
a b c d e
みたいなときです。
s = input().split() # ['a', 'b', 'c', 'd', 'e'] になる
こちらはあまり使う機会がないです。
1行 その2
abcde
を文字列ではなくリストとして受け取ることもできます。
s = list(input()) # ['a', 'b', 'c', 'd', 'e'] になる
使用問題例: ABC009 C - 辞書式順序ふたたび *（かなり難しいです）
複数行
....
.#..
..#.
みたいなときです。
g = [list(input()) for i in range(n)] # n は行数
# [['.', '.', '.', '.'], ['.', '#', '.', '.'], ['.', '.', '#', '.']] になる
使用問題例: ATC001 A - 深さ優先探索 *（典型ですが知らないと難しいです）
出力
結果を出力しましょう。
基本
基本的に問題に合わせて以下のように出力すれば大丈夫です。
print(ans) # ans は任意の変数
変数以外に文字列や数値を直接出力することもできます。
print("Yes")
print(0)
また、何も指定しなければ行末に改行が入ります。end= 引数で指定してあげれば行末の改行をなくすこともできます。
print("abc")
print("def")
print("abc", end="")
print("def")
abc
def
abcdef
カンマ区切りで複数出力することもできます。その際は sep= 引数で区切り文字を指定できます。
print("a", "b", "c") # -> a b c
print("a", "b", "c", sep="") # -> abc
リストの出力
また、リストの中身を空白区切りで出力したい場合は以下のようなこともできます。この際も区切り文字を指定できます。
a = [3, 1, 4, 1, 5]
print(*a)
print(*a, sep="")
3 1 4 1 5
31415
補足ですが、最近の AtCoder の問題は空白区切りの出力と改行区切りの出力が区別されないようです。具体的には、
3 1 4 1 5
3
1
4
1
5
のどちらも提出する際は区別されません。
問題例: ABC137 B - One Clue
基本文法
入力と出力だけできても肝心の中身が書けないとどうにもなりません。ここでは ABC (AtCoder Beginner Contest) の A 問題と B 問題レベルを解くのに最低限必要な文法について説明します。
詳しい文法については Python3基礎文法 などを参考にしてください。
四則演算
| 演算子 | 意味 |
|---|---|
| + | 足し算 |
| - | 引き算 |
| * | 掛け算 |
| / | 割り算 |
| // | 切り捨て割り算 |
| % | 余り |
| ** | 累乗 |
print(4 + 3) # 7
print(4 - 3) # 1
print(4 * 3) # 12
print(4 / 3) # 1.3333333333333333
print(4 // 3) # 1
print(4 % 3) # 1
print(4 ** 3) # 64
問題例: ABC145 A - Circle
リスト（list）
a = [] # 空のリスト
a.append(3) # リストに追加 [3]
a.append(1) # [3, 1]
a.append(4) # [3, 1, 4]
a.append(1) # [3, 1, 4, 1]
print(a[0]) # -> 3
print(a[3]) # -> 1
負の数を入れると後ろから見ることもできます。
a = [0, 1, 2, 3, 4, 5]
print(a[-1]) # -> 5
print(a[-2]) # -> 4
他によくつかうメソッドとして list.count() や list.index() があります。
a = [3, 1, 4, 1, 5]
# list.index(x) で要素 x が list の中で何番目にあるか返ってくる（複数ある場合は最小のもの）
print(a.index(1)) # -> 1
# list.count(x) で要素 x が list 内にいくつあるかが返ってくる
print(a.count(1)) # -> 2
スライス
スライスを使うことでリストの一部を取得することができます。
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a[1:3]) # -> [1, 2]
print(a[2:10:2]) # -> [2, 4, 6, 8]
print(a[5:]) # -> [5, 6, 7, 8, 9]
print(a[:4]) # -> [0, 1, 2, 3]
こちらも負の数を入れると後ろから見ることができます。
a = [0, 1, 2, 3, 4, 5]
print(a[4:1:-1]) # -> [4, 3, 2]
print(a[5:0:-2]) # -> [5, 3, 1]
文字列でもリストと同様の使い方ができます。
s = "abcdefg"
print(s[0]) # -> a
print(s[3]) # -> b
print(s[1:4]) # -> bcd
print(s[::2]) # -> aceg
参考記事:
・https://note.nkmk.me/python-list-append-extend-insert/ （リスト）
・https://note.nkmk.me/python-slice-usage/ （スライス）
if文 （条件分岐）
a = 5
b = 7
if a < b:
print("a < b")
elif a > b:
print("a > b")
else:
print("a == b")
# 出力結果
# a < b
問題例: ABC147 A - Blackjack
参考記事:
・https://note.nkmk.me/python-if-elif-else/
for文 （繰り返し処理）
for i in range(5): # 0 ~ 4
print(i)
0
1
2
3
4
他にも引数を指定することができます。 range(5) は range(0, 5) の省略です。
for i in range(2, 10, 3): # 2 ~ 9 で、3つおき
print(i)
2
5
8
リストの中身を直接見ることもできます。
a = [3, 1, 4, 1, 5]
for i in a:
print(i)
3
1
4
1
5
問題例: ABC142 B - Roller Coaster
参考記事:
・https://note.nkmk.me/python-for-usage/
集合（set）
リストと違って要素に重複がなく順序もありません。
s = set()
s.add(1) # {1}
s.add(2) # {1, 2}
s.add(3) # {1, 2, 3}
s.add(1) # {1, 2, 3} # 重複しない
リストを集合化することで重複する要素を消すこともできます。
a = [3, 1, 4, 1, 5, 9, 2, 6, 5]
s = set(a)
print(s) # -> {1, 2, 3, 4, 5, 6, 9}
in 演算子で集合内に要素が含まれているかがわかります。
s = {1, 2, 3, 4, 5}
print(1 in s) # -> True
print(8 in s) # -> False
参考記事:
・https://note.nkmk.me/python-set/
辞書（dict）
キーと値がセットになったデータ型です。{key: value} の形で書きます。
d = {"a": 1, "b": 2}
for key in ["a", "b"]:
d[key] += 1
print(d) # -> {'a': 2, 'b': 3}
# 存在しない key を指定すると新しく作成される
d["c"] = 3
print(d) # -> {'a': 2, 'b': 3, 'c': 3}
辞書型は順序が保持されないので注意が必要です（Python 3.7 以降は保持されますが、AtCoder 上のバージョンは 3.4 です）。具体的には、以下のコードは実行するたびに出力される要素の順番が変わります。
d = {"a": 1, "b": 2, "c": 3}
print(d)
# -> {'b': 2, 'c': 3, 'a': 1} だったり {'a': 1, 'c': 3, 'b': 2} だったり
参考記事:
・https://note.nkmk.me/python-dict-create/
その他
組み込み関数
便利な関数がたくさん用意されているので、積極的に使っていきましょう。ここではよく使うものをいくつかを紹介します。
abs()
数値の絶対値が返ってきます。
a = 5
b = -3
print(abs(a)) # -> 5
print(abs(b)) # -> 3
exit()
プログラムを途中で終了させることができます。組み込み関数ではないですが、似たようなものなのでここで紹介します。
print(0)
print(1)
exit()
print(2)
print(3)
0
1
exit() の時点でプログラムが終了しているため、2 と 3 が出力されません。for 文、if 文と組み合わせて、条件を満たしたときだけそこで終了させたい場合によく使います。
# リスト a の中に整数 n との差の絶対値が 1 になるものがあるか判定する
n = 5
a = [3, 1, 4, 1, 5]
for i in a:
if abs(i - n) == 1:
print("YES")
exit()
print("NO")
YES
上のコードの場合、条件を満たすものがあればそこで終了して "YES" を出力し、満たすものがなければ "NO" が出力されます。
問題例: ABC131 A - Security
len()
リストの長さが返ってきます。文字列の長さもわかります。
a = [0, 1, 2, 3, 4]
print(len(a)) # -> 5
s = "abcdefg"
print(len(s)) # -> 7
int(), str()
int() で数値（整数）に、str() で文字列にそれぞれ変換できます。
s = "1234"
print(type(s)) # <class 'str'>
n = int(s)
print(type(n)) # <class 'int'>
t = str(n)
print(type(t)) # <class 'str'>
max()
数値を比較して最大値を返します。リストにも使えます。
print(max(1, 2, 3)) # -> 3
a = [3, 1, 4, 1, 5]
print(max(a)) # -> 5
min()
数値を比較して最小値を返します。リストにも使えます。
print(min(1, 2, 3)) # -> 1
a = [3, 1, 4, 1, 5]
print(min(a)) # -> 1
sorted()
リストのソートができます。
a = [3, 1, 4, 1, 5, 9, 2]
b = sorted(a)
print(b) # -> [1, 1, 2, 3, 4, 5, 9]
c = sorted(a, reverse=True)
print(c) # -> [9, 5, 4, 3, 2, 1, 1]
list.sort() でもソートできますが、元のリストが書き換えられてしまうため個人的には好みじゃなく使っていません。
a = [3, 1, 4, 1, 5, 9, 2]
a.sort()
print(a) # -> [1, 1, 2, 3, 4, 5, 9]
sum()
リストの要素の合計値が返ってきます。
a = [3, 1, 4, 1, 5]
print(sum(a)) # -> 14
リスト内包表記
リストを作って要素を追加していく際、普通なら以下のように for 文を使って書きます。
a = []
for i in range(5):
a.append(i ** 2)
print(a)
[0, 1, 4, 9, 16]
しかし、リスト内包表記を使うとこれを 1 行で書くことができます。
a = [i ** 2 for i in range(5)]
print(a)
[0, 1, 4, 9, 16]
参考記事:
・https://note.nkmk.me/python-list-comprehension/
PyPyのすすめ
Python は実行速度が非常に遅いので、アルゴリズムの計算量的には十分でも提出すると TLE してしまうことがあります。そういうときは PyPy を使ってみましょう。PyPy についての説明は割愛しますが、簡単に言うと Python のコードがそのまま使えて Python よりも高速です。PyPy を使う際の注意事項など詳しくは「Python 競技プログラミング高速化tips」に書いてあります。
読みやすいコードを書こう（PEP8）
Python には PEP8 というコーディング規約があります。競技プログラミングのコードは基本的に自分しか読まないので正直どんな書き方をしても良いのですが、読みやすいコードを書くとバグも減らせます。詳細は「[Pythonコーディング規約]PEP8を読み解く」に書いてあります。なお、PyCharm では PEP8 に違反していると警告を出して教えてくれます。
この記事を読み終えたら
- AtCoder Problems に AtCoder の全過去問が載っているので、これをひたすら解く
- 蟻本（競プロの攻略本）を読む
- ABC-C (300点) 以降の問題はアルゴリズムやデータ構造の知識がないと難しいものも出てきます。
- AtCoder 版！蟻本 (初級編) に、けんちょんさんが蟻本の類題として AtCoder 上の問題をまとめてくれています。
- 蟻本をPythonで (初級編) に蟻本のコードを Python で書き直したものを載せています。
- 実際にコンテストに出る
- AtCoder では毎週コンテストが開かれています。