円環における位置情報の捉え方【競技プログラミング】

はじめに

• AtCoderのABC376のb問題で、円環での位置情報を扱う必要があって、問題は解けたものの無駄に時間を使ってしまったので、今後、同様の問題に出会ったとき、どのように解けば良いかを整理する。

円環の問題

• ABC376のb問題は、
  • 輪っかを両手（左手、右手）で持つことを考える。
  • 輪っかにはN個の区切りがあり、初期状態で（左手、右手）の位置は、（１，２）となる。
    • 左手と右手は同じ位置を持つことは出来ない。
    • 片手を固定したまま、もう一方の手は区切りを１ずつ移動させることが出来るが、固定した方の手を飛び越えることは出来ない。
    • 作業指示（クエリ）は「R 4」の形で示され、この例では、右手の持ち手を「4」まで移動させる。
      • もし、両手の位置が初期状態の（１，２）だったとき、移動後の位置は（１，４）で移動数は２となる。
    • 全てのクエリを終わったときの、総移動数を求めよ。

事前整理なしにその場で考えたコード

• for文が存在するのが意味不明だと思いますが、位置関係が頭の中でこんがらがってしまったので、「移動する持ち手」と「固定する持ち手」を考え、固定する持ち手+i{i in 1...N-1}という形で位置を把握する方針としたためです。

let (N,Q) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]//2次元配列

var ans = 0
var (l,r) = (0,1)

for _ in 0..<Q {
    let (h,t) = [readLine()!.split(separator:" ").map{String($0)}].map{($0[0],Int($0[1])!-1)}[0]
    // print(h,t)

    if (h == "L" && t == l) || (h == "R" && t == r) {continue}

    if h == "L" {
        for p1 in r...r+N-1 {
            var p0 = l
            if l < r { p0 += N }
            if (p1 - t) % N == 0 { ans += abs(p1 - p0)  ; l = p1 % N ; break }
        }
    } else {
        for p1 in l...l+N-1 {
            var p0 = r
            if r < l { p0 += N }
            if (p1 - t) % N == 0 { ans += abs(p1 - p0) ; r = p1 % N ; break }
        }
    }
}

print(ans)

• 例として、左手クエリ(h == "L")の時を説明します。
  • p0を左手の最初の位置、p1を移動後の位置とします。
  • 始点を「固定持ち手」と考え、位置は「固定する持ち手+i{i in 1...N-1}」の世界観で把握するため、移動持ち手の初期位置が「固定持ち手」より小さければ、Nを加えました。
  • 「移動持ち手」の位置p1がクエリの指定位置tになったとき、移動距離を加算し、左手の位置を塗り替えました。
  • ポイントは、新しい位置を l = p1 % N で取得できるように、位置を0インデックスにしたことかな。
• 無意味なforループがある時点で終わってるけど、AC取れたから、まぁ、よし。

公式で紹介されている解法

• 移動距離を返す関数move(_ from:Int,_ to:Int,_ ng:Int)->Intを作る。
• from,to,ngはそれぞれ、移動持ち手の最初の位置、移動後の位置、固定持ち手の位置となる。

func move(_ from:Int,_ to:Int,_ ng:Int)->Int{
    var s = from // startのs
    var e = to // endのe
    if s > e {s = to ; e = from} // 強制的に「s <= e」とする
    if s < ng && ng < e {
        return s + N - e // s〜e間でngが邪魔するとき。「e⇒次の周のs」の距離
    } else {
        return e - s // 「s⇒e」の距離 (s=eの場合を含む)
    }
}

• 上記の関数は分かりやすくて良いね。手の位置について、1-インデックスでも、0-インデックスでも関係なく使える。
• とりあえず、当初の0-インデックスのままクエリ処理のコードを書くと、こんな感じ。

for _ in 0..<Q {
    let (h,t) = [readLine()!.split(separator:" ").map{String($0)}].map{($0[0],Int($0[1])!-1)}[0]
    if h == "L" {
        ans += move(l,t,r)
        l = t
    } else {
        ans += move(r,t,l)
        r = t
    }
}

print(ans)

提出コードからforループをなくす場合

• 提出コードからforループをなくして、移動距離を取得する方法としては、「移動持ち手の最初の位置」を起点として時計回りに､「移動後の位置」と「固定持ち手の位置」を取得し、どちらの方が近いかで判断すると言う手がある。
  • 「移動後の位置」の方が近いときは、「移動後の位置」ー「最初の位置」が移動距離となる。
  • 「固定持ち手の位置」の方が近いときは、「最初の位置＋N」ー「移動後の位置」が移動距離となる。
  • 上記の考え方だと、位置関係の差異しか利用していないので、0-インデックス、1-インデックスのどちらでも良い。
• 上記に基づいてコードを書く際、次の公式(なのかな？単なる事実？)を用いる。ちなみに、swiftでは、N足した後に、Nの余剰を出しているけど、swiftでは、負数の余剰が負数になっちゃうから。言語によっては、自動的に正の値の余剰を出してくれるみたいです。

N個のインデックス(時計回り)を持つ円環における位置の差分

• 　インデックスiからjへの時計回りの移動距離(正の値)は、( j - i + N ) % N
• 　逆回転で、iからjへの反時計回りの移動距離(正の値)は、( i - j + N ) % N

• 上記の考えに基づいてクエリ処理を書くと、

for _ in 0..<Q {
    let (h,t) = [readLine()!.split(separator:" ").map{String($0)}].map{($0[0],Int($0[1])!-1)}[0]
    var (next,ng) = (0,0) // 計算前だから、数値は何でも良い
    
    if h == "L" {
        next = (t - l + N) % N // 移動持ち手の最初の位置から、移動後の位置までの距離
        ng = (r - l + N) % N // 移動持ち手の最初の位置から、固定持ち手までの距離
        l = t
    } else {
        next = (t - r + N) % N
        ng = (l - r + N) % N
        r = t
    }
    
    if next > ng { 
        ans += N - next // 固定持ち手の方が近ければ、１周の移動距離 - next
    } else {
        ans += next // 移動後の位置の方が近ければ、当然next
    }
}

print(ans)

• うーむ、スッキリしていて良いね！
• この緑色のinfoで書いた公式もどきを知っていれば、もっと短時間で解けたはず！

最後に

• ABC376は、殆ど4完だったのに、このb問題のせいで時間を無駄に消費して、d問題のコードのミスを見つけられなかったよ。
• 今日、d問題の解説を見て、「あれ？自分の解答とロジックが全く同じじゃん？なんで例題の出力でズレが生じたの？」と思って、自分のコードをよく見たら、１分で単純なケアレスミスを見つけて、提出したらACだったよ。あ〜あ。
• 過去も円環問題では頭が混乱して無駄に時間を過ごして、最終的に強引に解いていた気がするから、今回得た基礎的な知識を元に、簡単に解いていきたい。