「AtCoder 凡人が『緑』になるための精選50問詳細解説」コピペ用 コード全文集

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のコード全文集です
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

【サンプル(1～24問)】

#1 入力と出力 Dif:5 ABC199 A
https://atcoder.jp/contests/abc199/tasks/abc199_a

A,B,C=map(int, input().split())

if A**2+B**2<C**2:
    print("Yes")
else:
    print("No")

#2 文字列操作1 Dif:6 ABC197 A
https://atcoder.jp/contests/abc197/tasks/abc197_a

S=input()
ans=S[1]+S[2]+S[0]
print(ans)

#3 やるだけ Dif:15 ABC188 B
https://atcoder.jp/contests/abc188/tasks/abc188_b

N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))

naiseki=0

for i in range(N):
    naiseki+=A[i]*B[i]

if naiseki==0:
    print("Yes")
else:
    print("No")

#4 リストの操作 Dif:20 ABC191 B
https://atcoder.jp/contests/abc191/tasks/abc191_b

N,X=map(int, input().split())
A=list(map(int, input().split()))

ans=[]

for i in range(N):
    if A[i]!=X:
        ans.append(A[i])

print(*ans)

#5 全探索1 Dif:21 ABC190 B
https://atcoder.jp/contests/abc190/tasks/abc190_b

N,S,D=map(int, input().split())

for i in range(N):
    X,Y=map(int, input().split())
    if X<S and D<Y:
        print("Yes")
        exit()

print("No")

#6 ソート Dif:32 ABC201 B
https://atcoder.jp/contests/abc201/tasks/abc201_b

N=int(input())

mountains=[]

for i in range(N):
    S,T=map(str, input().split())
    T=int(T)
    mountains.append([T,S])

mountains.sort(reverse=True)

print(mountains[1][1])

#7 マス目問題 Dif:96 ABC197 B
https://atcoder.jp/contests/abc197/tasks/abc197_b

H,W,X,Y=map(int, input().split())

grid=[]

for i in range(H):
    S=input()
    S=list(S)
    grid.append(S)

X-=1
Y-=1

ans=0

# 上
for i in range(1,H):
    if 0<=X-i<H:
        if grid[X-i][Y]=="#":
            break
        else:
            ans+=1
# 下
for i in range(1,H):
    if 0<=X+i<H:
        if grid[X+i][Y]=="#":
            break
        else:
            ans+=1
# 左
for i in range(1,W):
    if 0<=Y-i<W:
        if grid[X][Y-i]=="#":
            break
        else:
            ans+=1
# 右
for i in range(1,W):
    if 0<=Y+i<W:
        if grid[X][Y+i]=="#":
            break
        else:
            ans+=1

ans+=1

print(ans)

#8 関数 Dif:105 ABC192 C
https://atcoder.jp/contests/abc192/tasks/abc192_c

def g1(x):
    x=str(x)
    x=list(x)
    x.sort(reverse=True)
    x="".join(x)
    return int(x)

def g2(x):
    x=str(x)
    x=list(x)
    x.sort()
    x="".join(x)
    return int(x)

def f(x):
    return g1(x)-g2(x)

N,K=map(int, input().split())

a=N

for i in range(K):
    a=f(a)

print(a)

#9 N進法 Dif:131 ABC186 C
https://atcoder.jp/contests/abc186/tasks/abc186_c

def judge_ten(x):
    x=str(x)
    if "7" in x:
        return True
    else:
        return False

def judge_eight(x):
    s=""
    while x>0:
        s=str(x%8)+s
        x//=8
    if "7" in s:
        return True
    else:
        return False

N=int(input())

ans=0

for i in range(1,N+1):
    if judge_ten(i)==False and judge_eight(i)==False:
        ans+=1

print(ans)

#10 約数列挙 Dif:142 ABC180 C
https://atcoder.jp/contests/abc180/tasks/abc180_c

