C - Lock All Doors 解説
by
kyopro_friends
番号が小さい部屋が左、大きい部屋が右にあるとします。
まず、最初にいる部屋より左に開いているドアがあれば、そのドアを操作できる部屋まで移動する必要があります。よって、そこまでのドアを一旦全て開くとしてよいです。同様に、最初にいる部屋より右に開いているドアがあれば、そこまでのドアを一旦全て開くとしてよいです。
そうすると、開いているドアは全てひと繋がりになるので、端から順に閉じていけばよいです。
例 1
1 0 1 0 0 1 1 0 1 1 1 ↓ ^ ここからスタート 1 0 0 0 0 0 0 0 1 1 1 ↓ 1 1 1 1 1 1 1 1 1 1 1
例 2
1 0 1 0 0 1 1 0 1 1 1 ↓ ^ ここからスタート 1 0 0 0 0 0 0 0 0 0 1 ↓ 1 1 1 1 1 1 1 1 1 1 1最初に開いていた最も左のドアの番号を \(i_L\)、最も右のドアの番号を \(i_R\) とすると、「一旦開く」が終わった時点で空いている最も左のドアの番号は \(\min(i_L,R+1)\)、最も右のドアの番号は \(\max(i_R,R)\) となります。よって、「一旦開く」での操作の回数はこの区間にある最初に閉じていたドアの個数であり、その後の操作回数はこの区間にあるドアの個数となります。
実装例(Python)
開いているドアのindexを右半開区間で保持していることに注意してください
N,S=map(int,input().split())
A=list(map(int,input().split()))
idx0=[i for i,a in enumerate(A) if a==0]
if len(idx0)==0:
print(0)
exit()
L=min(S,idx0[0])
R=max(S,idx0[-1]+1)
print(sum(A[L:R])+(R-L))
投稿日時:
最終更新: