概要

各時刻で 2 人の現在位置を1分ずつシミュレーションし、座標が一致した回数を数える問題です。
文字 L/R/S をそれぞれ \(-1/+1/0\) の移動量に変換して、順番に更新していけば解けます。

考察

重要なポイントは、「出会い」として数えるのが整数時刻 \(i\) の瞬間だけという点です。
つまり、各分の移動後の座標を見て、等しければ 1 回カウントします。途中ですれ違っても無視します。

例えば、ある1分で - 高橋: 0 → 1 - 青木: 1 → 0
のように交差しても、時刻の終わりでは一致していないので出会いではありません。

素朴な方法として「各時刻の位置を別配列に全部保存してから比較」もできますが、保存は不要です。
必要なのは「今の高橋の座標」「今の青木の座標」「出会い回数」だけなので、1回の走査で十分です。

制約は \(T \le 10^6\) なので、
- 各時刻を1回ずつ処理する \(O(T)\) は間に合う
- 2重ループのような \(O(T^2)\) は当然不可
となります。

アルゴリズム

1. 高橋の現在位置 tx = X、青木の現在位置 ay = Y、出会い回数 meet = 0 を用意。
2. \(i=0\) から \(T-1\) まで繰り返す。
   • A[i] に応じて tx を更新（L:-1, R:+1, S:0）
   • B[i] に応じて ay を更新
   • 更新後、tx == ay なら meet += 1
3. 最後に meet を出力。

移動量変換を delta() 関数にしておくと実装が見やすくなります。

計算量

• 時間計算量: \(O(T)\)
• 空間計算量: \(O(1)\)（入力文字列を除く）

実装のポイント

• 問題文より、時刻0はカウントしないので初期状態では比較しません。ループ内で移動後に判定します。

• S は移動量 0。delta 関数で L/R 以外を 0 として扱う実装は簡潔です。

• 入力サイズが大きいので、sys.stdin.readline を使うと安定して高速です。

  ソースコード

import sys

def delta(c: str) -> int:
    if c == 'L':
        return -1
    if c == 'R':
        return 1
    return 0  # 'S'

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

    tx = X
    ay = Y
    meet = 0

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

    print(meet)

if __name__ == "__main__":
    main()

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