ABC325の解説（A~E)
B問題 World Meeting
現在の時刻から24時間先まで全部シミュレーションして、そのときに一番多かった社員の数を出力すればよいです。
n=int(input()) rotti=[] ans=0 for i in range(n): rotti.append(list(map(int,input().split()))) for i in range(24): count=0 for ipp in range(n): if (rotti[ipp][1]+i)%24>=9 and (rotti[ipp][1]+i+1)%24<=18 and (rotti[ipp][1]+i+1)%24!=0: count+=rotti[ipp][0] ans=max(count,ans) print(ans)
C問題 Sensors
UnionFindやBFS（幅優先探索）で解くことができます。ぼくはBFSを使ってときました。
かなり典型的な問題だったと思います。
h,w=map(int,input().split()) rotti=[[]*1 for i in range(h)] for i in range(h): rotti[i]=list(input()) irane=set() ans=0 for i in range(h): for ipp in range(w): if rotti[i][ipp]=="." or str(i)+"a"+str(ipp) in irane: continue stack=[[i,ipp]] irane.add(str(i)+"a"+str(ipp)) iti=0 while len(stack)>iti: a=stack[iti][0] b=stack[iti][1] #上 if a-1>=0 and rotti[a-1][b]=="#": stack.append([a-1,b]) rotti[a-1][b]="." #右上 if a-1>=0 and b+1<w and rotti[a-1][b+1]=="#": stack.append([a-1,b+1]) rotti[a-1][b+1]="." #→ if b+1<w and rotti[a][b+1]=="#": stack.append([a,b+1]) rotti[a][b+1]="." #右下 if b+1<w and a+1<h and rotti[a+1][b+1]=="#": stack.append([a+1,b+1]) rotti[a+1][b+1]="." #下 if a+1<h and rotti[a+1][b]=="#": stack.append([a+1,b]) rotti[a+1][b]="." #左下1 if a+1<h and b-1>=0 and rotti[a+1][b-1]=="#": stack.append([a+1,b-1]) rotti[a+1][b-1]="." #左 if b-1>=0 and rotti[a][b-1]=="#": stack.append([a,b-1]) rotti[a][b-1]="." #左上 if b-1>=0 and a-1>=0 and rotti[a-1][b-1]=="#": stack.append([a-1,b-1]) rotti[a-1][b-1]="." iti+=1 ans+=1 print(ans)
D問題 Printing Machine
この問題は、貪欲な方法で解くことができます。
具体的にどういう方法かと言うと、プリントできるようになっている賞品のうち、一番はやくプリントできなくなってしまう賞品にプリントしていく…という方法です。
優先度付きキューなどを使うとかんたんに解けます。
Pythonの自分のコード
import heapq amount=[] heapq.heapify(amount) n=int(input()) rotti=[] for i in range(n): a,b=map(int,input().split()) b+=a rotti.append([a,b]) rotti=sorted(rotti) t=0 count=0 iti=0 ans=0 while 1==1: if count==0 and iti<n: hako=rotti[iti][0] t=hako heapq.heappush(amount,rotti[iti][1]) iti+=1 count+=1 while iti<n and rotti[iti][0]==hako: heapq.heappush(amount,rotti[iti][1]) iti+=1 count+=1 if iti<n and t>=rotti[iti][0]: while iti<n and t>=rotti[iti][0]: heapq.heappush(amount,rotti[iti][1]) iti+=1 count+=1 if count==0: break count-=1 hako=heapq.heappop(amount) if hako>=t: t+=1 ans+=1 print(ans)
E問題 Our clients, please wait a moment
ダイクストラ法を使ってときます。
少しむずかしくなっているのが、移動手段が社用車と電車の２種類あって、社用車から電車に乗り換えることはできるというところです。
電車で都市Xについたときの最短時間と社用車で都市Xについたときの最短時間のそれぞれをダイクストラ法を使って求めていくことによって解くことができます。
Pythonの自分のコード
import heapq n,a,b,c=map(int,input().split()) rotti=[] for i in range(n): rotti.append(list(map(int,input().split()))) amount=[[100000000000000000]*2 for i in range(n)] #社用車、電車 irane=[] irane2=[] for i in range(n): irane.append(i+1) irane2.append(i+1) amount[0][0]=0 amount[0][1]=0 stack=[[0,1,0]] heapq.heapify(stack) count=len(stack) """ irane=set([1]) irane2=set([1]) """ while count>0: hako=heapq.heappop(stack) x=hako[0] y=hako[1] z=hako[2] if z==0: if not y in irane: count-=1 continue irane.remove(y) count-=1 for i in list(irane): hako=rotti[y-1][i-1]*a+amount[y-1][0] if amount[i-1][0]>hako: count+=1 amount[i-1][0]=hako heapq.heappush(stack,[amount[i-1][0],i,0]) hako=rotti[y-1][i-1]*b+c+amount[y-1][0] if hako<amount[i-1][1]: amount[i-1][1]=hako count+=1 heapq.heappush(stack,[amount[i-1][1],i,1]) continue if not y in irane2: count-=1 continue irane2.remove(y) count-=1 for i in list(irane2): hako=rotti[y-1][i-1]*b+c+amount[y-1][1] if hako<amount[i-1][1]: amount[i-1][1]=hako count+=1 heapq.heappush(stack,[amount[i-1][1],i,1]) print(min(amount[n-1][0],amount[n-1][1]))
最後までありがとうございました。
