AtCoder Beginner Contest 170(ABC170) A～F解説
AtCoder Beginner Contest 170(ABC170)のA～Fまでの解説です。
コンテスト中はA～Eまでを解き(68:26+3WA)、Eが少し易しめだったこともありレート微増に終わりました。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc170/
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc170/editorial.pdf
A問題:
5個の変数のそれぞれについて、どの変数が0になっているかを確かめればよいです。
単にif文を5つ書く、変数を配列として受け取りfor文の中でif文を用いる、配列中に0が存在することが保証されているので配列中の0の位置を検索する、などの方法で実装を行うことができます。
B問題:
いわゆる鶴亀算の問題です。
制約が小さいので、鶴をk(0<=k<=X)匹、亀をX-k匹としたときの足の数をそれぞれ計算し、Yに等しくなるような(k,X-k)の組があるかをfor文により全探索して確かめればよいです。
あるいは、Y<2*XまたはY>4*XまたはY%2==1を満たすときは明らかに不可能、そうでないときは可能であると判定する方法でも解くことができます。
C問題:
整数列{pi}に含まる可能性のない整数のうち、0未満の数について0とXとの差の絶対値より小さくなることはなく、同様に101より大きい数について101とXとの差の絶対値より小さくなることはありません。
このことから、解の候補として0から101までの整数のみを見ればよいことが分かります。
ただ、上記のように問題ごとに探索すべき正確な範囲を考えるのは面倒です。
正確な範囲が分からずとも、代わりに正確な範囲を含む十分大きな範囲(例えば-1000<=k<=1000)について、整数列{pi}に含まれないもののうち、Xとの差の絶対値が最小となる整数のうち最も小さいものを全探索で求めれば十分です。
piの個数の制約が小さいので、各kについてpiと一致しないかを全探索しO(N)で毎回判定することでも解くことができますが、{pi}を集合型などで管理することで、kが{pi}に含まれるかをO(logN)で判定でき処理を高速化できます。
実装の際はN=0のケース、すなわちpiの行が空行になるケースに注意してください(Pythonなど、言語によっては空行の読み込みでエラーとなる場合があります)。
サンプルコード(Python):
https://atcoder.jp/contests/abc170/submissions/14294977
x,n=map(int,input().split())
if n!=0: #空行の読み込みを回避、処理を高速化するためにpiを集合型で管理する
s=set(list(map(int,input().split())))
else:
s=[]
diff=10**18
ans=10**18
for i in range(-10000,10000): #十分大きな範囲の整数について確かめる
if i in s: #{pi}に含まれる場合は計算を行わない
continue
else:
if abs(x-i)<diff: #Xとの差の絶対値が最小になるものを求める
ans=i
diff=abs(x-i)
print(ans)
D問題:
明らかに、数列{Ai}の順序は答えに影響を及ぼさないので、Aiを小さい順にソートした列について考えます。
ここで、あるAiが条件を満たさないとき、数列中にAiを割り切る数Ajが存在します。
これを逆に見ると、各Aiについて、Aiより大きいAiの倍数すべては、Aiで割り切ることができます。
したがって、各Aiについて、Aiより大きいAiの倍数を10^6以下の範囲ですべて列挙し、最後に各Aiが列挙した値に含まれているかを判定することで、この問題を解くことができます。
各Aiについて、同じ値の倍数は1回だけ列挙すれば十分であること、Aiがすでに列挙した値に含まれている場合はその倍数を求める必要がないこと(∵AjがAiで割り切れるとき、Ajの倍数はすべてAiの倍数です)から、調和級数での近似により上記の処理の計算量がO(max(Ai)log(max(Ai))+NlogN)であることが分かります。
ただし、同じ値が複数回現れるとき、その値は1度だけ処理することと、その値が答えにならないことに注意します(∵AiはAi自身を割り切ります)。
具体的には、ある数Aiを見るとき、その数が数列に複数個含まれる場合は、Ai自身も列挙した数に加えればよいです。
サンプルコード(Python):
https://atcoder.jp/contests/abc170/submissions/14416682
import collections
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #小さい順にソートしておく
s=set()
cnt=collections.Counter(arr) #各要素の個数を事前に数えておく
for i in range(n):
if arr[i] in s: #Aiがすでに列挙した数に含まれていれば処理を行わない
continue
if cnt[arr[i]]>=2: #Aiが2個以上含まれているとき、Ai自身を列挙した数に加える
s.add(arr[i])
for j in range(2,10**6//arr[i]+1): #Ai自身を除くAiの倍数を列挙する
s.add(arr[i]*j)
ans=0
for i in range(n): #列挙した数に含まれないAiの個数を数える
if arr[i] in s:
continue
ans+=1
print(ans)
E問題:
各園ごとの最高レートの管理と、各時点での各園の最高レートのうちの最小値の管理が必要になる問題です。
具体的には、移動元の園児のレートの削除、移動先の園児のレートの追加、各園ごとの最高レートの取得、各園の最高レートの書き換え、各園の最高レートのうちの最小値の取得の5つが行えればよいです。
平衡二分木では上記の操作をすべてO(logN)で行うことができることから、平衡二分木が実装されている場合はこれを用いることで、この問題をO(QlogN)で解くことができます。
また平衡二分木を用いない場合でも、O(QlogN)でこの問題を解くことができます(例えばhttps://qiita.com/Salmonize/items/638da118cd621d2628d1が参考になります)。
以下にその方法を述べます。
まず、各時点での各園の最高レートのうちの最小値の管理は、各園の最高レートの書き換えと最小値の取得がO(logN)で行えればよいので、例えばセグメント木などを用いて各園の最高レートを管理することで、クエリごとにO(logN)で求めることができます。
また、各園ごとの最高レートの管理には要素の削除・追加・最高値の取得の3つの操作をO(logN)で行えることが必要です。
これは一見平衡二分木によらなければ不可能であるように見えますが、この問題の場合は例えば優先度付きキューを上手く使うことでトータルO(QlogN)で上記の操作を行うことができます。
例えば、各園ごとに優先度付きキューにより最高レートを管理し、また各園ごとにいなくなった園児の集合を管理しておきます。
そして、クエリごとに移動元の集合に移動する園児の番号を追加、移動先の集合から移動する園児の番号を存在すれば削除するという操作を行い、その後、移動先の園について優先度付きキューから最大レートを取り出し、移動元の園について優先度付きキューから最大レートを取り出すという操作を行います。
ここで、移動元の園については、取り出した最大レートが園にいない園児のものだった場合は読み捨てる、という操作を繰り返して最大レートを求めます。
クエリごとにいなくなった園児の集合の長さが1増加するので、読み捨てる回数は高々Q回であることが分かります。
以上よりトータルO(QlogN)で各園ごとの最高レートを管理できることが分かりました。
各園ごとの最高レートの管理と各園の最高レートのうちの最小値の管理をそれぞれトータルO(QlogN)で行えることが分かったので、この問題をO(QlogN)で解くことができることが示せました。
サンプルコード(Python):
https://atcoder.jp/contests/abc170/submissions/14416787
import heapq
import sys
input=sys.stdin.readline
class SegmentTreeMin(): #区間minを求めるセグメント木
def __init__(self,n,init):
self.offset=2**((n-1).bit_length())
self.tree=[init]*(2*self.offset)
self.init=init
def update(self,pos,val):
pos+=self.offset
self.tree[pos]=val
while pos>1:
pos=pos//2
self.tree[pos]=min(self.tree[2*pos],self.tree[2*pos+1])
def query(self,l,r):
l+=self.offset
r+=self.offset
ret=self.init
while l<=r:
ret=min(ret,self.tree[r])
r=(r-1)//2
ret=min(ret,self.tree[l])
l=(l+1)//2
return ret
n,q=map(int,input().split())
items=[[] for _ in range(2*10**5+1)] #各園ごとの最大値を管理する優先度付きキュー
sets=[set() for _ in range(2*10**5+1)] #優先度付きキューで要素の削除を再現するための各園ごとの集合型
values=[[0,0] for _ in range(n+1)] #i番目の幼児のレートと所属する園
lens=[0]*(2*10**5+1) #それぞれの優先度付きキューの長さ
maxs=SegmentTreeMin(2*10**5+1,10**18) #各園の最高レートを管理するセグメント木
for i in range(n):
a,b=map(int,input().split())
values[i+1][0]=a
values[i+1][1]=b
lens[b]+=1
heapq.heappush(items[b],(-a,i+1))
for i in range(1,2*10**5+1): #各園に園児がいる場合、その園の最高レートを求めセグメント木の要素を書き換える
if lens[i]==0:
continue
tmp,num=heapq.heappop(items[i])
maxs.update(i,-tmp)
heapq.heappush(items[i],(tmp,num))
for _ in range(q): #クエリごとの処理
c,d=map(int,input().split())
prev=values[c][1]
values[c][1]=d
sets[prev].add(c) #移動元の園からc番目の幼児がいなくなったことを記録する
if c in sets[d]: #移動先の園にc番目の幼児がいなくなったことが記録されている場合、それを取り消す
sets[d].discard(c)
heapq.heappush(items[d],(-values[c][0],c))
lens[d]+=1
dmax,num=heapq.heappop(items[d])
maxs.update(d,-dmax) #移動先の園の最高レートを求めセグメント木の要素を書き換える
heapq.heappush(items[d],(dmax,num))
tmp=-10**18
while lens[prev]!=0:
prevmax,num=heapq.heappop(items[prev])
if num in sets[prev]: #取り出した最高レートがいなくなった園児のものの場合、その値を読み捨てる(この操作は高々O(Q)回しか起こらない)
lens[prev]-=1
else: #いなくなっていない園児のものの場合、その値でセグメント木の要素を書き換える
tmp=prevmax
heapq.heappush(items[prev],(prevmax,num))
break
maxs.update(prev,-tmp)
print(maxs.query(1,2*10**5)) #クエリごとの各園の最高レートのうちの最小値を出力する
F問題:
まず、各マスにおいて4方向に1～Kマス進むような愚直なBFSを考えます。
この計算量はO(HWK)ですが、各マスに到達するまでのコストを保持することにすると、明らかに、移動元のマスのコストが移動先のマスのコスト以上のとき、そのマスに移動する意味はありません(∵移動先のマスはすでにより小さいコストで探索されており、かつ移動元のマスとしてキューに追加されています)。
さらに、このようなマスがあるとき、そのマスを超えて進む意味もありません(∵そのようなマスからそのマスの先に進んだほうがコストが真に小さくなります)。
したがって、上記の条件をBFSの条件判定に加えることにします。
ここで、上記の条件を満たさないとき移動元のマスとしてキューに追加することにすると、移動元のキューに追加されるのは(移動元のマスのコスト)+1<=(移動先のマスのコスト)を満たすときですが、(移動元のマスのコスト)+1=(移動先のマスのコスト)となるとき、そのマスは同じ方向への移動で複数回キューに追加されることになります。
例えば、K=10^4、H=1,W=10^5のような盤面を考えると、x座標が10^4<=x<=10^5-10^4のマスについて、同じマスが10^4回キューに追加されることになり、明らかにTLEします。
これを回避するためには、移動元のマスとしてキューに追加する条件から(移動元のマスのコスト)+1=(移動先のマスのコスト)を除けばよいです。
すなわち、移動元のマスとしてキューに追加する条件を、(移動元のマスのコスト)+1<(移動先のマスのコスト)を満たすときとすればよいです。
このようにすると、同じ方向から移動したときには高々1回しか各マスがキューに追加されず、あるマスに到達する移動方向は4方向しかないので、計算量がO(HW)となりこの問題を解くことができました。
サンプルコード(Python):
https://atcoder.jp/contests/abc170/submissions/14417014
import collections
h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split()) #座標の表現が(y,x)の形式であることに注意する
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1 #以下では左上の座標を(0,0)としているので与えられた座標を-1しておく
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0 #スタート地点のコストは0
while len(q)!=0:
x,y=q.popleft()
c=cost[y][x]
for i in range(1,k+1): #盤面からはみ出す・障害物にぶつかる・スタート地点のコストと同じかそれ以下のマスに到達するのいずれかを満たすまで処理を続ける
if x+i<w and board[y][x+i]=='.' and c<cost[y][x+i]:
if cost[y][x+i]>c+1: #コストが真に小さくなるときその地点を新たなスタート地点に加えコストを更新する
cost[y][x+i]=c+1
q.append((x+i,y))
else:
break
for i in range(1,k+1):
if x-i>=0 and board[y][x-i]=='.' and c<cost[y][x-i]:
if cost[y][x-i]>c+1:
cost[y][x-i]=c+1
q.append((x-i,y))
else:
break
for i in range(1,k+1):
if y+i<h and board[y+i][x]=='.' and c<cost[y+i][x]:
if cost[y+i][x]>c+1:
cost[y+i][x]=c+1
q.append((x,y+i))
else:
break
for i in range(1,k+1):
if y-i>=0 and board[y-i][x]=='.' and c<cost[y-i][x]:
if cost[y-i][x]>c+1:
cost[y-i][x]=c+1
q.append((x,y-i))
else:
break
if cost[gy][gx]==10**18: #ゴール地点のコストが初期値のままであれば到達不可能
print(-1)
else: #そうでなければ最小コストを出力する
print(cost[gy][gx])
この記事が気に入ったらサポートをしてみませんか？