#はじめに
1年前に機械学習をやりたい、それならpythonだ！ってなったものの、別に情報系卒でもないし、プログラミングをやった経験もないので始めようと思いながら何も動かすことができませんでした。
「何か、なにかプログラミングやってみたい、でも何をやればいいの?」ってときに見つけたのが競技プログラミングです。これをやることで、いろんなアルゴリズムの考え方や、プログラミングでできることをいろいろと学べました。そして、普通に競技プログラミングにハマって今日まで続けています。
そんなところで競技プログラミングでよく使う技術のメモと、もっと使ってほしい技術の紹介です。もっとpython勢増えてほしい。特に短い、早い、わかりやすいコードの人が増えてほしい。いつも短い順、早い順で探して参考にしてるので。
※githubにjupyterのコードをアップしました。
#基本入力、出力、format関数
他の人が色々書いているのでさっくりです。
入力はかならず使うのでスペルミスしないように辞書登録すると良いと思います。
format関数は覚えておいたほうが良いところがたまにある。%dとかでも良いけどformatの方がよりpython的かな。
追記：最近f-stringが便利です。formatよりも短くかけるのでおすすめ
0埋めは最近使いました。あと九九表をきれいに出すときに使いますね。
最後のはかなり便利です。print(' ',join(str,c)))よりだいぶ楽ですよね。
n=int(input()) #数値入力 「N」だけの入力のとき
a,b=map(int, input().split()) #複数数値入力 「A B」みたいなスペース空いた入力のとき
c=list(map(int, input().split())) #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
s=[list(map(int,list(input()))) for i in range(h)] # 二次元配列入力 二次元マップみたいな入力のとき
a=100
b=0.987654321
print('{0:06d}-{1:6f}'.format(a,b)) # 0埋めのときの出力
000100-0.987654
#f-string
a=123
print(f'test {a} desu')
print(*c) #リスト出力
for i in [['#','.','#'],['#','#','#']]:print(*i, sep='') #二次元リストで間を詰めたもの
#.#
###
#初期化、内包表記
初期化はいつものやり方を作っといたほうが良いです。特に2次元リスト
最初はコピーとかも混乱しますよね。「python 参照渡し」とかで調べてみると良いと思います。
内包表記は覚えておくと何かと便利です。
a=[0]*5
b=a #良くない配列のコピー
b2=a[:] #1次元のときはコピーはこれで良い
a[1]=3
print('b:{}, b2:{}'.format(b,b2)) #b:[0, 3, 0, 0, 0], b2:[0, 0, 0, 0, 0]
import copy
a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
b=copy.deepcopy(a) #2次元配列はこうコピーする
#内包表記奇数のみ
odd=[i for i in range(100) if i%2==1] #[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
#素数、2重ループ、2分探索、
ソートは基本できたらする感じで。しないよりはしたほうが良い。ラムダこれ以外の使いみちあまりしたこと無い・・・
素数はこれがかなり早かったです。10**5で100msくらい。
2重ループのこの抜け方はちょいちょい忘れるのでメモ。elseのとこは、初めにans='-1 -1 -1'しておいてifのところをans=(i,j,n-i-j)とすれば最後に普通にprint(ans)で済みます。
2分探索は自分でも組むことはできますが、モジュール使ったほうが便利です。ミス無いですし。
#ソート
w=[[1, 2], [2, 6] , [3, 6], [4, 5], [5, 7]]
w.sort()
w.sort(key=lambda x:x[1],reverse=True) #二個目の要素で降順並び替え
#素数リスト
n = 100
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
primes.difference_update(range(i*2, n+1, i))
primes=list(primes)
#二重ループ 正解を見つけたらループを止める
n,y=1000, 1234000
for i in range(n+1):
for j in range(n-i+1):
if y-10000*i-5000*j==1000*(n-i-j):
print(i, j, n-i-j)
break
else:
continue
break
else:
print('-1 -1 -1')
#二部探索
import bisect
a = [1, 2, 3, 5, 6, 7, 8, 9]
b=bisect.bisect_left(a, 8)
最大公約数、組み合わせ、ビット演算、n進数
最大公約数もモジュールで出しましょう。バージョンの関係でmathじゃなくてfractionsです。
itertoolは全探索（ビット演算）との関係でproductをよく使います。evalとのセットも多い。
集計も頻出。Counter便利です。
n進数はできておくと便利です。n進数に直せという直接的なもの以外でも「nのx乗のみ使える」みたいな問題で使うことはあります。
#最大公約数、最小公倍数
import fractions
a,b=map(int, input().split())
f=fractions.gcd(a,b)
f2=a*b//f
print(f,f2)
#combinations、組み合わせ、順列
from itertools import permutations, combinations,combinations_with_replacement,product
a=['a','b','C']
print(list(permutations(a)))
print(list(combinations(a,2)))
print(list(combinations_with_replacement(a,3)))
#ビット演算、式を計算
a=list(product(['+','-'],repeat=3))
s=['5', '5', '3', '4']
for i in a:
ans=s[0]+i[0]+s[1]+i[1]+s[2]+i[2]+s[3]
if eval(ans)==7:
print(ans+'=7')
break
#集計
from collections import Counter
a=[2,2,2,3,4,3,1,2,1,3,1,2,1,2,2,1,2,1]
a=Counter(a)
for i in a.most_common(3):print(i)
#n進数
n=64
k=-3
bi=''
while n!=0:
bi+=str(n%abs(k))
if k<0:n=-(-n//k)
else:n=n//k
print(bi[::-1])
#最短経路、深さ探索、幅探索
周辺埋めは探索のときとかはやっておくと便利です。
最短経路はこれが美しいかはわかりませんが、毎回これをもとに書いてます。
深さ探索、幅探索ももっと良い書きかたありますが、とりあえず自分はこれを使ってます。
#最短経路
ys,xs=2,2
yg,xg=4,5
a=['########', '#......#', '#.######', '#..#...#', '#..##..#', '##.....#', '########']
n=[(ys-1,xs-1)]
route={n[0]:0}
p=[[1,0],[0,1],[-1,0],[0,-1]]
count=1
while route.get((yg-1,xg-1),0)==0 and count != 10000:
n2=[]
for i in n:
for j in p:
np=(i[0]+j[0],i[1]+j[1])
if a[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
n2.append(np)
route[np]=count
n=n2
count+=1
print(n,route)
#深さ探索
q=[{1, 3}, {1, 4}, {9, 5}, {5, 2}, {6, 5},{3,5},{8,9},{7,9}]
count=0
while count!=10000:
a=q.pop()
for j in q:
if len(j&a) != 0:
j |=a
count=0
break
else:q=[a]+q
if count>len(q): break
count+=1
print(count,q)
#幅優先探索
n=7
pt=[[1, 2, 3], [0], [5, 0], [6, 0], [6], [2], [3, 4]]
def bfs(v):
d=[-1]*n
d[v]=0
q=[v]
c=1
while q:
q1=[]
for i in q:
for j in pt[i]:
if d[j]==-1:
d[j]=c
q1.append(j)
q=q1
c+=1
print(d,q)
return d
print(bfs(0))
アルファベット列挙、素因数分解、文字列変換、しゃくとり法
アルファベット列挙は直打ちでもいいけどこれが確実か。ordとかchrを覚えておくとためになるときがあるかもと。
素因数分解はよく使うのでやり方を記憶しておく。
文字列変換は基本はreplaceだけど、複数文字のやり方も覚えておきたい。
しゃくとり法も考え方が重要。
#アルファベット
al=[chr(ord('a') + i) for i in range(26)]
print(al)
#素因数分解
pf={}
m=341555136
for i in range(2,int(m**0.5)+1):
while m%i==0:
pf[i]=pf.get(i,0)+1
m//=i
if m>1:pf[m]=1
print(pf)
#複数の文字列を変換
S='54IZSB'
S = S.translate(str.maketrans("ODIZSB","001258"))
print(S)
#しゃくとり
n=int(input())
a=list(map(int, input().split()))
count=0
right=0
m=dict()
for left in range(n):
while right<n and m.get(a[right],0)==0:
m[a[right]]=m.get(a[right],0)+1
right+=1
count=max(count,right-left)
m[a[left]]=m.get(a[left],1)-1
print(count)
累積和、動的計画法
累積和は計算量を減らす方法として基本。forの中にsumを入れたくなったらこれを疑う。疑わないとやられる。
動的計画法は水色以上だと基本で必要になるイメージ。名前でイメージしにくいけど、数式作って順に解いてくという数学的帰納法チックなやつ。
# 累積和
a=list(range(1,30))
a2=[0]
for i in a:a2.append(a2[-1]+i)
#DP1
n=6
w=8
weight=[2,1,3,2,1,5]
value=[3,2,6,1,3,85]
dp=[[0 for i in range(w+1)] for j in range(n+1)]
for i in range(n):
for j in range(w+1):
if j>=weight[i] : dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])
else: dp[i+1][j]=dp[i][j]
print(dp[:i+2])
print(dp[n][w])
numpy,scipyについて
atcoderではnumpyやscipyが使えますので、覚えておいたほうが得な場合は多いです。
forだと間に合わないところも間に合ったりします。
コードがスッキリしてかっこよくなります。numpy、scipy使いましょう!
#周辺埋め
h,w=map(int, input().split())
s = ["."*(w+2)]+["."+input()+"." for i in range(h)]+["."*(w+2)]
print(s)
import numpy as np
s=np.array(s)
s=s[::-1,:].T #90度回転
s=s[::-1,::-1] #180度回転
s[i:i+2,j:j+2]=5 #指定の2x2を書き換え
np.sum(s[:3,:2]=='5') #指定の数を数える。
#各座標の点をある点に集める時のマンハッタン距離コストの導出、日経コン本戦Cなど。
a=[2, 5, 3, 9, 5, 6, 9]
F=lambda x:np.int64(x).cumsum().cumsum()[:-1]
print(F([0]+a)+F([0]+a[::-1])[::-1]) # [142 107 82 63 62 71 92]
#組み合わせの数 ※すいません。atcoderだとREでした。
from scipy.special import comb
comb(10**5, 100, exact=True)%(10**9+7)
#組み合わせのmod対応
とりあえずこれを置いておきますが、powerのところは、pow(x,mod-2,mod)で十分という話があります。
def framod(n, mod, a=1):
for i in range(1,n+1):
a=a * i % mod
return a
def power(n, r, mod):
if r == 0: return 1
if r%2 == 0:
return power(n*n % mod, r//2, mod) % mod
if r%2 == 1:
return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
a=framod(n, mod)
b=framod(k, mod)
c=framod(n-k, mod)
return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod
print(comb(10**5,5000,10**9+7))
print(comb(100000, 50000,10**9+7))
#グラフ、最短経路など
グラフはまだまだ詳しくないですが、
すべての2点間の最短距離を求める：ワーシャルフロイト法
任意の2点間の距離：ベルマンフォード法
負のループがない2点間距離：ダイクストラ法
という認識です。
#ワーシャルフロイト法
n=int(input())
#c=[[random.randint(1, 10) for i in range(n)] for i in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
c[i][j]=min(c[i][j],c[i][k]+c[k][j])
for i in c:
print(i)
from scipy.sparse.csgraph import floyd_warshall
cost=floyd_warshall(c)
#ベルマンフォード法
def BF(p,n,s):
inf=float("inf")
d=[inf for i in range(n)]
d[s-1]=0
for i in range(n+1):
for e in p:
if e[0]!=inf and d[e[1]-1]>d[e[0]-1]+e[2]:
d[e[1]-1] = d[e[0]-1] + e[2]
if i==n-1:t=d[-1]
if i==n and t!=d[-1]:
return [0,'inf']
return list(map(lambda x:-x, d))
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
a=[[x,y,-z] for x,y,z in a]
print(BF(a, n, 1)[-1])
# ダイクストラ法
mp2=[[2, 4, 2], [3, 4, 5], [3, 2, 1], [1, 3, 2], [2, 0, 8], [0, 2, 8], [1, 2, 4], [0, 1, 3]]
from heapq import heappop, heappush
inf=float('inf')
d=[inf for i in range(5)]
d[0]=0
prev=[None]*5
p=dict()
for i,j,k in mp2: p[i]=p.get(i,[])+[(j,k)]
print(p)
q=[]
heappush(q,(d[0],0))
while q:
print(q,d,prev)
du, u = heappop(q)
if d[u]<du: continue
for v,weight in p.get(u,[]):
alt=du+weight
if d[v]>alt:
d[v]=alt
prev[v]=u
heappush(q, (alt,v))
p=[4]
while prev[p[-1]]!=None: p.append(prev[p[-1]])
print('最短経路',*p[::-1])
print('最短距離',d)
メモ化再帰
pythonの関数はグローバル変数を書き換えないと言われてますが、リストの中は変えてくんですね。それを利用してメモ化再帰作ってみました。
@lru_cacheで十分とも言えますが。やりたかったので。
再帰上限はそのままだと1000回なので、sysで変更しておきます。
#同じことをこれを関数前に置いとくだけでもできます。
#from functools import lru_cache
#@lru_cache(maxsize=1000)
fiv=[1,1]
def f(n):
if n<len(fiv):return fiv[n]
ans=(f(n-2)+f(n-1))%(10**9+7)
fiv.append(ans)
return ans
import sys
sys.setrecursionlimit(10000)
print(f(6000))
print(len(fiv))
Union find
Union find はたまに出てきますね。これ一から書いてると無理なんで誰かブログで書いてる実装を準備しておきましょう。
自分はこちらの方の実装を使わせていただいています。
これ使うだけで解けるみたいなのが400でちょいちょい出ます。
どれとどれが仲間なのかなって問題はけっこうこれが使えます。
ちなみにこの実装は最後に全部find入れとかないとつながらないので注意。
どうつながらないのかは最後のforループをコメントアウトして試してみてください。
class UnionFind(object):
def __init__(self, n=1):
self.par = [i for i in range(n)]
self.rank = [0 for _ in range(n)]
def find(self, x):
if self.par[x] == x:
return x
else:
self.par[x] = self.find(self.par[x])
return self.par[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x != y:
if self.rank[x] < self.rank[y]:
x, y = y, x
if self.rank[x] == self.rank[y]:
self.rank[x] += 1
self.par[y] = x
def is_same(self, x, y):
return self.find(x) == self.find(y)
n,m=5, 3 #map(int, input().split()) n:ノードの数, m:パスの数
uf1=UnionFind(n)
for i,j in [[1, 2],[5, 4],[4, 1]]: # range(m):
a,b=i,j #map(int, input().split()) #a,b:つながっている辺
uf1.union(a-1,b-1)
for i in range(n):uf1.find(i) # 一周findすることによって接続漏れをなくす。
print(uf1.par) #[4, 4, 2, 4, 4]
環境について
あまり詳しくないですが、初心者はAnaconda入れてそれに入っているjupyter notebookがおすすめです。もしくはGoogle Colaboratoryなら環境構築もほぼなしで行けます。
jupyterは動かしたプログラムの変数に何が入ったのかを確認しやすくて良いです。
まとめ
こんなところです。筆者のレベルが上昇したら追加予定。