こんばんわ。とーです。
二月からAtCoderに本腰入れて取り組み始め、一か月が経ちました。（とほぼ同時に50記事になったのでこの記事を書きました）
継続は力なりというのでしょうか、レートの伸びが目に見えて嬉しい限りです。
さて、この一か月(2/10~3/10)で、ABCのB,C問題を中心に198問解きました
そしてレートの推移がこちらになります
実は、この一年間で過去に競プロを始めようと思ったことが二回ほどあったのですが
一回目:四月初め。pythonの初心者向けの本を買ってやろうとするも、別にそれは競プロ用でもなんでもなく、標準入力を受け取るところでinf年時間を溶かし3日で断念
二回目:九月初め。夏の成績も出て八月はブルーになっていた気持ちも落ち着いてさて始めようかと思ったら、案外夏休みが短くて二週間しかできず、Aを埋めてBを1/3くらい解くので精一杯
みたいな状況でした
この一か月で、B問題で入力や単純な操作のメソッドを学び、C問題でアルゴリズムの典型例を学習してきました
A,B問題を全部解けば、基本的な操作は理解できると思うので割愛します
C問題,D問題を通して学んだアルゴリズムや操作、教育的な問題をまとめたいと思います
☆☆☆が「C解けるなら知ってて当然」、☆☆が「Cの中堅レベルで使える」、☆が「Dで威力を発揮する」くらいの大雑把な感じの分類です
☆☆☆累積和（いもす法）
二週間くらい前は扱いに一苦労でしたが、今は結構扱えるようになってきて使い勝手が良いです
累積和の強みとして、一回作ってしまえば部分区間の和（や積）をO(1)で求められるというところです
計算が間に合わねえ！って問題も累積和で解決するタイプが（特にCだと）多いです
いもす法はその派生です これは累積和より早くリストが作れます
「被覆区間を求める」タイプの問題で力を発揮します
C - ハイスコア
C - 総和
C - Together
D - Candy Distribution
A - Zero-Sum Ranges
☆☆☆最小公倍数、最大公約数（ユークリッドの互除法）
ユークリッドの互除法で最大公約数を求めるアルゴリズム
def gcd(x,y): #x >= y while y != 0: k = x x = y y = k%y return x
※最小公倍数を求めるときは、最小公倍数を求めたい数の組をa,bとし、最小公倍数をL、最大公約数をGとすれば、a*b == L*Gという関係が成り立つため、L = a*b/Gで求まる
def primes(n): ass = [] is_prime = [True] * (n + 1) is_prime[0] = False is_prime[1] = False for i in range(2, int(n**0.5) + 1): if not is_prime[i]: continue for j in range(i * 2, n + 1, i): is_prime[j] = False for i in range(len(is_prime)): if is_prime[i]: ass.append(i) return ass
☆☆☆全探索（10進法をn進法に直す）
効率的なやり方が思いつかない場合、全探索で求めてしまった方が安全な場合が多いです
計算量（全部で何通りあるかでよい）を確認し、10**6までだったら余裕で間に合うので、どんどんパソコン君に全探索を丸投げしましょう
10進法をn進法に直すアルゴリズム（NはN桁まで0埋めします）
def Base_10_to_n(X,n): if (int(X/n)): return Base_10_to_n(int(X/n),n)+str(X%n) return str(X%n) for X in range(n**N): STR = Base_10_to_n(X,n).zfill(N)
D - Patisserie ABC
C - All Green
C - 755
C - Synthetic Kadomatsu
D - Simple Knapsack
☆☆☆漸化式によるDP
☆☆二分探索
D - Lazy Faith
C - Snuke Festival
☆☆ワーシャルフロイド法、ダイクストラ法
ワーシャルフロイド法
from scipy.sparse.csgraph import floyd_warshall #呪文を唱える n,m = map(int,input().split()) #nは頂点の数、mは辺の数 d = [[float("inf")]*n for i in range(n)] #ここに辺の重さを格納 L = [] for i in range(n): d[i][i] = 0 #同じ頂点間は重さ0 for i in range(m): a,b,l = map(int,input().split()) #a,bは頂点(1インデックス)、lは重さ if a == 1: #今回は始点が頂点1の辺は繋がない L.append([a,b,l]) else: d[a-1][b-1] = l #距離を格納(双方向) d[b-1][a-1] = l d = floyd_warshall(d) #最短距離を求める
import heapq def dijkstra_heap(s): #始点sから各頂点への最短距離 d = [float("inf")] * n #ここに始点sから各点への最短距離を格納 used = [True] * n #Trueは「最短距離が未確定」を意味する d[s] = 0 #始点sは当然距離0 used[s] = False #d[s]=0と確定したのでFalseに edgelist = [] #全部調べつくしたとき、このリストは空になる for e in edge[s]: #edgelistに[重み,行き先]を入れる heapq.heappush(edgelist,e) while len(edgelist): minedge = heapq.heappop(edgelist) #まだ使われてない頂点の中から最小の距離（重み）のものを探す if not used[minedge[1]]: #取り出した[重み,行き先]の「行き先」が、最短距離確定済み頂点なら continue #引き返す（距離が無駄に増える）だけなので使わない v = minedge[1] #行き先 d[v] = minedge[0] #距離（重み） used[v] = False #「今」見た頂点はFalseにする for e in edge[v]: #行き先から出る道[重み,行き先]の要素eに対して if used[e[1]]: #行き先が「最短距離未確定」ならば heapq.heappush(edgelist,[e[0]+d[v],e[1]]) #edgelistにソートしてぶち込む return d #調べつくしたら、最短経路の入ったリストdを返す n,w = map(int,input().split()) #nは頂点の数、wは辺の数を表す edge = [[] for i in range(n)] #edge[i]は、iから出る道の[重み,行先]の配列 for i in range(w): x,y,z = map(int,input().split()) #x,yは頂点の番号、zは重み（距離） edge[x].append([z,y]) edge[y].append([z,x]) print(dijkstra_heap(0)) #番号0の頂点からの最短経路を求める
C - 友達の友達
C - 正直者の高橋くん
C - Blue Bird
B - リモコン
☆☆Union Find（シンプル・サイズ付き）
シンプルなUnion Find
N,Q = map(int,input().split()) #N個の頂点（0インデックス）、Q個のクエリ L = [] for i in range(Q): L.append(list(map(int,input().split()))) par = [] rank = [] for i in range(N): par.append(i) rank.append(0) def find(x,par): if par[x] == x: return x else: return find(par[x],par) def unite(x,y,par,rank): x = find(x,par) y = find(y,par) if x != y: if rank[x] < rank[y]: par[x] = y else: par[y] = x if rank[x] == rank[y]: rank[x] += 1 def same(x,y,par): return find(x,par) == find(y,par)
サイズ付きUnion Find
N,M = map(int,input().split()) L = [] for i in range(M): L.append(list(map(int,input().split()))) L.reverse() par = [] rank = [0]*N size = [1]*N for i in range(N): par.append(i) def find(x,par): if x == par[x]: return x else: return find(par[x],par) def unite(x,y,par,rank,size): x = find(x,par) y = find(y,par) if x != y: if rank[x] < rank[y]: par[x] = y size[y] += size[x] else: par[y] = x size[x] += size[y] if rank[x] == rank[y]: rank[x] += 1 def same(x,y,par): return find(x,par) == find(y,par)
B: Union Find - AtCoder Typical Contest 001 | AtCoder
D - Decayed Bridges
☆しゃくとり法
C - One-stroke Path
D - Fennec VS. Snuke
☆逆元
nCk = n!/(k!*(n-k)!)を10**9+7で割ったあまりを制限時間内に求めるアルゴリズム
import math n = int(input()) k = int(input()) a = (math.factorial(n))%(10**9+7) b = (math.factorial(k)%(10**9+7)) c = (math.factorial(n-k)%(10**9+7)) print((a*pow(b*c,10**9+5,10**9+7))%(10**9+7))
操作編
☆☆☆スタック、キュー
from collections import deque L = deque([1,2,3,4]) a = L.popleft() a == 1 L.append(5) L == deque([2,3,4,5])
☆☆リストのn番目でソート
L = sorted(L, key = lambda x:x[n]) #n番目（0インデックス）でソート
☆☆リストのコピー
L = [1,2,3,4,5] M = copy.deepcopy(L) M == [1,2,3,4,5]
☆小数点以下の四捨五入
fは四捨五入したい数digitは小数第何位で四捨五入したいかを表す
f,digit = map(float,input().split()) def my_round(f, digit): p = 10**digit return (f*p*2+1)//2/p
