競技プログラミングPythonまとめ
久しぶりの記事になってしまいました。AtCoderの過去問を解きながらPythonを勉強しています。多少の知識が纏まってきたので、ここを棚卸しに活用します。ほぼ単なるメモです。
いつもお世話になっている参照先
Python基礎文法の整理
変数名 = 変数
関数() # ()は関数が処理する内容。データ。
[] # コンテナ型。複数のデータを収めてるもの。
変数名.関数(コンテナ名[]) とかも出来る。入力
文字列を一つだけ受け取る
a = input()
空白を空けて複数の文字列を受け取る
a, b = input().split()
数値を一つだけ受け取る
n = int(input())
数値を複数受け取る 「A B」のように空白で区切る入力のとき
a, b = map(int, input().split())
リスト入力 「a1 a2 a3 ...」のように入力数が決まっていない場合
s = list(map(int, input().split()))
リスト入力の別解。内包表記は何かと便利なので慣れるべき。
s = [int(i) for i in input().split()]
複数入力を受け取る、かつ入力行数指定のとき（例はn=行数）
n = int(input())
p = [int(input()) for _ in range(n)]
複数入力を受け取る（行列の形）
n, m = map(int,input().split())
p = [list(map(int,input().split())) for i in range(m)]
print(type(P), P)
2 3
1 32
2 63
1 12
[[1, 32], [2, 63], [1, 12]]
空の繰り返しを与えて行列を作る場合（ABC050B）
n = int(input())
t = list(map(int, input().split()))
m = int(input())
for _ in range(m):
p, x = map(int, input().split())
print(sum(t)-t[p-1]+x)
5
7 2 3 8 5
3
4 2
1 7
4 13
19
25
30出力
基本。{}に対応するformat()を出力。 ※3.6以降はf"{}"で書いた方が楽。
print("{} {}".format(a+b+c, s))
0.3644 小数点第4位に丸めることもできる。
print("{:.4f}".format(a))
左詰め python---------
print("python".ljust(15,'-'))
中央寄せ -----python----
print("python".center(15,'-'))
右詰め ---------python
print("python".rjust(15,'-'))
10桁ゼロ埋め 0000000029
print(str(29).rjust(10,'0'))
リストのアンパック出力
print(*c)
二次元リストで間を詰めたもの
for i in [['#','.','#'],['#','#','#']]:print(*i, sep='')
#.#
###よくある処理
＝ よくある処理（三項演算子）＝ print(三項演算子)みたいに一行で書ける。
条件式が真のときに評価される式 if 条件式 else 条件式が偽のときに評価される式
条件式が真のときに返す値 if 条件式 else 条件式が偽のときに返す値
＝ よくある処理（リスト） ＝
len(lst) リストの全要素数を取得
lst.count('a') リストの特定要素の出現回数を取得
lst.index('a') リストのインデックス取得
1 in lst リストに数値の1がいるか否か
リストに数値を入力してそれを計算したいとき。
リストをソートして変数へアンパックし代入。便利。
a, b, c = list(map(int, input().split()))
s = a, b, c
l = sorted(s)
x, y, z = l
リストに含まれる全ての値が条件に合致するか。
allをanyに変えるといずれかの要素が条件に合致するか、に変更できる。
lst = [0, 1, 2, 3, 4]
print(all([i > 2 for i in lst]))
# リストの各要素に特定の条件（処理）を与えたい場合
a = [int(x) for x in input().split()]
for x in a:
if
break
else # breakするならelse不要
print
＝ よくある処理（文字列） ＝
eval('1 + 2') 文字列を式として実行
s.replace(' ', '-') 文字列の置換
''.join(lst) リストの全要素の結合
'abc123def'[:] # すべての文字列が取れる
'abc123def'[-1:] # 終端文字がとれる
'abc123def'[:-1] # 最後の1文字以外のものがとれる。
'abc123def'[::-1] # 文字が逆転する
＝ よくある処理（数値） ＝
// 小数点切り捨ての割り算
sum(lst) リストに含まれる要素の合計
# 文字列不可,[:-1]とすれば最後の値を除きsum
sum(int(i) for i in lst) 上述と等価
abs(x) 絶対値(0からの距離)の取得内包表記
内包表記でリストを作成するとき。
変数名＝[式 for 任意の変数名 in イテラブルオブジェクト if 条件式]
入力数nまでの、3と5と15の倍数を「除く」リストを生成の例
lst = [i for i in range(1, n+1) if i % 3 != 0 and i % 5 != 0]
入力数nまでの、3と5と15の倍数「だけ」のリストを生成の例
lst = [i for i in range(1, n+1) if i % 3 == 0 or i % 5 == 0]
条件式が真のときに評価される式 if 条件式 else 条件式が偽のときに評価される式
l = [i * 10 if i % 2 == 0 else i for i in range(10)]
# [0, 1, 20, 3, 40, 5, 60, 7, 80, 9]
二次元配列入力
s = [list(map(int,list(input()))) for i in range(h)]
九九を一つのリストに入力
s = [x*y for x in range(1, 10) for y in range(1, 10)]
[1, 2, 3, 4, 5, 6, 7, 8, 9,
2, 4, 6, 8, 10, 12, 14, 16, 18,
3, 6, 9, 12, 15, 18, 21, 24, 27,
4, 8, 12, 16, 20, 24, 28, 32, 36,
5, 10, 15, 20, 25, 30, 35, 40, 45,
6, 12, 18, 24, 30, 36, 42, 48, 54,
7, 14, 21, 28, 35, 42, 49, 56, 63,
8, 16, 24, 32, 40, 48, 56, 64, 72,
9, 18, 27, 36, 45, 54, 63, 72, 81]
九九を二次元配列で入力
s = [[x*y for x in range(1, 10)] for y in range(1, 10)]
[[1, 2, 3, 4, 5, 6, 7, 8, 9],
[2, 4, 6, 8, 10, 12, 14, 16, 18],
[3, 6, 9, 12, 15, 18, 21, 24, 27],
[4, 8, 12, 16, 20, 24, 28, 32, 36],
[5, 10, 15, 20, 25, 30, 35, 40, 45],
[6, 12, 18, 24, 30, 36, 42, 48, 54],
[7, 14, 21, 28, 35, 42, 49, 56, 63],
[8, 16, 24, 32, 40, 48, 56, 64, 72],
[9, 18, 27, 36, 45, 54, 63, 72, 81]]全探索の基礎
ABC136B 範囲条件に合致する数値をカウント
n = int(input())
ans = 0
for i in range(1, n+1):
if 0 < i < 10 or 99 < i < 1000 or 9999 < i < 100000:
ans += 1
print(ans)
ABC051B 複数の要素x，y，zを組み合わせ、条件sに合致すればカウント+1
k, s = map(int, input().split())
ans = 0
for x in range(k+1):
for y in range(k+1):
for z in range(k+1):
if x+y+z == s:
ans += 1
print(ans)
ABC051B（計算量を減らした解法）
k, s = map(int, input().split())
ans = 0
for x in range(k+1):
for y in range(k+1):
z = s-x-y
if 0 <= z <= k and x+y+z == s:
ans += 1
print(ans)
ABC130B カウント要素2つをコントロールする事例
N, X = map(int, input().split())
L = list(map(int, input().split()))
distance = 0
cnt = 1
for i in range(N):
distance += L[i]
if distance <= X:
cnt += 1
print(cnt)itertoolsまとめ
順列（重複を含む、異なる複数の要素の組み合わせ）
import itertools
lst = ['a', 'b', 'c', 'd']
print(list(itertools.permutations(lst, 2)))
[('a', 'b'), ('a', 'c'), ('a', 'd'),
('b', 'a'), ('b', 'c'), ('b', 'd'),
('c', 'a'), ('c', 'b'), ('c', 'd'),
('d', 'a'), ('d', 'b'), ('d', 'c')]
組み合わせ（重複を除く、異なる複数の要素の組み合わせ）
import itertools
lst = ['a', 'b', 'c', 'd']
print(list(itertools.combinations(lst, 2)))
[('a', 'b'), ('a', 'c'), ('a', 'd'),
('b', 'c'), ('b', 'd'), ('c', 'd')]
重複順列（1つ(同一内容)のリストからマトリクス状に組み合わせを生成）
import itertools
lst = ['a', 'b', 'c', 'd']
print(list(itertools.product(lst, repeat=2)))
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'),
('b', 'a'), ('b', 'b'), ('b', 'c'), ('b', 'd'),
('c', 'a'), ('c', 'b'), ('c', 'c'), ('c', 'd'),
('d', 'a'), ('d', 'b'), ('d', 'c'), ('d', 'd')]
直積（デカルト積）（2つ(異なる内容)のリストからマトリクス状に組み合わせを生成）
import itertools
lst = ['a', 'b', 'c', 'd']
num = [1, 2, 3, 4]
print(list(itertools.product(lst, num)))
[('a', 1), ('a', 2), ('a', 3), ('a', 4),
('b', 1), ('b', 2), ('b', 3), ('b', 4),
('c', 1), ('c', 2), ('c', 3), ('c', 4),
('d', 1), ('d', 2), ('d', 3), ('d', 4)]
計算事例① 順列の前者後者を全て足したもの ※アンパックしてるから
import itertools
num = [1, 2, 3, 4]
data = list(itertools.permutations(num, 2))
print([sum(x) for x in zip(*data)])
# [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
[30, 30]
計算事例② 順列をそれぞれ足したもの
import itertools
num = [1, 2, 3, 4]
data = list(itertools.permutations(num, 2))
print([sum(x) for x in (data)])
[3, 4, 5, 3, 5, 6, 4, 5, 7, 5, 6, 7]
計算事例③ 順列を全部足したもの
import itertools
num = [1, 2, 3, 4]
data = list(itertools.permutations(num, 2))
print(sum([sum(x) for x in (data)]))
# 60高速化のおまじない
とりあえずPypyで提出すれば何とかなる（かもしれない）。
import sys
input = sys.stdin.readline # コードの最初に追加。2〜10倍も違うらしい。雑記
A問題はifで場合分けを全て書けば解ける。
B問題はforで解く。「どのような解法があるか」を考えるより「どのようにforを回すか」で考えた方が答えに近づくように思う。
C問題もforありきで「全通り」を調べ上げるのが基本。ただし計算量の制約に応じて記述を工夫しないとTLE。
D問題はこれから。
//end