AtCoder Beginner Contest 158(ABC158) A～F解説

たのん

AtCoder Beginner Contest 158(ABC158)のA～Fまでの解説です。
バーチャル参加でA～Eの5完(69:56+3WA)、その後Fも解きました(パフォ1800相当なのでそれなりに上手くいった感じがします、本番でもこれくらいの成績を出せるようにしたいです)。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc158
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc158/editorial.pdf

A問題:

与えられた文字列の中にAとBの両方があれば、2つの鉄道会社の間にバスが運行することになります。
逆にいうと、与えられた文字列が'AAA'または'BBB'のときにはバスが運行することはありません。
したがって与えられた文字列が'AAA'もしくは'BBB'であれば'No'を、そうでなければ'Yes'を出力すればよいです。

B問題:

まず、A+B個のボールを何回まで長さがNを超えずに並べることができるかを考えます。
これはN/(A+B)の小数点を切り捨てた値に一致し、この回数をKとすると、列にはK*A個の青いボールが置かれることになります。
列にK*(A+B)個のボールを並べたとき、長さがNになるまであとN%(A+B)個のボールを並べることができます。
これがA以下であればA個の青いボールのうちN%(A+B)個しか置くことができず、Aより大きければA個の青いボールすべてを置くことができます。
したがって、この問題の答えはK*A+min(N%(A+B),A)と表すことができ、以上によりこの問題を解くことができました。
(B問題としては難しめの問題な印象でした)

C問題:

制約より、10%の消費税が100円以下となるのは税抜き価格が1009円以下のときなので、税抜き価格が0円から1009円までの範囲を全探索し、8%の消費税がA円、10%の消費税がB円となるものを求めればよいです(上限をわざわざ1009円にしなくとも、消費税が100円より大きくなるような適当な数を上限に取ればよいです)。

サンプルコード(Python)
https://atcoder.jp/contests/abc158/submissions/10758654

a,b=map(int,input().split())
ans=-1
for i in range(10000,-1,-1): #10000円から0円まで大きい順に調べる
 tax1=int(i*0.08)
 tax2=int(i*0.1)
 if tax1==a and tax2==b:
   ans=i
print(ans)

D問題:

実際に文字列の反転をシミュレートしようとすると、1回の反転につきO(|S|)かかってしまい、最悪の場合計算量がO(|S|Q)となり制限時間に間に合いません。
ここで、文字列を反転させる操作を奇数回行っているとき、すなわち文字列が反転した状態であるときと、操作を偶数回行っているとき、すなわち文字列が反転していない状態であるときで場合分けして考えます。
まず、文字列が反転していない状態のときは、先頭への文字の追加、末尾への文字の追加はそのまま行えばよいです。
また、文字列が反転した状態のときは、先頭への文字の追加を末尾への文字の追加に、末尾への文字の追加を先頭への文字の追加にそれぞれ置き換えればよいです。
先頭へ追加された文字は、追加された順と逆順に、末尾へ追加された文字は追加された順番と同順に並ぶので、上記の場合分けにしたがって先頭に追加された文字と末尾へ追加された文字を管理し、文字列を反転させる操作が最終的に偶数回行われているときは(先頭に追加された文字を逆順にした文字列)+(元の文字列)+(末尾に追加された文字列)を、奇数回行われているときはこの文字列を反転させたものを出力すればよいです。
この計算量はO(N+Q)となり、この問題を解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc158/submissions/10770030

s=input()
q=int(input())
head=[]
tail=[]
rev=False
for _ in range(q):
 tmp=list(input().split())
 if tmp[0]=='1': #文字列を反転させる操作のとき
   if rev==False: #反転していない状態であれば反転した状態にする
     rev=True
   else:
     rev=False #反転した状態であれば反転していない状態にする
 if tmp[0]=='2': #文字を追加する操作のとき
   if rev==False: #反転していない状態であれば、先頭への追加はそのまま先頭に、末尾への追加もそのまま末尾に追加する
     if tmp[1]=='1':
       head.append(tmp[2])
     if tmp[1]=='2':
       tail.append(tmp[2])
   if rev==True: #反転した状態であれば、先頭への追加は末尾への追加に、末尾への追加は先頭への追加に置き換える
     if tmp[1]=='1':
       tail.append(tmp[2])
     if tmp[1]=='2':
       head.append(tmp[2])
