Codeforces Round #637(Div.2) A～E解説
Codeforces Round #637 (Div.2)のA～Eまでの解説です。
今回も無事にA～Dまでの4完を達成しレートを伸ばすことができました＊
問題のアドレスは以下になります↓
https://codeforces.com/contest/1341
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/76479
A問題:
各袋の重さはa-bからa+bの間の任意の整数値を取るので、各袋の重さの総量もn(a-b)からn(a+b)の間の任意の整数値を取ることができます。
したがって、各袋の重さの総量がc-dからc+dの間に収まるためには、c-d<=n(a-b)<=c+dまたはc-d<=n(a+b)<=c+dを満たせばよく、各a,b,c,dについてこれを確かめればよいです。
サンプルコード(Python):
https://codeforces.com/contest/1341/submission/77769496
t=int(input())
for _ in range(t):
n,a,b,c,d=map(int,input().split())
if n*(a-b)>c+d or n*(a+b)<c-d: #上記の条件を満たさないのはc+d<n(a-b)またはn(a+b)<c-dのとき
print('No')
else:
print('Yes')
B問題:
長さNの配列を用意し、i番目の頂点がピークであるとき配列のi番目の要素を1、そうでないとき0とします。
その後、この配列の累積和acumを求めておきます。
すると、区間[l,r]について、もしr番目の頂点がピークであれば区間[l,r]に含まれるピースの個数はacum[r]-acum[l]-1に等しく、区間[l,r]に含まれるピークの個数はr番目の頂点がピークでなければacum[r]-acum[l]に等しくなります。
これを利用して、左端をn-k+1から1まで順に見ていき、ピークの個数が最大となる区間のうち左端が最も小さいものをO(N)で求めることができ、この問題をO(N)で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1341/submission/77782748
t=int(input())
for _ in range(t):
n,k=map(int,input().split())
arr=list(map(int,input().split()))
peaks=[0]*(n)
for i in range(1,n-1):
if arr[i]>arr[i-1] and arr[i]>arr[i+1]:
peaks[i]=1
acum=[0]
for i in range(1,n):
acum.append(acum[-1]+peaks[i])
maxs=0
pos=-1
for i in range(n-k,-1,-1):
tmp=acum[i+k-1]-acum[i]
if peaks[i+k-1]==1:
tmp-=1
if tmp>=maxs:
maxs=tmp
pos=i
print(maxs+1,pos+1)
C問題:
開始時点ではすべての場所のvalueが1に等しいので、任意の場所を候補に選ぶことができます。
ある場所を選んだとき、その場所がまだ塗られていない場所の右端以外にあれば、その場所の右隣のvalueのみが1増加します。
これから、ある場所を選んだとき、まだ塗られていない場所の右端に到達するまで今選んだ場所の右隣の場所を選び続けることになります。
右隣まで見たあとは、残った場所のvalueがすべて1に等しくなるので、また任意の場所を候補に選ぶことができるようになります。
この操作をすべての場所を選ぶまで続けます。
このような操作により選んだ場所の順番と与えられた数列の順番を一致させることができればYes、そうでなければNoを出力すればよいです。
この判定は事前に各要素の位置を求めておくことでO(N)で行うことができるので、この問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1341/submission/77866676
t=int(input())
for _ in range(t):
n=int(input())
arr=list(map(int,input().split()))
poss={}
for i in range(n):
poss[arr[i]]=i
poss[n+1]=0
right=n
start=poss[1]
pos=poss[1] #スタートするのは1がある場所から
next=1 #最初に見る数は1
while 1:
if arr[pos]==next: #今見ている場所にある数字が見るべき数に一致していれば1つ右隣に移動し、見るべき数を1増やす
pos+=1
next+=1
else: #一致していなければそのような数列を生成することはできない
print('No')
break
if pos==right: #まだ塗られていない地点の右端に到達したら、右端の位置を操作を開始した位置に変更し、スタートする場所を更新する
right=start
start=poss[next]
pos=poss[next]
if next==n+1: #1からNまでのすべての数を見ることができればそのような数列を生成することができる
print('Yes')
break
D問題:
類題としてMatch Matchingが挙げられます(ただしMatch Matchingの方が難しいです)。
桁数が固定であることから、上位の桁から順に可能な限り大きい数を取るのが最善であることは明らかです。
したがって、k桁目である数を取るとき、残った操作回数で(k+1)桁以降のすべての桁で数を作れるのであれば、その数を取るのが最善であることがわかります。
これから、事前にDPを用いて、末尾からi桁見たときにちょうどj回の操作回数ですべての桁で0～9までのいずれかの数を作ることができるかを判定しておけば、この問題を解くことができます。
具体的には、i桁目である数を作るコストがcのとき、DP[i][j-c]=TrueであればDP[i+1][j]=Trueとして更新します。
このDPは各桁について事前に0～9までの数を作るためのコストをO(N)で求めておくことで10*O(NK)で求めることができるので、この問題を10*O(NK)で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1341/submission/77835483
N,K=map(int,input().split())
arr=[list(input()) for _ in range(N)]
dp=[[False]*(K+1) for _ in range(N+1)]
dp[0][0]=True
costs=[[] for _ in range(2**7)]
digits=["1110111","0010010","1011101","1011011","0111010","1101011","1101111","1010010","1111111","1111011"]
for i in range(2**7): #あり得るすべての状態について、0～9までの数を作るコストを求める
bits=format(i,'b')
if len(bits)!=7:
bits='0'*(7-len(bits))+bits
for digit in digits:
tmp=0
for j in range(7):
if bits[j]=='0' and digit[j]=='1':
tmp+=1
elif bits[j]=='1' and digit[j]=='0':
break
else:
costs[i].append(tmp)
for i in range(2**7):
costs[i]=list(set(costs[i]))
for i in range(N): #末尾から各桁を見て、DPを更新していく
tmp=0
for k in range(7):
if arr[N-i-1][k]=='1':
tmp+=2**(6-k)
for j in range(K,-1,-1):
for c in costs[tmp]:
if j-c>=0 and dp[i][j-c]==True:
dp[i+1][j]=True
ans=''
for i in range(N): #先頭から各桁を見て、可能な限り大きい数を取っていく
for j in range(9,-1,-1):
cost=0
for k in range(7):
if arr[i][k]=='0' and digits[j][k]=='1':
cost+=1
elif arr[i][k]=='1' and digits[j][k]=='0':
break
else:
if K-cost>=0 and dp[N-i-1][K-cost]==True:
ans+=str(j)
K-=cost
break
else: #ある時点で1つも選べる数がないとき、与えられた桁をすべて0～9のいずれかの数にすることはできない
print(-1)
break
else: #操作が終了したとき、上記の操作で得られた数が答えとなる
print(ans)
E問題:
もしも各diからdjにちょうどg秒で移動できるかどうかが事前に分かっていれば、移動できる頂点間に重さ1の辺を張ることで、この問題を幅優先探索を用いてO(mg)で解くことができます(∵各diについて高々g個以下の場所にしか移動できないので、辺の本数は高々mg本になります)。
この判定は各diごとにO(mg)でナップサックDPを行うことで行うことができますが、これでは到底間に合いません。
そこで各diからdjにちょうどg秒で移動できるかどうかを事前に求めるのではなく、動的に判定することを考えます。
これは両隣の要素について、g-(現在の時刻%g)秒以内で到達できるかを判定すればよいです(∵各di,djについて|i-j|>=2のとき、必ずその間の要素を通るので、結局両隣のみの移動を考えれば十分です)。
この遷移について、diにt%g秒で到達したときの信号待ちの回数を配列を用いて管理することにすると、diに隣り合うd(i-1),d(i+1)について、t+abs(di-d(i+1))<=gかつd(i+1)に(t+abs(di-d(i+1))%g秒で到達したことがあるか, t+abs(di-d(i-1))<=gかつd(i+1)に(t+abs(di-d(i+1))%g秒で到達したことがあるかを判定し、この条件を満たす場合は遷移すればよいです。
遷移において信号待ちした回数を持っておくことにすると、t+abs(di-d(i+1))またはt+abs(di-d(i-1))がgに等しくなったとき、信号待ちした回数を1増やすことになります。
この遷移図は移動時に信号待ちした回数が0または1回増えるので、0-1BFSと呼ばれる処理を実装することで最短路を求めることができます。
具体的には、t+abs(di-d(i+1))またはt+abs(di-d(i-1))がg未満のときはその遷移をキューの先頭に、t+abs(di-d(i+1))またはt+abs(di-d(i-1))がgに等しいときはその遷移をキューの末尾に追加することで実現できます。
この処理では最大でdiにt%g秒で到達したときの信号待ちの回数を管理する配列のサイズだけ操作を行うことになり、この空間計算量はO(mg)に等しいことから、この問題をO(mg)で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1341/submission/78019122
import collections
n,m=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
g,r=map(int,input().split())
q=collections.deque()
q.append((0,0,0))
checked=[[-1]*(g) for _ in range(m)]
checked[0][0]=0
while len(q)!=0:
v,t,cnt=q.popleft()
if v!=m-1: #右端以外の地点にいるとき、右隣の地点への遷移が可能かどうかを判定する
cost1=arr[v+1]-arr[v]
if t+cost1<=g: #(現在の時刻)%g+(右隣の地点への移動時間)がg以下であり、かつ((現在の時刻)+(右隣の地点への移動時間))%gに右隣にいたことがなければ遷移する
if checked[v+1][(t+cost1)%g]==-1:
if t+cost1<g:
q.appendleft((v+1,t+cost1,cnt))
checked[v+1][t+cost1]=cnt
else: #移動した後の時刻がgに等しくなるとき、信号待ちの回数を1増やす
q.append((v+1,0,cnt+1)
checked[v+1][0]=cnt+1
if v!=0: #左端以外の地点にいるとき、左隣の地点への遷移が可能かどうかを判定する
cost2=arr[v]-arr[v-1]
if t+cost2<=g: #(現在の時刻)%g+(左隣の地点への移動時間)がg以下であり、かつ((現在の時刻)+(左隣の地点への移動時間))%gに左隣にいたことがなければ遷移する
if checked[v-1][(t+cost2)%g]==-1:
if t+cost2<g:
q.appendleft((v-1,t+cost2,cnt))
checked[v-1][t+cost2]=cnt
else: #移動した後の時刻がgに等しくなるとき、信号待ちの回数を1増やす
q.append((v-1,0,cnt+1))
checked[v-1][0]=cnt+1
ans=10**18
for i in range(m): #ある地点diからNまでg-(現在の時刻)%g秒以内に移動できるとき、((現在の時刻)%gにdiにいるときの最小の信号待ち回数)*(g+r)+(diからNまでの移動時間)が答えの候補となる
for j in range(g):
if checked[i][j]==-1:
continue
else:
if j+n-arr[i]<=g:
ans=min(ans,checked[i][j]*(g+r)+j+n-arr[i])
if ans==10**18: #Nに到達することができないとき、答えは-1
print(-1)
else: #そうでなければNに到達するまでの移動時間の最小値が答えとなる
print(ans)
この記事が気に入ったらサポートをしてみませんか？