3次元の入れ子を作りたいときに参照渡しにならないようにつくる方法。dp[i][j][k] 1≦i≦x 1≦j≦y 1≦k≦z として、 dp = [[[0]*(z+1) for _ in range(y+1)] for __ in range(x+1)] ABC281 D - Max Multiple などで使用。

・x**yを使わないといけないのに、yの制約が「0≦y≦10**9」とかのとき。①"aのn乗"の計算 def reppow(a,n): if n == 0: return 1 if n == 1: return a if n%2 == 1: ret = reppow(a,n-1)*a return ret ret = reppow(a,n//2) ret = ret*ret return ret このまま…

最小全域木問題に対してのプリム法による解法 AOJ ALDS1_12_A Minimum Spanning Tree・まずスタートの点を決める ・「既に到達した点」から「まだ到達していない点」へ行く辺の中で一番コストの低い辺を探す ・その辺を採用し、辺の先の点は「既に到達した点…

最小全域木問題に対してのクラスカル法による解法 AOJ GRL 2_A Minimum Spanning Tree・重みを持つすべての辺をコスト順に並び替える ・コストの低い辺から順に採用するか検討していく ・その辺を採用すると「閉路」ができてしまうなら採用しない ・「閉路」…

unionfindのお約束部分 #n = int(input()) par = [-1]*n siz = [1]*n def root(x): if par[x] == -1: return x else: par[x] = root(par[x]) return par[x] def size(x): return siz[root(x)] def unite(x,y): x = root(x) y = root(y) if x == y: return Fa…

エラトステネスのふるい・任意のn以下の素数のリストをO(nloglogn)（らしい）で得る。 def prime(x): x = int(x) if x < 2: return [] P = [True]*(x+1) P[0],P[1] = False,False res = [] for i in range(x+1): if P[i] == False: continue else: res.appen…