More than 3 years have passed since last update.

個人的なアルゴリズム解説(グラフなど)

Last updated at 2021-09-09Posted at 2021-08-17

これはAtCoderで緑コーダーになるために自分が学んだアルゴリズムなどの備忘録です。
他の人のコードを参考にしている部分もあります。
言語はPythonを使っています。

グラフ

グラフ(wikipedia)
グラフについて解説していく。
まずはデータの取り込み方から。

データの取り込み

typical90 078-EasyGraphProblem

N,M=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)
ans=0
for i in range(1,N+1):
    count=0
    for t in G[i]:
        if t<i:
            count+=1
    if count==1:
        ans+=1
print(ans)

上は筆者の書いたコード。配列の0番目は使っていない。
下のコードではグラフの構造を作らずに直接数えている。

n, m = map(int,input().split())
ans = [0] * n
for i in range(m):
    a, b = map(int,input().split())
    if a < b:
        ans[b - 1] += 1
    else:
        ans[a - 1] += 1

# 自分より小さい頂点が１つしかないものをカウントする
print(ans.count(1))

DFS(深さ優先探索)

dfs(wikipedia)
まずはグラフではない問題をみる。

AHC005 A-Patrolling

この問題の趣旨はDFSではないが、ヴィジュアライザがわかりやすいのでこれを取り上げる。

import sys
import time
sys.setrecursionlimit(10**6)
N,si,sj=map(int,input().split())
c=[]
for _ in range(N):
    c+=[list(input())]
time0=time.time()

