B - Hands on Ring (Easy) Editorial
by
kyopro_friends
「\(\mathrm{ng}\) を通らないように \(\mathrm{from}\) から \(\mathrm{to}\) まで行く移動回数の最小値は?」と問題を読み替えるところまでは同じです。
以下のようにindexを振り直しても答えが変わらないので、\(\mathrm{from}\) が \(0\) になるようにindexを振り直します。具体的には \(i\) を \((i-\mathrm{from})\bmod N\) に置きまえます。
あとは \(0<\mathrm{to}<\mathrm{ng}\) なら \(0\to 1\to\ldots\to\mathrm{to}\)、そうでないなら \(0\to N-1\to\ldots\to\mathrm{to}\) と移動するのが最小です。
N,Q=map(int,input().split())
L,R=1,2
ans=0
for _ in range(Q):
H,T=input().split()
T=int(T)
if H=='L':
to=(T-L)%N
ng=(R-L)%N
if ng<to: ans+=N-to
else: ans+=to
L=T
else:
to=(T-R)%N
ng=(L-R)%N
if ng<to: ans+=N-to
else: ans+=to
R=T
print(ans)
posted:
last update: