tooh’s diary

半角全角、常体敬体が入り乱れるカオス

一か月のまとめ

こんばんわ。とーです。
二月からAtCoderに本腰入れて取り組み始め、一か月が経ちました。(とほぼ同時に50記事になったのでこの記事を書きました)
継続は力なりというのでしょうか、レートの伸びが目に見えて嬉しい限りです。

さて、この一か月(2/10~3/10)で、ABCのB,C問題を中心に198問解きました
f:id:saguh:20190312025823p:plain

そしてレートの推移がこちらになります
f:id:saguh:20190312025844p:plain


実は、この一年間で過去に競プロを始めようと思ったことが二回ほどあったのですが
一回目:四月初め。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で求まる

C - Monsters Battle Royale


☆☆☆素数素因数分解、エラトステネスの篩、階乗の約数)

n以下の素数を列挙するアルゴリズム

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

C - Factors of Factorial

☆☆☆全探索(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

C - 柱柱柱柱柱
C - Strange Bank


☆☆二分探索

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 - 列

幅優先探索

C - 幅優先探索


深さ優先探索

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))

C - 経路





操作編

☆☆☆スタック、キュー

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