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

これはAtCoderで緑コーダーになるために自分が学んだアルゴリズムなどの備忘録です。
他の人のコードを参考にしている部分もあります。
言語はPythonを使っています。
# グラフ
グラフ([wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)))
グラフについて解説していく。
まずはデータの取り込み方から。
## データの取り込み
### [typical90 078-EasyGraphProblem](https://atcoder.jp/contests/typical90/tasks/typical90_bz)
```Python
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番目は使っていない。
下のコードではグラフの構造を作らずに直接数えている。

```Python
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](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2))
まずはグラフではない問題をみる。
### [AHC005 A-Patrolling](https://atcoder.jp/contests/ahc005/tasks/ahc005_a)
この問題の趣旨はDFSではないが、ヴィジュアライザがわかりやすいのでこれを取り上げる。

```Python
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](https://atcoder.jp/contests/abc204/tasks/abc204_c)
有向グラフ
単純に全ての頂点からDFSを行えばよい。この場合のDFSは一度調べた場所は通らないので一回のDFSは$Ο(N)$である。これを全ての頂点で行うので$Ο(N^2)$となる。$2 \leq N \leq 2000$なので十分高速である。

```Python
# おまじない
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型にすることで同じものが複数入ることを防いでいる。

```Python
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](https://atcoder.jp/contests/typical90/tasks/typical90_c)
距離(間にある辺の数)が最も大きい2点を求める問題。
方法はまず適当な頂点から最も距離の大きい点を求め、次にその点から最も距離の大きい頂点を探す。

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

```Python
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頂点間に道が存在するグラフを[連結グラフ](https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%82%B0%E3%83%A9%E3%83%95)という。
[閉路](https://ja.wikipedia.org/wiki/%E9%96%89%E8%B7%AF)を持たない連結グラフを[木](https://ja.wikipedia.org/wiki/%E6%9C%A8_(%E6%95%B0%E5%AD%A6))という。
2色に色分けできるグラフを[2部グラフ](https://ja.wikipedia.org/wiki/2%E9%83%A8%E3%82%B0%E3%83%A9%E3%83%95)という。木は2部グラフである。
### [typical90 026-Independent Set on a Tree](https://atcoder.jp/contests/typical90/tasks/typical90_z)
色分けした後、頂点数が多い色の方からN/2個取り出せば答え。

```Python
# 木は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])
```
```Python
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](https://atcoder.jp/contests/abc209/tasks/abc209_d)
一見距離を求める問題だがいちいち距離を求めていると、$Ο(QN)$となりTLEになってしまう。色分けすることで、それぞれは$Ο(1)$で求まるようになるので、$Ο(N+Q)$となる。

```Python
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](https://atcoder.jp/contests/atc001/tasks/unionfind_a)
それぞれの頂点について自身が接続している根を格納するリストを作る。根がないときは自身の値を入れておく。根を調べるときにうまく経路を圧縮していくことでだいたい$Ο(\log N)$で計算出来る。
この問題では$Ο(Q\log N)$となり、$1 \leq N \leq 10^5$ , $1 \leq Q \leq 2\times10^5$であるため、十分高速。

```Python
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')
```
下はクラスを使ってみたものだ。

```Python
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](https://atcoder.jp/contests/abc206/tasks/abc206_d)
```Python
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())
```

## メモ
### https://atcoder.jp/contests/abc208/tasks/abc208_d
### https://atcoder.jp/contests/atc001/tasks/dfs_a
### https://atcoder.jp/contests/abc211/tasks/abc211_d

# DP
## [ABC204 D-Cooking](https://atcoder.jp/contests/abc204/tasks/abc204_d)
```Python
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](https://atcoder.jp/contests/abc189/tasks/abc189_d)
```Python
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](https://atcoder.jp/contests/abc184/tasks/abc184_d)
```Python
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](https://atcoder.jp/contests/abc217/tasks/abc217_e)
```Python

```
# その他
## 優先度付きキュー
優先度付きキュー([wikipedia](https://ja.wikipedia.org/wiki/%E5%84%AA%E5%85%88%E5%BA%A6%E4%BB%98%E3%81%8D%E3%82%AD%E3%83%A5%E3%83%BC))
常にソートされた状態を保ってくれる配列
### [ABC212 D-Querying Multiset](https://atcoder.jp/contests/abc212/tasks/abc212_d)
```Python
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](https://atcoder.jp/contests/abc214/tasks/abc214_e)
```Python
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](https://atcoder.jp/contests/abc188/tasks/abc188_d)
```Python
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](https://atcoder.jp/contests/abc183/tasks/abc183_d)
```Python
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](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2))
特定の値がソートされた配列のどこに入るかを調べる。
計算量は$Ο(\log N)$。
### [ABC205 D-Kth Excluded](https://atcoder.jp/contests/abc205/tasks/abc205_d)
```Python

```
### [ABC172 C-Tsundoku](https://atcoder.jp/contests/abc172/tasks/abc172_c)
```Python

```
## エラトステネスの篩
N以下の素数を列挙する方法。
約数の列挙にも使える。
計算量はだいたい$Ο(N\log N)$。
### [ABC215 D-Coprime 2](https://atcoder.jp/contests/abc215/tasks/abc215_d)
```Python

```
### [ABC170 D-Not Divisible](https://atcoder.jp/contests/abc170/tasks/abc170_d)
```Python

```
### [ABC172 D-Sum of Divisors](https://atcoder.jp/contests/abc172/tasks/abc172_d)
```Python

```
## メモ
https://atcoder.jp/contests/typical-algorithm