\(Q\) 個の指示を順番に見ていきながら、現在の左手・右手の位置、および今までに行なった操作回数の最小値を管理することを考えます。手の位置の管理は簡単なので、この問題を解く上でメインとなるのは、以下のようなクエリに答えるためのプログラムを書くことです。

• \(1\) 以上 \(N\) 以下の整数 \(\mathrm{from},\mathrm{to},\mathrm{ng}\) が与えられる。円環上でパーツ \(\mathrm{from}\) からパーツ \(\mathrm{to}\) まで、パーツ \(\mathrm{ng}\) を通らないように移動したいとき、移動回数の最小値は？（ただし、\(\mathrm{from}\neq\mathrm{ng},\mathrm{to}\neq\mathrm{ng}\) が保証される）

これは、\(\mathrm{from},\mathrm{to},\mathrm{ng}\) の大小関係によって場合分けをすることで解くことができます。\(3\) つの整数の大小関係は \(6\) 通りあるので、それらすべてを分けて考えてもよいですが、以下のようにすると \(2\) 通りの場合分けで済み簡潔です。

まず、\(\mathrm{from},\mathrm{to}\) は入れ替えてしまっても問題ない（すなわち、\(\mathrm{from}\) から \(\mathrm{to}\) に移動しても \(\mathrm{to}\) から \(\mathrm{from}\) に移動しても移動回数は変わらない）ことに着目します。これにより、\(\mathrm{from}>\mathrm{to}\) の場合は \(\mathrm{from}\) と \(\mathrm{to}\) を入れ替えることで、常に \(\mathrm{from}\leq \mathrm{to}\) を満たすようにすることができます。（このように、固定できる大小関係を固定しておくことで場合分けを減らすテクニックはしばしば有効です。）

あとは \(\mathrm{ng}\) がどこにあるかが問題ですが、これは本質的には \(2\) 通りしかありません：\(\mathrm{from}<\mathrm{ng}<\mathrm{to}\) である場合とそれ以外の場合です。

前者については、\(\mathrm{from}\rightarrow\mathrm{(from-1)}\rightarrow\dots\rightarrow 1 \rightarrow N\rightarrow \dots\rightarrow \mathrm{(to+1)}\rightarrow\mathrm{to}\) と移動するのが最適なので、移動回数は \((\mathrm{from}-1)+1+(N-\mathrm{to})=N+\mathrm{from}-\mathrm{to}\) です。

後者については、\(\mathrm{from}\rightarrow\mathrm{(from+1)}\rightarrow\dots\rightarrow \mathrm{(to-1)}\rightarrow\mathrm{to}\) と移動するのが最適なので、移動回数は \(\mathrm{to}-\mathrm{from}\) です。

よって、この場合分けを実装することで本問題を \(O(N)\) で解くことができます。

実装例 (C++) :

#include <bits/stdc++.h>

using namespace std;

int num_move(int n, int from, int to, int ng) {
    if (from > to) swap(from, to);
    if (from < ng and ng < to) {
        return n + from - to;
    } else {
        return to - from;
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    int l = 1, r = 2;
    int ans = 0;
    for (int i = 0; i < q; i++) {
        char h;
        int t;
        cin >> h >> t;
        if (h == 'L') {
            ans += num_move(n, l, t, r);
            l = t;
        } else {
            ans += num_move(n, r, t, l);
            r = t;
        }
    }
    cout << ans << endl;
}

実装例 (Python) :

def num_move(n, from_, to, ng):
    if from_ > to:
        from_, to = to, from_
    if from_ < ng < to:
        return n + from_ - to
    else:
        return to - from_

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':
        ans += num_move(n, l, t, r)
        l = t
    else:
        ans += num_move(n, r, t, l)
        r = t

print(ans)