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: