ABC376-B（Hands on Ring Easy）と円環の基本的な特性について

https://atcoder.jp/contests/abc376/tasks/abc376_b

　B 問題にしては結構むずかしめの問題が出ました。円環の基本的な性質についてまとめるいい機会になったので、まとめます。

# 1. 愚直解

```python
n,q = list(map(int, input().split(' ')))
hand = [1,2]
ans = 0
for i in range(q):
    h,t = input().split()
    t = int(t)
    idx = int(h=='R')
    now = hand[idx]
    other = hand[idx^1]
    collide = False
    cnt = 0
    while now != t:
        now = now%n + 1
        if now == other:
            collide = True
        cnt += 1
    if collide:
        ans += n - cnt
    else:
        ans += cnt
    hand[idx] = now
print(ans)
```

　カーソルを時計回りに進めていき、その途中で相手の位置を経過すれば（`collide`）衝突したと判定します。重要な性質として、**時計回りの経路+反時計回りの経路＝周期** となるので、衝突した時は **周期－時計回りの経路** を足せば良いです。

　基本的に円環は方向を固定（だいたい時計回りだと思いますが）して、反対方向の時は周期から差し引いた値をプラスする、と考えた方が、簡潔なコードになると思います。

　この問題の制約では問題になりませんが、この方法だと周期の長さだけシミュレーションが必要なので、制約が大きい場合は使えません。

# 2. 距離の比較

```python
n,q = list(map(int, input().split(' ')))
hand = [1,2]
ans = 0
for i in range(q):
    h,t = input().split()
    t = int(t)
    idx = int(h=='R')
    now = hand[idx]
    other = hand[idx^1]
    dist_to_target = (t-now)%n
    dist_to_other = (other-now)%n
    if dist_to_target < dist_to_other:
        ans += dist_to_target
    else:
        ans += n - dist_to_target
    hand[idx]=t 
print(ans)
```

　時計回りの距離を考えます。
 
　自分の位置を `now`、相手の位置を `other` とすると、`now < other` のときは自明に `other-now` です。`other < now` のときも実は `other - now`（に mod を取ったもの）になります。

　なので、まとめて `(other - now)%n` になります。

　そして、**相手との時計回りの距離＜ターゲットとの時計回りの距離** のとき、時計回りだと衝突することを意味します。これで $O(1)$ で衝突判定ができます。

# 3. ニ倍する

```python
from sortedcontainers import SortedSet,SortedList
n,q = list(map(int, input().split(' ')))
st = SortedSet([1,2,1+n,2+n])
hand = [1,2]
ans = 0
for i in range(q):
    h,t = input().split()
    t = int(t)
    idx = int(h=='R')
    now = hand[idx]
    other = hand[idx^1]
    if now == t:
        continue
    st.add(t)
    st.add(t+n)
    nearest = (st[st.bisect_right(now)]-1)%n + 1
    if nearest == t:
        ans += (t-now)%n
    else:
        ans += (now-t)%n
    hand[idx] = t
    st.remove(now)
    st.remove(now+n)
print(ans)
```

　ニ倍の配列（またはインデックス）を用意することにより、うまく処理できる問題も多いです。「自分の位置」と「自分の位置$+N$」のインデックスを記録しておくと、**自分の位置より時計回りに大きいマスが必ず存在する**ことが保証できます。（もし $N$ より大きいマスがヒットした場合は、mod を取ればよい）

　二分探索で、自分より時計回りに大きいマスの中で最も近いもの（`nearest`）がわかります。`nearest` がターゲットだった場合は衝突なし、そうでない場合は衝突ありです。マスに存在するコマの数を $M$ とすると、$O(\text{log}M)$ となるので、ほぼ定数倍とみなせるぐらい高速です。

# 4. 円環の順序判定

```python
n,q = list(map(int, input().split(' ')))
hand = [1,2]
ans = 0
for i in range(q):
    h,t = input().split()
    t = int(t)
    idx = int(h=='R')
    now = hand[idx]
    other = hand[idx^1]
    if (now-t)*(t-other)*(other-now) > 0:
        ans += (t-now)%n
    else:
        ans += (now-t)%n
    hand[idx] = t
print(ans)
```

　実は、時計回りの位置で $(a,b,c)$ であるマスがこの順序であるかは、

```math
(a-b)(b-c)(c-a)>0
```

　の真偽と一致します。[ながたかなさんの解説](https://atcoder.jp/contests/abc367/editorial/10712) でも有名になりましたね。

### 証明

　$a<b<c$ のときは、

```math
\displaylines{
a-b < 0 \\
b-c < 0 \\
c-a > 0
}
```

　より、正となります。ここで、ローテーションが起こり、$c<a<b$ となったときを考えます。**最大であった $c$ が最小になる** ので、$c$ が関わる不等式だけ正負が反転します。ちょうど $2$ つの正負が反転するので、この不等式の結果は変わりません。同様に、何回ローテーションが起こったとしても、正負が反転するのは $2$ つだけなので、不等式の結果は変わりません。