head=''.join(map(str,head))
tail=''.join(map(str,tail))
ans=head[::-1]+s+tail #答えは(先頭に追加した文字列の逆順)+(元の文字列)+(末尾に追加した文字列)となる
if rev==True: #もし最終的に文字列が反転した状態なら答えの文字列を反転させる
 ans=ans[::-1]
print(ans)

E問題:

すべての連続部分列がPで割り切れるかどうかを判定しようとするとO(N^2)かかってしまい制限時間に間に合いません。
ここで、右端の要素を右端とするN個の連続部分列について、それらの右端を左に動かしていくことですべての連続部分列が得られることから、このN個の連続部分列を用いてPで割り切れる連続部分列の個数を求めることを考えます。
これらの連続部分列を長さの順に1番目からN番目まで番号を付けることにすると、k番目の連続部分列から右からi個の要素を取り除いた部分列のあまりrem(k,i)は、rem(k,i)*10^i+d(N-i+1)*10^(i-1)+…+d(N)*10^0≡rem(k)(mod P)を満たします(ここでd(k)はk番目の文字の値、rem(k)はk番目の連続部分列のあまりを表します)。
rem(k,i)が0のとき、k番目の連続部分列から右からi個の要素を取り除いた部分列はPで割り切ることができ、これはrem(k)≡rem(k,i)*10^i+d(N-i+1)*10^(i-1)+…+d(N)*10^0≡d(N-i+1)*10^(i-1)+…+d(N)*10^0(mod P)と同値です。
したがって、rem(k)≡d(N-i+1)*10^(i-1)+…+d(N)*10^0を満たすkの個数を数えることで、右端がi番目の要素であるような連続部分列のうちPで割り切れるものの個数を求めることができます。
事前にrem(k)をO(N)で求め、連想配列であまりごとの個数を管理することにすると、rem(k)≡d(N-i+1)*10^(i-1)+…+d(N)*10^0を満たすkの個数をO(logP)で求めることができ、探索すべき要素をi(=右端)のみに絞ることができたのでこの問題をO(NlogP)で解くことができました。
ただし、rem(k,i)はk<=iのとき定義できないことから、iを進めるごとに連想配列のあまりがrem(i)となる個数を1減らす必要があります。
また、Pが2または5のときは、Pが10を割り切ることから、上記の方法を用いることができません。
このとき、文字列のi番目の要素を見たとき、それがPで割り切れるならばi番目の要素を右端とするすべての連続部分列はPで割り切れることが分かるので、i番目の要素がPで割り切れるのであれば答えにiを足すという操作を繰り返すことでO(N)でこの問題を解くことができます。
以上により、制限時間内にこの問題を解くことができることが分かります。

サンプルコード(Python):
https://atcoder.jp/contests/abc158/submissions/10770931

import collections
n,p=map(int,input().split())
s=input()
arr=[int(s[i]) for i in range(len(s))] #文字列の各文字をそれぞれ数字に変換しておく
if p==2 or p==5: #P=2,5のときは10を割り切るので連続部分列の右端のみを見ればよい
 ans=0
 for i in range(n):
   if arr[i]%p==0:
     ans+=i+1
 print(ans)
else: #Pが2でも5でもないとき
 dic=collections.defaultdict(int)
 tmp=0
 for i in range(n-1,-1,-1): #右端の要素を右端とする連続部分列のあまりを順に求める
   tmp+=arr[i]*pow(10,n-1-i,p)
   tmp%=p
   dic[tmp]+=1
 ans=0
 rem=0 #調べるあまりの値(初期値は0)
 for i in range(n-1,-1,-1):
   ans+=dic[rem]
   rem+=arr[i]*pow(10,n-1-i,p) #調べるあまりの値に(i番目の要素)*10^(n-1-i)を加える
   rem%=p
   dic[rem]-=1 #右端の要素が右端、i番目の要素が左端となる連続部分列のあまりの個数を1減らす
 print(ans)

F問題:

まず、それぞれのロボットをX座標の小さい順に並び替えておきます。
このとき、場合の数の遷移をDPで求めることを考えると、i番目のロボットを移動させないときの場合の数は、i+1～N番目までのロボットがなす場合の数に等しく、i番目のロボットを移動させたときの場合の数は、i+1番目以降のロボットでi番目のロボットを移動させたときの影響を受けないロボットの最小の番号をjとすると、j～N番目までのロボットがなす場合の数に等しくなります。
したがって、DP[i]=DP[i+1]+DP[j]として求めることができ、これを後ろから求めていくと、求める答えはDP[0]に等しくなります。
2分探索を用いてi番目のロボットがどのロボットまで影響を与えるかをO(NlogN)で求めておくと、i番目のロボットを移動させたときに影響を受けないロボットの最小の番号jは、(i～k番目のロボットが影響を与えるロボットの番号のうち最も大きいもの)+1となります(ここでkはi番目のロボットが影響を与えるロボットの最大の番号を表します)。
iを大きい順に見てjを求めることにすると、各iについてi～k番目のロボットが影響を与えるロボットの番号のうち最も大きいものを求めることは区間の最大値を求めることに相当し、愚直に求めると最悪の場合計算量がO(N^2)となり制限時間に間に合いませんが、セグメント木を用いて区間の最大値を求めると計算量がO(NlogN)となり、各iについてjを制限時間内に求めることができるようになります(セグメント木については次のスライドを参照してください→https://www.slideshare.net/iwiwi/ss-3578491)。
これを用いるとDPの計算はO(N)で行えるので、以上によりこの問題を解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc158/submissions/10771823

class SegmentTreeMax():
 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番目の要素を覆う要素すべてについて値を更新する
   pos+=self.offset
   self.tree[pos]=val
   while pos>1:
     pos=pos//2
     self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
 def query(self,l,r): #区間[l,r]での最大値を求める
   l+=self.offset
   r+=self.offset
   ret=self.init
   while l<=r:
     ret=max(ret,self.tree[r])
     r=(r-1)//2
     ret=max(ret,self.tree[l])
     l=(l+1)//2
   return ret

mod=998244353
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0]) #X座標の小さい順にソートする
st=SegmentTreeMax(n,0)
ranges=[0]*n
for i in range(n):
 x=arr[i][0]+arr[i][1] #各ロボットが到達できる最大の位置
 l=-1
 r=n
 while r-l!=1: #2分探索によりどのロボットまで影響するかを求める(0-indexed)
   mid=(l+r)//2
   if arr[mid][0]>=x:
     r=mid
   else:
     l=mid
 ranges.append(r-1) #i番目のロボットがr-1番目のロボットまで影響することを記録する
 st.update(i,r-1) #セグメント木のi番目の要素をr-1に更新する
for i in range(n-1,-1,-1):
 ranges[i]=st.query(i,ranges[i]) #区間[i,k]での番号の最大値を求める
 st.update(i,ranges[i]) #セグメント木のi番目の要素を上記の最大値に更新する
dp=[0]*(n+1)
dp[-1]=1 #DPの初期値は1(すべてのロボットを除いた場合に相当する)
for i in range(n-1,-1,-1):
 j=ranges[i]+1
 dp[i]=dp[i+1]+dp[j] #後ろから順にDP[i]=DP[i+1]+DP[j]として更新する
 dp[i]%=mod
print(dp[0])

この記事が気に入ったらサポートをしてみませんか？