temp=[[False for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(N):
        if c[i][j]=='#':
            temp[i][j]=True
s=''
def dfs(i,j):
    global s,temp
    temp[i][j]=True
    if i!=0 and temp[i-1][j]==False:
        s+='U'
        dfs(i-1,j)
        s+='D'
    if i!=N-1 and temp[i+1][j]==False:
        s+='D'
        dfs(i+1,j)
        s+='U'
    if j!=0 and temp[i][j-1]==False:
        s+='L'
        dfs(i,j-1)
        s+='R'
    if j!=N-1 and temp[i][j+1]==False:
        s+='R'
        dfs(i,j+1)
        s+='L'
dfs(si,sj)
print(s)

ABC204 C-Tour

有向グラフ
単純に全ての頂点からDFSを行えばよい。この場合のDFSは一度調べた場所は通らないので一回のDFSは$Ο(N)$である。これを全ての頂点で行うので$Ο(N^2)$となる。$2 \leq N \leq 2000$なので十分高速である。

# おまじない
import sys
sys.setrecursionlimit(10000)
# 入力の読み込み
N,M=map(int,input().split())
# graph[i] は都市iから道路で直接繋がっている都市のリスト
graph=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
temp=[False]*N
# dfs
def dfs(u):
    temp[u]=True
    for v in graph[u]:
        if temp[v]: # 既に調べた頂点をは2度以上調べない
            continue
        dfs(v)
ans=0
for i in range(N):
    temp=[False]*N
    # temp[j] は都市jに到達可能かどうかを表す
    dfs(i)
    ans+=sum(temp)
print(ans)

再帰を使わずにwhileを使ったものを下に示す。
実行時間は同じ。これから調べるものを格納するstackはset型にすることで同じものが複数入ることを防いでいる。

N,M=map(int,input().split())
graph=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
temp=[False]*N
# ここまで同じ
def serch(x):
    temp=[False]*N
    stack=set() # これから調べるものを格納する
    stack.add(x)
    while stack: # stackに中身がある間
        u=stack.pop()
        temp[u]=True
        for v in graph[u]:
            if temp[v]:
                continue
            stack.add(v)
    return sum(temp)
ans=0
for i in range(N):
    ans+=serch(i)
print(ans)

typical90 003-Longest Circular Road

距離(間にある辺の数)が最も大きい2点を求める問題。
方法はまず適当な頂点から最も距離の大きい点を求め、次にその点から最も距離の大きい頂点を探す。

import sys
sys.setrecursionlimit(10**6)
N = int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    graph[a].append(b)
    graph[b].append(a)
c_max = -1  # 深さの最大値
c_n = -1    # 深さが最大となる頂点
def dfs(u,par,deep):
    global c_max,c_n
    if c_max<deep:
        c_max=deep
        c_n=u
    for v in graph[u]:
        if v == par: # 木なので前の頂点以外は調べていない
            continue
        dfs(v, u, deep + 1)
dfs(0,-1,0)
dfs(c_n,-1,0)
ans=c_max+1
print(ans)

N = int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    graph[a].append(b)
    graph[b].append(a)
c_max = -1  # 深さの最大値
c_n = -1    # 深さが最大となる頂点
def serch(x):
    global c_max,c_n
    stack = [(x, -1, 0)]
    while stack:
        u, par, deep = stack.pop()
        if c_max<deep:
            c_max=deep
            c_n=u
        for v in graph[u]:
            if v == par:
                continue
            stack.append((v, u, deep + 1))
serch(0)
serch(c_n)
ans=c_max+1
print(ans)

2部グラフ

グラフ上の任意の2頂点間に道が存在するグラフを連結グラフという。
閉路を持たない連結グラフを木という。
2色に色分けできるグラフを2部グラフという。木は2部グラフである。

typical90 026-Independent Set on a Tree

色分けした後、頂点数が多い色の方からN/2個取り出せば答え。

# 木は2部グラフなので、頂点を2色に塗り分けできる
# 頂点数が多い色の方からN/2個取り出せば答え

n = int(input())
to = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    to[u].append(v)
    to[v].append(u)

ans = [[], []]
stack = [(0, -1, 0)]
while stack:
    u, par, color = stack.pop()
    ans[color].append(u+1)
    for v in to[u]:
        if v == par: continue
        stack.append((v, u, color ^ 1))
if len(ans[0]) > len(ans[1]): print(*ans[0][:n//2])
else: print(*ans[1][:n//2])

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n=int(input())
g=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    g[a-1]+=[b-1]
    g[b-1]+=[a-1]
C=[1]*n
def dfs(v,p=-1):
    for c in g[v]:
        if c==p: continue
        dfs(c,v)
        if C[c]: C[v]=0
dfs(0)
print(*[v+1 for v in range(n) if C[v]][:n//2])

ABC209 D-Collision

一見距離を求める問題だがいちいち距離を求めていると、$Ο(QN)$となりTLEになってしまう。色分けすることで、それぞれは$Ο(1)$で求まるようになるので、$Ο(N+Q)$となる。

N,Q=map(int,input().split())
G=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    G[a].append(b)
    G[b].append(a)

stack = [(0, -1)]
C=[-1]*N
C[0]=0
while stack:
    u, par = stack.pop()
    color=C[u]
    for v in G[u]:
        if v == par: continue
        stack.append((v, u))
        C[v]=color ^ 1

for _ in range(Q):
    c,d=map(int,input().split())
    c,d=c-1,d-1
    if C[c]==C[d]:
        print('Town')
    else:
        print('Road')

UnionFind

UnionFindは繋がっているかどうかだけが重要な問題。

ATC001 B-UnionFind

それぞれの頂点について自身が接続している根を格納するリストを作る。根がないときは自身の値を入れておく。根を調べるときにうまく経路を圧縮していくことでだいたい$Ο(\log N)$で計算出来る。
この問題では$Ο(Q\log N)$となり、$1 \leq N \leq 10^5$ , $1 \leq Q \leq 2\times10^5$であるため、十分高速。

import sys
sys.setrecursionlimit(10**6)
N,Q=map(int,input().split())
par=[i for i in range(N)]
def root(u):
    if par[u]==u:
        return u
    else:
        par[u]=root(par[u])
        return par[u]
for i in range(Q):
    P,A,B=map(int,input().split())
    A,B=A-1,B-1
    if P==0:
        x=root(A)
        y=root(B)
        if x!=y:
            par[x]=y # xの根をyにする
    else:
        x=root(A)
        y=root(B)
        if x==y:
            print('Yes')
        else:
            print('No')

下はクラスを使ってみたものだ。

class Union:
    def __init__(self,n):
        self.par=[i for i in range(n)]
    def root(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.root(self.par[x])
            return self.par[x]
    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return
        self.par[x]=y
    def same(self,x,y):
        return self.root(x)==self.root(y)
N,Q=map(int,input().split())
uni=Union(N)
for i in range(Q):
    P,A,B=map(int,input().split())
    A,B=A-1,B-1
    if P==0:
        uni.unite(A,B)
    else:
        if uni.same(A,B):
            print('Yes')
        else:
            print('No')

ABC206 D-KAIBUNsyo

import sys
sys.setrecursionlimit(2*10**5)
class Union:
    def __init__(self,n):
        self.N=n
        self.par=[i for i in range(n)]
    def root(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.root(self.par[x])
            return self.par[x]
    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return
        self.par[x]=y
    def union_num(self):
        re=0
        for i in range(self.N):
            if self.par[i]!=i:
                re+=1
        return re
N=int(input())
A=list(map(int,input().split()))
uni=Union(2*10**5)
for i in range(N//2):
    a,b=A[i]-1,A[N-1-i]-1
    uni.unite(a,b)
print(uni.union_num())

DP

ABC204 D-Cooking

N=int(input())
T=list(map(int,input().split()))
t_sum=sum(T)
dp=[[False for i in range(2*t_sum)] for j in range(N+1)]
dp[0][T[0]]=True
for i in range(1,N):
    t=T[i]
    dp[i][t]=True
    ans=[]
    for j in range(2*t_sum):
        dp[i][j]=dp[i-1][j]
        if j-t>=0:
            dp[i][j]=dp[i][j] or dp[i-1][j-t]
for i in range((t_sum+1)//2,2*t_sum):
    if dp[N-1][i]:
        print(i)
        break

ABC189 D-Logical Expression

N=int(input())
S=[]
for i in range(N):
    S.append(input())
y=[[0,0] for i in range(N+1)]
y[0][0]=1
y[0][1]=1
for i in range(N):
    if S[i]=='AND':
        y[i+1][0]=y[i][0]*2+y[i][1]
        y[i+1][1]=y[i][1]
    else:
        y[i+1][0]=y[i][0]
        y[i+1][1]=y[i][0]+y[i][1]*2
print(y[N][1])

期待値

ABC184 D-increment of coins

A,B,C=map(int,input().split())
dp=[[[0 for i in range(101)] for j in range(101)] for k in range(101)]
dp[A][B][C]=1
for i in range(A,100):
    for j in range(B,100):
        for k in range(C,100):
            dp[i+1][j][k]+=dp[i][j][k]*i/(i+j+k)
            dp[i][j+1][k]+=dp[i][j][k]*j/(i+j+k)
            dp[i][j][k+1]+=dp[i][j][k]*k/(i+j+k)
ans=0
for i in range(A,101):
    for j in range(B,101):
        for k in range(C,101):
            if i!=100 and j!=100 and k!=100:
                continue
            ans+=dp[i][j][k]*(i+j+k-A-B-C)
print(ans)

メモ

https://atcoder.jp/contests/abc210/tasks/abc210_d

https://atcoder.jp/contests/dp/tasks

キュー

ABC217 E-Sorting Queries

その他

優先度付きキュー

優先度付きキュー(wikipedia)
常にソートされた状態を保ってくれる配列

ABC212 D-Querying Multiset

import heapq
Q=int(input())
a=[]
s=0
for _ in range(Q):
    q=input()
    if q[0]=='1':
        n,x=map(int,q.split())
        heapq.heappush(a, x-s)
    elif q[0]=='2':
        n,x=map(int,q.split())
        s+=x
    else:
        p=heapq.heappop(a)
        print(p+s)

ABC214 E-Packing Under Range Regulations

import heapq
T=int(input())
for i in range(T):
    N=int(input())
    LR=[]
    for j in range(N):
        l,r=map(int,input().split())
        LR.append([l,r])
    LR.append([float('inf'),float('inf')])
    LR.sort()
    hq=[]
    k=0
    j=0
    l=-1
    r=-1
    while True:
        if hq:
            if l==k:
                heapq.heappush(hq,r)
                l,r=LR[j]
                j+=1
            else:
                if hq[0]>=k:
                    heapq.heappop(hq)
                    k+=1
                else:
                    print('No')
                    break
        else:
            if j<N:
                if l==-1:
                    l,r=LR[j]
                    j+=1
                else:
                    k=l
                    heapq.heappush(hq,r)
                    l,r=LR[j]
                    j+=1
            else:
                print('Yes')
                break

いもす法

いもす法の書き方が他の人と違いそう。

ABC188 D-Snuke Prime

N,C=map(int,input().split())
imos={}
for i in range(N):
    a,b,c=map(int,input().split())
    a=a-1
    if a in imos:
        imos[a]+=c
    else:
        imos[a]=c
    if b in imos:
        imos[b]-=c
    else:
        imos[b]=-c
limos=[]
for i,j in imos.items():
    limos.append([i,j])
ln=len(limos)
limos.sort()
ls=[]
s=0
for i in range(ln):
    s+=limos[i][1]
    ls.append([limos[i][0],min(s,C)])
ans=0
for i in range(ln-1):
    ans+=(ls[i+1][0]-ls[i][0])*ls[i][1]
print(ans)

ABC183 D-Water Heater

N,W=map(int,input().split())
imos={}
for i in range(N):
    s,t,p=map(int,input().split())
    if s in imos:
        imos[s]+=p
    else:
        imos[s]=p
    if t in imos:
        imos[t]-=p
    else:
        imos[t]=-p
limos=[]
for i,j in imos.items():
    limos.append([i,j])
limos.sort()
s=0
for i in limos:
    s+=i[1]
    if s>W:
        print('No')
        break
else:
    print('Yes')

二分探索

二分探索(wikipedia)
特定の値がソートされた配列のどこに入るかを調べる。
計算量は$Ο(\log N)$。

ABC205 D-Kth Excluded

ABC172 C-Tsundoku

エラトステネスの篩

N以下の素数を列挙する方法。
約数の列挙にも使える。
計算量はだいたい$Ο(N\log N)$。

メモ

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up