概要

数直線上を移動する高橋君と青木君の \(T\) 分間の動きが与えられたとき、各整数時刻 \(i\) (\(1 \leq i \leq T\)) において 2 人の座標が一致する回数を求める問題です。

考察

この問題で重要なのは、2 人の絶対的な座標そのものではなく、「2 人の座標の差」に着目することです。

1. 座標の差の管理

高橋君の時刻 \(i\) における座標を \(x_i\)、青木君の座標を \(y_i\) とします。2 人が出会う条件は \(x_i = y_i\)、つまり \(x_i - y_i = 0\) となることです。 初期状態（時刻 0）の差を \(diff = X - Y\) とし、毎分の移動に応じてこの \(diff\) を更新していくことで、2 人が同じ場所にいるかどうかを判定できます。

2. 移動による差の変化

1 分間の移動で \(diff\) がどのように変化するかを考えます。 高橋君の移動を \(\Delta a\)、青木君の移動を \(\Delta b\) とすると（Lなら \(-1\)、Rなら \(+1\)、Sなら \(0\)）、新しい差は次のように計算できます。 $\(diff_{new} = diff_{old} + (\Delta a - \Delta b)\)$

例えば： - 高橋君が R (+1)、青木君が L (-1) に動いた場合：差は \(+1 - (-1) = +2\) 変化します。 - 2 人が同じ方向（例：共に L）に動いた場合：差の変化は \(-1 - (-1) = 0\) となり、相対的な距離は変わりません。

3. 注意点

• 時刻 0 はカウントしない: 問題文に「時刻 0 も対象に含みません」とあるため、初期状態で \(X=Y\) であっても、それはカウントに含めないよう注意が必要です。
• 移動の途中は無視: 1 分間の移動の最中にすれ違ったとしても、それは「出会い」とは見なしません。あくまで整数時刻 \(i\) での座標のみをチェックします。

アルゴリズム

1. 2 人の座標の差の初期値 diff = X - Y を計算し、出会った回数 meet_count = 0 を用意します。
2. 時刻 \(i = 1\) から \(T\) まで、以下の操作を繰り返します。
   • 文字列 \(A\) の \(i\) 文字目と \(B\) の \(i\) 文字目を確認します。
   • 高橋君の移動に応じて diff を加減算します。
   • 青木君の移動に応じて diff を加減算します（青木君が正の方向に動くと差は縮まるため、引き算になります）。
   • diff == 0 であれば、meet_count を 1 増やします。
3. 最終的な meet_count を出力します。

計算量

• 時間計算量: \(O(T)\) 文字列の長さ \(T\) に対して 1 回のループで処理が終わるため、非常に高速です。\(T \leq 10^6\) ですが、Python の単純なループであれば十分制限時間内に間に合います。
• 空間計算量: \(O(T)\) 入力された移動経路の文字列を保持するために \(O(T)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(T\) が大きいため、Python では sys.stdin.read().split() を使って一括で入力を読み込むと効率的です。

• zip関数の活用: 2 つの文字列 \(A, B\) を同時にループで回す際、zip(a_moves, b_moves) を使うとコードを簡潔に書くことができます。

• 条件分岐の最適化: 2 人が同じ移動（ma == mb）をしたときは diff が変化しないため、その処理をスキップすることでわずかに高速化できます。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、空白で分割して取得します。
    # T: 時間, X: 高橋君の初期座標, Y: 青木君の初期座標, A: 高橋君の移動, B: 青木君の移動
    input_data = sys.stdin.read().split()
    if len(input_data) < 5:
        return
    
    t = int(input_data[0])
    x = int(input_data[1])
    y = int(input_data[2])
    a_moves = input_data[3]
    b_moves = input_data[4]
    
    # 高橋君と青木君の現在の座標の差 (高橋 - 青木) を管理します。
    # 初期時刻 (時刻 0) の差を計算します。
    diff = x - y
    meet_count = 0
    
    # 各時刻 i (1 から T) における移動を順番に処理します。
    # zip を使用して文字列 A と B の各文字を同時に取り出します。
    for ma, mb in zip(a_moves, b_moves):
        # 高橋君と青木君の移動が異なる場合のみ、座標の差を更新します。
        # 同じ移動（例：共に 'L'）をした場合、相対的な差は変わりません。
        if ma != mb:
            # 高橋君の移動による差の変化
            if ma == 'L':
                diff -= 1
            elif ma == 'R':
                diff += 1
            
            # 青木君の移動による差の変化
            # (高橋 - 青木) なので、青木君が正の方向に動くと差は減少し、負の方向に動くと増加します。
            if mb == 'L':
                diff += 1
            elif mb == 'R':
                diff -= 1
        
        # 時刻 i における座標が等しい（差が 0）かどうかを判定します。
        if diff == 0:
            meet_count += 1
            
    # 出会った回数を出力します。
    sys.stdout.write(str(meet_count) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。