def Divisor_List(N):
    divisor=[]

    i=1
    while i**2<=N:
        if N%i==0:
            divisor.append(i)
            if i!=N//i:
                divisor.append(N//i)
        i+=1

    divisor.sort()
    return divisor

N=int(input())

ans=Divisor_List(N)

for x in ans:
    print(x)

#11 シミュレーション Dif:168 ABC203 C
https://atcoder.jp/contests/abc203/tasks/abc203_c

N,K=map(int, input().split())

friends=[]
for i in range(N):
    A,B=map(int, input().split())
    friends.append([A,B])

friends.sort()

now_village=0

now_village+=K

for i in range(N):
    friend_village=friends[i][0]
    friend_money=friends[i][1]

    if friend_village<=now_village:
        now_village+=friend_money
    else:
        break

print(now_village)

#12 最小公倍数 Dif:172 ABC148 C
https://atcoder.jp/contests/abc148/tasks/abc148_c

import math
def lcm(x,y):
    return (x*y)//math.gcd(x,y)

A,B=map(int, input().split())
print(lcm(A,B))

#13 少数と誤差 Dif:274 ABC189 B
https://atcoder.jp/contests/abc189/tasks/abc189_b

N,X=map(int, input().split())

alcohol=0

for i in range(N):
    V,P=map(int, input().split())
    alcohol+=V*P
    if 100*X<alcohol:
        print(i+1)
        exit()

print(-1)

#14 数学問題1 Dif:274 ABC181 C
https://atcoder.jp/contests/abc181/tasks/abc181_c

N=int(input())

points=[]
for i in range(N):
    x,y=map(int, input().split())
    points.append([x,y])

for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            x1,y1=points[i][0],points[i][1]
            x2,y2=points[j][0],points[j][1]
            x3,y3=points[k][0],points[k][1]

            if (x2-x1)*(y3-y1)==(y2-y1)*(x3-x1):
                print("Yes")
                exit()

print("No")

#15 余り Dif:292 ABC182 C
https://atcoder.jp/contests/abc182/tasks/abc182_c

N=int(input())

amari1=False
amari2=False
amari_all=N%3

N=str(N)

for i in range(len(N)):
    keta_num=N[i]
    keta_num=int(keta_num)
    if keta_num%3==1:
        amari1=True
    elif keta_num%3==2:
        amari2=True

if amari_all==0:
    print(0)

elif amari_all==1:
    if amari1==True:
        if len(N)<=1:
            print(-1)
        else:
            print(1)
    else:
        if len(N)<=2:
            print(-1)
        else:
            print(2)

elif amari_all==2:
    if amari2==True:
        if len(N)<=1:
            print(-1)
        else:
            print(1)
    else:
        if len(N)<=2:
            print(-1)
        else:
            print(2) 

#16 itertools Dif:335 ABC183 C
https://atcoder.jp/contests/abc183/tasks/abc183_c

N,K=map(int, input().split())

time=[]

for i in range(N):
    T=list(map(int, input().split()))
    time.append(T)

ans=0

import itertools
for root in itertools.permutations(range(1,N)):
    now_time=0
    now_time+=time[0][root[0]]
    now_city=root[0]

    for i in range(1,N-1):
        to_city=root[i]
        now_time+=time[now_city][to_city]
        now_city=to_city

    now_time+=time[now_city][0]
    if now_time==K:
        ans+=1

print(ans)

#17 全探索2 Dif:379 ABC193 C
https://atcoder.jp/contests/abc193/tasks/abc193_c

N=int(input())

able_num=set()

for a in range(2,10**5+10):
    for b in range(2,100):
        if a**b<=N:
            able_num.add(a**b)
        else:
            break

print(N-len(able_num))

#18 数列の和 Dif:386 ABC177 C
https://atcoder.jp/contests/abc177/tasks/abc177_c

N=int(input())
A=list(map(int, input().split()))
mod=10**9+7

A_sum=sum(A)

ans=0

for i in range(N):
    A_sum-=A[i]
    ans+=A[i]*(A_sum)
    ans%=mod

print(ans)

#19 数直線 Dif:417 ABC175 C
https://atcoder.jp/contests/abc175/tasks/abc175_c

X,K,D=map(int, input().split())

X=abs(X)

if 0<X-K*D:
    print(abs(X-K*D))

else:
    move_count=K-X//D

    jump_before=X-D*(X//D)
    jump_after=jump_before-D

    if move_count%2==0:
        print(abs(jump_before))
    else:
        print(abs(jump_after))

#20 文字列操作2 Dif:436 ABC199 C
https://atcoder.jp/contests/abc199/tasks/abc199_c

N=int(input())
S=input()
Q=int(input())

S="0"+S
S=list(S)

flip=False

for i in range(Q):
    T,A,B=map(int, input().split())

    if T==1:
        if flip==False:
            S[A],S[B]=S[B],S[A]

        else:
            if A<=N:
                A+=N
            else:
                A-=N
            if B<=N:
                B+=N
            else:
                B-=N
            S[A],S[B]=S[B],S[A]

    # T=2
    else:
        if flip==True:
            flip=False
        else:
            flip=True

S_left=S[1:N+1]
S_right=S[N+1:]

if flip==False:
    ans=S_left+S_right
else:
    ans=S_right+S_left

print("".join(ans))

#21 最小と最大 Dif:483 ABC195 B
https://atcoder.jp/contests/abc195/tasks/abc195_b

A,B,W=map(int, input().split())

W_g=W*1000

min_ans=10**15
max_ans=-10**15

for X in range(1,10**6+10):
    if A*X<=W_g<=B*X:
        min_ans=min(min_ans,X)
        max_ans=max(max_ans,X)

if min_ans==10**15:
    print("UNSATISFIABLE")

else:
    print(min_ans,max_ans)

#22 期待値・区間和 Dif:485 ABC154 D
https://atcoder.jp/contests/abc154/tasks/abc154_d

N,K=map(int, input().split())
p=list(map(int, input().split()))

p_ex=[]
for i in range(N):
    p_ex.append((p[i]+1)/2)

p_ex_Cum=[p_ex[0]]
for i in range(1,N):
    p_ex_Cum.append(p_ex_Cum[i-1]+p_ex[i])

ans=-10**15
for i in range(N-K+1):
    if i==0:
        ans_tmp=p_ex_Cum[i+K-1]
    else:
        ans_tmp=p_ex_Cum[i+K-1]-p_ex_Cum[i-1]

    ans=max(ans,ans_tmp)

print(ans)

#23 pypy Dif:565 ABC189 C
https://atcoder.jp/contests/abc189/tasks/abc189_c

※提出は「pypy」で行う

N=int(input())
A=list(map(int, input().split()))

ans=-10**15
for l in range(N):
    A_min=A[l]
    for r in range(l,N):
        A_min=min(A_min,A[r])
        ans=max(ans,A_min*(r-l+1))

print(ans)

#24 Bit全探索 Dif:595 ABC167 C
https://atcoder.jp/contests/abc167/tasks/abc167_c

N,M,X=map(int, input().split())

C=[]
A=[]
for i in range(N):
    CA=list(map(int, input().split()))
    C.append(CA[0])
    A.append(CA[1:])

ans=10**20
for i in range(1<<N):
    cost=0
    skill=[0]*M

    for shift in range(N):
        if i>>shift & 1==1:
            cost+=C[shift]
            for j in range(M):
                skill[j]+=A[shift][j]

    if X<=min(skill):
        ans=min(ans,cost)

if ans==10**20:
    print(-1)
else:
    print(ans)

#25 DP1 Dif:600? EDPC A
https://atcoder.jp/contests/dp/tasks/dp_a

N=int(input())
h=[0]+list(map(int, input().split()))

dp=[10**15]*(N+1)

dp[1]=0
dp[2]=abs(h[2]-h[1])

for i in range(3,N+1):
    cost2=dp[i-2]+abs(h[i]-h[i-2])
    cost1=dp[i-1]+abs(h[i]-h[i-1])
    dp[i]=min(cost1,cost2)

print(dp[N])

#26 deque Dif:610 ABC158 D
https://atcoder.jp/contests/abc158/tasks/abc158_d

S=input()
Q=int(input())

inv=False
 
from collections import deque
S_deque=deque()
 
for i in range(len(S)):
    S_deque.append(S[i])
 
for i in range(Q):
    TFC=list(map(str, input().split()))
 
    if TFC[0]=="1":
        if inv==False:
            inv=True
        else:
            inv=False

    else:
        F=TFC[1]
        C=TFC[2]

        if inv==False:
            if F=="1":
                S_deque.appendleft(C)
            else:
                S_deque.append(C)
        else:
            if F=="1":
                S_deque.append(C)
            else:
                S_deque.appendleft(C)
 
ans="".join(S_deque)
 
if inv==True:
    ans=ans[::-1]
 
print(ans)

#27 BFS(幅優先探索)1 Dif:629 ABC204 C
https://atcoder.jp/contests/abc204/tasks/abc204_c

N,M=map(int, input().split())

connect=[[] for i in range(N+1)]

for i in range(M):
    A,B=map(int, input().split())
    connect[A].append(B)

from collections import deque

def BFS(start):
    visited=[False]*(N+1)
 
    visited[start]=True
    cnt=1
 
    que=deque()
    que.append(start)
 
    while 0<len(que):
        now_city=que.popleft()
 
        for to_city in connect[now_city]:
            if visited[to_city]==False:
                visited[to_city]=True
                cnt+=1
                que.append(to_city)
 
    return cnt

ans=0

for i in range(1,N+1):
    ans+=BFS(i)

print(ans)

#28 Bit全探索2 Dif:653 173 C
https://atcoder.jp/contests/abc173/tasks/abc173_c

H,W,K=map(int, input().split())

c=[]

for gyou in range(H):
    tmp=input()
    tmp=list(tmp)
    c.append(tmp)
 
ans=0
 
for gyou_red in range(1<<H):
    for retu_red in range(1<<W):
        black=0
        
        for gyou in range(H):
            for retu in range(W):
 
                if gyou_red>>gyou & 1==0 and retu_red>>retu & 1==0:
                    if c[gyou][retu]=="#":
                        black+=1
        
        if black==K:
            ans+=1
 
print(ans)

#29 包除原理 Dif:653 ABC178 C
https://atcoder.jp/contests/abc178/tasks/abc178_c

N=int(input())
mod=10**9+7

A_all=pow(10,N,mod)
A_0=pow(9,N,mod)
A_9=pow(9,N,mod)
A_0_9=pow(8,N,mod)

ans=A_all-(A_0+A_9-A_0_9)
ans%=mod
print(ans)

#30 全探索3 Dif:694 ABC166 D
https://atcoder.jp/contests/abc166/tasks/abc166_d

X=int(input())

for A in range(-10**3,10**3):
    for B in range(-10**3,10**3):
        if A**5-B**5==X:
            print(A,B)
            exit()

#31 貪欲 Dif:719 ABC149 D
https://atcoder.jp/contests/abc149/tasks/abc149_d

N,K=map(int, input().split())
R,S,P=map(int, input().split())
T=input()

hands=[]
ans=0

for i in range(N):
    if T[i]=="r":
        if i<K:
            ans+=P
            hands.append("p")
        elif K<=i and hands[i-K]!="p":
            ans+=P
            hands.append("p")
        else:
            hands.append("x")

    if T[i]=="s":
        if i<K:
            ans+=R
            hands.append("r")           
        elif K<=i and hands[i-K]!="r":
            ans+=R
            hands.append("r")
        else:
            hands.append("x")

    if T[i]=="p":
        if i<K:
            ans+=S
            hands.append("s")          
        elif K<=i and hands[i-K]!="s":
            ans+=S
            hands.append("s")
        else:
            hands.append("x")

print(ans)

#32 数学問題2 Dif:722 ABC190 D
https://atcoder.jp/contests/abc190/tasks/abc190_d

N=int(input())

ans=0

i=1
while i*i<=2*N:
    if 2*N%i==0:
        x=i
        y=2*N//i
        if x%2!=y%2:
            ans+=2
    i+=1

print(ans)

#33 UnionFind Dif:732 ABC177 D
https://atcoder.jp/contests/abc177/tasks/abc177_d

class UnionFind:
    def __init__(self, n):
        self.n=n
        self.parent_size=[-1]*n
    def merge(self, a, b):
        x, y=self.leader(a), self.leader(b)
        if x == y: return 
        if abs(self.parent_size[x])<abs(self.parent_size[y]): x, y=y, x
        self.parent_size[x] += self.parent_size[y] 
        self.parent_size[y]=x
        return 
    def same(self, a, b):
        return self.leader(a) == self.leader(b)
    def leader(self, a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def size(self, a):
        return abs(self.parent_size[self.leader(a)])
    def groups(self):
        result=[[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

N,M=map(int, input().split())
Uni=UnionFind(N)

for i in range(M):
    A,B=map(int, input().split())
    A-=1
    B-=1
    Uni.merge(A,B)

friends_group=Uni.groups()

friends_size=[]
for fri in friends_group:
    friends_size.append(len(fri))

print(max(friends_size))

#34 素因数分解 Dif:732 ABC169 D
https://atcoder.jp/contests/abc169/tasks/abc169_d

def prime_factorize(N):
    if N==1:
        return [1]
    prime_list=[]
    i=2
    while i*i<=N:
        if N%i==0:
            prime_list.append(i)
            N//=i
        else:
            i+=1
    if N!=1:
        prime_list.append(N)
    return prime_list

N=int(input())

if N==1:
    print(0)
    exit()

prime_N=prime_factorize(N)

prime_N=set(prime_N)

ans=0

for p in prime_N:
    for e in range(1,10**10):
        if N%(p**e)==0:
            ans+=1
            N//=p**e
        else:
            break

print(ans)

#35 二分探索 Dif:741 ABC146 C
https://atcoder.jp/contests/abc146/tasks/abc146_c

def price(N):
    N_str=str(N)
    d=len(N_str)
    return A*N+B*d

A,B,X=map(int, input().split())

if X<price(1):
    print(0)
    exit()

left=1
right=10**20

while 1<right-left:
    N=(left+right)//2
    if price(N)<=X:
        left=N
    else:
        right=N

if 10**9<left:
    left=10**9

print(left)

#36 ループ Dif:754 ABC167 D
https://atcoder.jp/contests/abc167/tasks/abc167_d

N,K=map(int, input().split())
A=[0]+list(map(int, input().split()))
 
visited=[-1]*(N+1)
visited[1]=0
 
now_town=1
move_cnt=0
 
for i in range(10**6):
    move_cnt+=1
    now_town=A[now_town]
 
    if move_cnt==K:
        print(now_town)
        exit()
    
    if visited[now_town]==-1:
        visited[now_town]=move_cnt
    else:
        cycle=move_cnt-visited[now_town]
        break
 
K-=move_cnt

K%=cycle
for i in range(K):
    now_town=A[now_town]
 
print(now_town)

#37 BFS(幅優先探索)2 Dif:804 ABC168 D
https://atcoder.jp/contests/abc168/tasks/abc168_d

N,M=map(int, input().split())

connect=[[] for i in range(N+1)]

for i in range(M):
    A,B=map(int, input().split())
    connect[A].append(B)
    connect[B].append(A)
 
visited=[False]*(N+1)
visited[1]=True

from collections import deque
que=deque()
que.append(1)

ans=[0]*(N+1)

while 0<len(que):
    now_room=que.popleft()
    for to_room in connect[now_room]:
        if visited[to_room]==False:
            visited[to_room]=True
            ans[to_room]=now_room
            que.append(to_room)

print("Yes")
for i in range(2,N+1):
    print(ans[i])

#38 Bit全探索3 Dif:809 ABC197 C
https://atcoder.jp/contests/abc197/tasks/abc197_c

※提出は「pypy」で行う

N=int(input())
A=list(map(int, input().split()))

def calc_or(left,right):
    result=0
    for i in range(left,right):
        result=result | A[i]
    return result

ans=2**40
 
for i in range(1<<(N+1)):
    if i & 1 ==0 or i>>N & 1 ==0:
        continue

    partitions=[]
    for shift in range(N+1):
        if i>>shift & 1 ==1:
            partitions.append(shift)
   
    ans_tmp=0
    for j in range(len(partitions)-1):
        ans_tmp=ans_tmp^calc_or(partitions[j],partitions[j+1])
    ans=min(ans,ans_tmp)

print(ans)

#39 heap Dif:823 ABC141 D
https://atcoder.jp/contests/abc141/tasks/abc141_d

N,M=map(int, input().split())
A=list(map(int, input().split()))

A_minus=[]
for i in range(N):
    A_minus.append((-1)*A[i])

import heapq
heapq.heapify(A_minus)

for i in range(M):
    X=heapq.heappop(A_minus)
    X/=2
    X=int(X)
    heapq.heappush(A_minus,X)

ans=(-1)*sum(A_minus)

print(ans)

#40 数学問題3 Dif:831 ABC197 D
https://atcoder.jp/contests/abc197/tasks/abc197_d

N=int(input())
x0,y0=map(int, input().split())
xn2,yn2=map(int, input().split())

center_x=(x0+xn2)/2
center_y=(y0+yn2)/2

x0-=center_x
y0-=center_y

from math import sin,cos,pi
x1=cos(2*pi/N)*x0-sin(2*pi/N)*y0
y1=sin(2*pi/N)*x0+cos(2*pi/N)*y0

x1+=center_x
y1+=center_y

print(x1,y1)

#41 DP2 Dif:875 ABC178 D
https://atcoder.jp/contests/abc178/tasks/abc178_d

S=int(input())
mod=10**9+7

dp=[0]*(10**5)

dp[0]=0
dp[1]=0
dp[2]=0
dp[3]=1
dp[4]=1
dp[5]=1

for i in range(6,S+1):
    dp[i]=sum(dp[3:i-2])+1
    dp[i]%=mod

print(dp[S])

#42 DP3 Dif:900? EDPC D
https://atcoder.jp/contests/dp/tasks/dp_d

※提出は「pypy」で行う

N,W=map(int, input().split())
items=[[0,0]]
for i in range(N):
    w,v=map(int, input().split())
    items.append([w,v])

dp=[[0]*(W+1) for i in range(N+1)]

for gyou_i in range(1,N+1):
    for retu_w in range(W+1):
        w,v=items[gyou_i]
        if retu_w-w<0:
            dp[gyou_i][retu_w]=dp[gyou_i-1][retu_w]
        else:
            red=dp[gyou_i-1][retu_w]
            blue=dp[gyou_i-1][retu_w-w]+v
            dp[gyou_i][retu_w]=max(red,blue)

print(dp[N][W])

#43 鳩の巣原理 Dif:902 ABC174 C
https://atcoder.jp/contests/abc174/tasks/abc174_c

K=int(input())

amari=0

for i in range(1,K+1):
    amari=amari*10+7
    
    if amari%K==0:
        print(i)
        exit()

    amari%=K

print(-1)

#44 BFS(幅優先探索)3 Dif:959 ABC151 D
https://atcoder.jp/contests/abc151/tasks/abc151_d

H,W=map(int, input().split())

maze=[]
for i in range(H):
    tmp=input()
    maze.append(list(tmp))
 
from collections import deque
 
def explore(start_gyou,start_retu):
    maze_count=[[-1]*W for i in range(H)]
    maze_count[start_gyou][start_retu]=0

    que=deque()
    que.append([start_gyou,start_retu])
    
    while 0<len(que):
        now_gyou,now_retu=que.popleft()
        now_count=maze_count[now_gyou][now_retu]
       
        # 左
        if 0<=now_gyou-1<H and 0<=now_retu<W:
            if maze[now_gyou-1][now_retu]=="." :
                if maze_count[now_gyou-1][now_retu]==-1:
                    maze_count[now_gyou-1][now_retu]=now_count+1
                    que.append([now_gyou-1,now_retu])
      
        # 右
        if 0<=now_gyou+1<H and 0<=now_retu<W:
            if maze[now_gyou+1][now_retu]=="." :
                if maze_count[now_gyou+1][now_retu]==-1:
                    maze_count[now_gyou+1][now_retu]=now_count+1
                    que.append([now_gyou+1,now_retu])
     
        # 上
        if 0<=now_gyou<H and 0<=now_retu-1<W:
            if maze[now_gyou][now_retu-1]=="." :
                if maze_count[now_gyou][now_retu-1]==-1:
                    maze_count[now_gyou][now_retu-1]=now_count+1
                    que.append([now_gyou,now_retu-1])
     
        # 下
        if 0<=now_gyou<H and 0<=now_retu+1<W:
            if maze[now_gyou][now_retu+1]=="." :
                if maze_count[now_gyou][now_retu+1]==-1:
                    maze_count[now_gyou][now_retu+1]=now_count+1
                    que.append([now_gyou,now_retu+1])
    
    max_count=0
    for gyou in range(H):
        for retu in range(W):
            max_count=max(max_count,maze_count[gyou][retu])

    return max_count
 
ans=0
for gyou in range(H):
    for retu in range(W):
        if maze[gyou][retu]==".":
            ans=max(ans,explore(gyou,retu))
 
print(ans)

#45 余りの除算 Dif:1014 ABC156 D
https://atcoder.jp/contests/abc156/tasks/abc156_d

n,a,b=map(int, input().split())
mod=10**9+7

def nCr_mod(n,r,mod):
    # 分子
    numerator=1
    for i in range(n-r+1,n+1):
        numerator*=i
        numerator%=mod
    # 分母
    denominator=1
    for i in range(1,r+1):
        denominator*=i
        denominator%=mod
    denominator_inv=pow(denominator,-1,mod)
    return numerator*denominator_inv%mod

ans=pow(2,n,mod)
ans-=1
ans-=nCr_mod(n,a,mod)
ans-=nCr_mod(n,b,mod)
ans%=mod
print(ans)

#46 DP4 Dif:1015 ABC153 E
https://atcoder.jp/contests/abc153/tasks/abc153_e

※提出は「pypy」で行う

H,N=map(int, input().split())

dp=[10**10]*(H+1)
dp[0]=0
 
for i in range(N):
    A,B=map(int, input().split())
    for h in range(H+1):
        if h+A<=H:
            dp[h+A]=min(dp[h+A],dp[h]+B)
        else:
            dp[H]=min(dp[H],dp[h]+B)

print(dp[H])

#47 セグメントツリー Dif:1053 ABC185 F
https://atcoder.jp/contests/abc185/tasks/abc185_f

※提出は「pypy」で行う

def segfunc(x,y):
    return x^y

class SegTree:
    def __init__(self,x_list,init,segfunc):
        self.init=init
        self.segfunc=segfunc
        self.Height=len(x_list).bit_length()+1
        self.Tree=[init]*(2**self.Height)
        self.num=2**(self.Height-1)
        for i in range(len(x_list)):
            self.Tree[2**(self.Height-1)+i]=x_list[i]
        for i in range(2**(self.Height-1)-1,0,-1):
            self.Tree[i]=segfunc(self.Tree[2*i],self.Tree[2*i+1])
           
    def select(self,k):
        return self.Tree[k+self.num]
       
    def update(self,k,x):
        i=k+self.num
        self.Tree[i]=x
        while i>1:
            if i%2==0:
                self.Tree[i//2]=self.segfunc(self.Tree[i],self.Tree[i+1])
            else:
                self.Tree[i//2]=self.segfunc(self.Tree[i-1],self.Tree[i])
            i//=2

    def query(self,l,r):
        result=self.init
        l+=self.num
        r+=self.num+1

        while l<r:
            if l%2==1:
                result=self.segfunc(result,self.Tree[l])
                l+=1
            if r%2==1:
                result=self.segfunc(result,self.Tree[r-1])
            l//=2
            r//=2
        return result


N,Q=map(int, input().split())
A=list(map(int, input().split()))

seg=SegTree(A,0,segfunc)
for i in range(Q):
    T,X,Y=map(int, input().split())
    if T==1:
        X-=1
        seg.update(X,seg.select(X)^Y)
    else:
        X-=1
        Y-=1
        print(seg.query(X,Y))

#48 マンハッタン距離 Dif:1054 ABC178 E
https://atcoder.jp/contests/abc178/tasks/abc178_e

N=int(input())

point=[]
for i in range(N):
    x,y=map(int, input().split())
    point.append([x,y])

pointX_conv=[]
pointY_conv=[]

for x,y in point:
    pointX_conv.append(x+y)
    pointY_conv.append(x-y)

Xdist_max=abs(max(pointX_conv)-min(pointX_conv))
Ydist_max=abs(max(pointY_conv)-min(pointY_conv))

print(max(Xdist_max,Ydist_max))

#49 高速素因数分解 Dif:1057 ABC177 E
https://atcoder.jp/contests/abc177/tasks/abc177_e

N=int(input())
A=list(map(int, input().split()))

D=[0]*(10**6+10)

for i in range(2,10**6+10):
    if D[i]!=0:
        continue
    for k in range(1,10**6):
        if i*k<10**6+10:
            if D[i*k]==0:
                D[i*k]=i
        else:
            break

def fast_prime_fact(x):
    prime=[]
    while 1<x:
        prime.append(D[x])
        x//=D[x]
    return prime

pairwise=True
prime_used=[0]*(10**6+10)
for i in range(N):
    prime_list=fast_prime_fact(A[i])
    prime_set=set(prime_list)
    for i in prime_set:
        if prime_used[i]==1:
            pairwise=False
            break
        else:
            prime_used[i]=1

if pairwise==True:
    print("pairwise coprime")
    exit()

from math import gcd
g=A[0]
for i in range(1,N):
    g=gcd(g,A[i])

if g==1:
    print("setwise coprime")
else:
    print("not coprime")

#50 ダイクストラ法 Dif:1135 ABC192 E
https://atcoder.jp/contests/abc192/tasks/abc192_e

N,M,X,Y=map(int, input().split())

connect=[[] for i in range(N+1)]

for i in range(M):
    A,B,T,K=map(int, input().split())
    connect[A].append([B,T,K])
    connect[B].append([A,T,K])

que=list()

import heapq
heapq.heappush(que,[0,X])

time=[10**20]*(N+1)
time[X]=0
confirmed=[False]*(N+1)

from math import ceil
while 0<len(que):
    now_time,now_place=heapq.heappop(que)
    if confirmed[now_place]==True:
        continue
    confirmed[now_place]=True
    for to_place,T,K in connect[now_place]:
        if confirmed[to_place]==False:
            to_time=ceil(now_time/K)*K+T
            if to_time<time[to_place]:
                time[to_place]=to_time
                heapq.heappush(que,[to_time,to_place])

if time[Y]==10**20:
    print(-1)
else:
    print(time[Y])

#UnionFindの実装

# UnionFind
class UnionFind:
    # 初期化 nは要素数
    def __init__(self,n):
        # 全体の大きさ
        self.n=n
        # -x:グループのサイズ(自身が根),k(正):根がk
        self.parent_size=[-1]*n

    # 要素の根を返す
    def leader(self,a):
        # aが根ならa自身を返す
        if self.parent_size[a]<0: return a
        # aが根でないなら根に向かって木をたどる＋根の更新
        self.parent_size[a]=self.leader(self.parent_size[a])
        # 根を返す
        return self.parent_size[a]

    # aとbを結合
    def merge(self,a,b):
        # a,bの根をx,yへ
        x,y=self.leader(a),self.leader(b)
        # 根が同じなら終了
        if x == y: return 
        # グループのサイズ=要素数を比較　サイズの小さい方を大きい方につなげるため
        # x<yならばx,yを入れ替える
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        # サイズの更新：小さい方のサイズを大きい方のサイズに足す
        self.parent_size[x] += self.parent_size[y]
        # サイズが小さい方の根を大きい方の根につなげる
        self.parent_size[y]=x
        return 

    # 同じグループか判定　同じならTrue
    def same(self,a,b):
        # 根を比較して同じならTrue
        return self.leader(a) == self.leader(b)

    # 属するグループのサイズを返す
    def size(self,a):
        # 根の絶対値=サイズ
        return abs(self.parent_size[self.leader(a)])

    # groupの全体を返す
    def groups(self):
        # グループの格納リストを作る
        result=[[] for _ in range(self.n)]
        # リストの生成
        for i in range(self.n):
            result[self.leader(i)].append(i)
        # 空の要素を消す
        return [r for r in result if r != []]

#セグメントツリーの実装

# セグメントツリー
#演算
def segfunc(x,y):
    return x+y

class SegTree:
    # 初期化(元のリスト、単位元、演算)
    def __init__(self,x_list,init,segfunc):
        # 単位元
        self.init=init
        # 演算
        self.segfunc=segfunc
        # 高さ=もとの数列の長さのビット長+1
        self.Height=len(x_list).bit_length()+1
        # 木
        self.Tree=[init]*(2**self.Height)
        # Tree最下段一番左のインデックス番号
        self.num=2**(self.Height-1)
        # 最下段に要素をセット
        for i in range(len(x_list)):
            self.Tree[2**(self.Height-1)+i]=x_list[i]
        # 上に向かって構築
        for i in range(2**(self.Height-1)-1,0,-1):
            self.Tree[i]=segfunc(self.Tree[2*i],self.Tree[2*i+1])

    # 参照
    def select(self,k):
        return self.Tree[k+self.num]

    # 更新(k番目(0インデックス),値)
    def update(self,k,x):
        # 最下段のインデックス番号に合わせる
        i=k+self.num
        # 最下段の要素を更新
        self.Tree[i]=x
        # 上に向かって更新
        while i>1:
            # iが偶数の時
            if i%2==0:
                self.Tree[i//2]=self.segfunc(self.Tree[i],self.Tree[i+1])
            # iが奇数の時
            else:
                self.Tree[i//2]=self.segfunc(self.Tree[i-1],self.Tree[i])
            i//=2
 
    # 区間の処理
    def query(self,l,r):
        # 下から処理
        # 計算結果　初期値は単位元
        result=self.init
        # 左端　最下段のインデックスに合わせる
        l+=self.num
        # 右端　最下段のインデックスに合わせる　後の処理を楽にするため+1しておく
        r+=self.num+1

        while l<r:
            # lが奇数だったら
            if l%2==1:
                # 値を使う
                result=self.segfunc(result,self.Tree[l])
                # 一個右に移動
                l+=1
            # rが奇数だったら
            if r%2==1:
                # 値を使う
                result=self.segfunc(result,self.Tree[r-1])
            l//=2
            r//=2
        # 結果を返す
        return result