1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2024-10-22

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

1. 愚直解

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. 距離の比較

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. ニ倍する

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. 円環の順序判定

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)$ であるマスがこの順序であるかは、

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

 の真偽と一致します。ながたかなさんの解説 でも有名になりましたね。

証明

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

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

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

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?