概要

各分ごとに 2 人の現在位置を更新し、その時点で座標が一致しているかを数えればよい問題です。
途中ですれ違うかどうかは関係なく、整数時刻 \(1,2,\dots,T\) だけを見れば十分です。

考察

この問題で大事なのは、「出会い」とみなすのは各分の移動が終わった時点だけ ということです。

たとえば、

• 高橋君: 座標 \(0\) から R
• 青木君: 座標 \(1\) から L

のような場合、移動の途中ではすれ違いますが、

• 時刻 \(0\) では \(0\) と \(1\)
• 時刻 \(1\) では \(1\) と \(0\)

であり、整数時刻では一致していません。したがって、この場合は 出会った回数は \(0\) 回 です。

---

各文字の移動量は次のように考えられます。

• L : \(-1\)
• R : \(+1\)
• S : \(0\)

すると、毎分ごとに

• 高橋君の現在位置
• 青木君の現在位置

を 1 回ずつ更新し、更新後に 2 人の位置が等しいかを調べればよいです。

素朴な考え方

各時刻 \(i\) について、「時刻 \(0\) から \(i\) までの移動」を毎回最初から合計して位置を求めることもできます。
しかしこれを毎回やると、各時刻ごとに最大 \(O(T)\)\(、全体で \)O(T^2)$ になってしまいます。

制約は \(T \le 10^6\) なので、\(O(T^2)\) は到底間に合いません。

どう解決するか

今いる位置さえ分かっていれば、次の 1 分後の位置は 1 文字ぶん更新するだけで求められます。
つまり、位置を 逐次更新 すれば各分あたり \(O(1)\) で済み、全体で \(O(T)\) になります。

アルゴリズム

1. 高橋君の現在位置を \(X\)、青木君の現在位置を \(Y\) で初期化する。
2. 答え ans を \(0\) にする。
3. \(i=0\) から \(T-1\) まで順に、
   • \(A[i]\) に応じて高橋君の位置を更新する
   • \(B[i]\) に応じて青木君の位置を更新する
   • 更新後、2 人の位置が等しければ ans を 1 増やす
4. ans を出力する。

具体例

たとえば、

• \(T=3\)
• \(X=0,\ Y=2\)
• \(A=\text{`RSL`}\)
• \(B=\text{`LLS`}\)

とします。

各時刻の位置は次のようになります。

• 時刻 \(1\)：
  • 高橋君 \(0 \to 1\)
  • 青木君 \(2 \to 1\)
  • 一致するので \(1\) 回
• 時刻 \(2\)：
  • 高橋君 \(1 \to 1\)
  • 青木君 \(1 \to 0\)
  • 一致しない
• 時刻 \(3\)：
  • 高橋君 \(1 \to 0\)
  • 青木君 \(0 \to 0\)
  • 一致するのでさらに \(1\) 回

答えは \(2\) です。

計算量

• 時間計算量: \(O(T)\)
• 空間計算量: \(O(1)\)

実装のポイント

• L, R, S をそれぞれ \(-1, +1, 0\) に変換する関数 delta を作ると実装しやすいです。

• 入力サイズが大きいので、Python では sys.stdin.readline を使うと安心です。

• 文字列の末尾の改行を除くために strip() を使っています。

• 時刻 \(0\) は数えないので、1 文字進めて位置を更新したあとで判定する のがポイントです。

  ソースコード

import sys

def delta(c):
    if c == 'L':
        return -1
    if c == 'R':
        return 1
    return 0

def main():
    input = sys.stdin.readline
    T, X, Y = map(int, input().split())
    A = input().strip()
    B = input().strip()

    tx, ay = X, Y
    ans = 0

    for i in range(T):
        tx += delta(A[i])
        ay += delta(B[i])
        if tx == ay:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。