概要

数直線上を移動する2人について、各時刻での座標の差を追跡し、差が \(0\) になる（同じ座標にいる）回数を数える問題です。

考察

2人の座標をそれぞれ個別に管理することもできますが、重要な気づきは 2人の座標の差（相対位置）だけに注目すればよい という点です。

時刻 \(0\) での座標の差は \(D = X - Y\) です。各時刻で高橋君と青木君がそれぞれ移動しますが、差 \(D\) がどう変化するかを考えます。

• 高橋君が R に移動 → \(D\) が \(+1\)（高橋君が正方向に離れる）
• 高橋君が L に移動 → \(D\) が \(-1\)
• 青木君が R に移動 → \(D\) が \(-1\)（青木君が正方向に動くと差は縮まる）
• 青木君が L に移動 → \(D\) が \(+1\)
• S（停止）→ 変化なし

つまり、高橋君の移動は差にそのまま影響し、青木君の移動は 逆向き に影響します。

毎時刻この差を更新し、\(D = 0\) となった回数を数えれば答えになります。

具体例

\(X = 3\), \(Y = 5\), \(A = \) RRL, \(B = \) LLS の場合：

時刻	高橋君の移動	青木君の移動	差 \(D\) の変化	\(D\)	出会い？
0	—	—	—	\(3 - 5 = -2\)	—
1	R (+1)	L (+1)	\(+2\)	\(0\)	✅
2	R (+1)	L (+1)	\(+2\)	\(2\)	❌
3	L (-1)	S (0)	\(-1\)	\(1\)	❌

答えは 1 回です。

素朴なアプローチとの比較

2人の座標を別々に管理しても同じ \(O(T)\) で解けますが、差だけを管理する方が変数が1つで済み、シンプルです。この問題では \(T \leq 10^6\) なので、\(O(T)\) の線形走査で十分間に合います。

アルゴリズム

1. 差 \(D = X - Y\) を初期化する。
2. \(i = 0, 1, \ldots, T-1\) について：
   • \(A[i]\) が R なら \(D\) に \(+1\)、L なら \(-1\)。
   • \(B[i]\) が R なら \(D\) に \(-1\)、L なら \(+1\)（高橋君とは逆向き）。
   • \(D = 0\) ならカウントを \(+1\)。
3. カウントを出力する。

計算量

• 時間計算量: \(O(T)\) — 文字列を1回走査するだけ
• 空間計算量: \(O(T)\) — 入力の文字列の格納分（差の管理自体は \(O(1)\)）

実装のポイント

• 高速な入力: \(T\) が最大 \(10^6\) と大きいため、Python では sys.stdin.buffer.read() を用いて一括読み込みすることで、入力のボトルネックを回避しています。

• 差の符号の向き: 青木君の移動は差に対して逆向きに作用する点に注意が必要です。例えば青木君が R（正方向）に動くと、差 \(X - Y\) は 減少 します。ここを間違えると WA になります。

• 整数オーバーフロー: \(X, Y\) の初期値が最大 \(\pm 10^9\) ですが、Python は多倍長整数なのでオーバーフローの心配はありません。C++ などでは long long を使いましょう。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    T = int(tokens[0])
    X = int(tokens[1])
    Y = int(tokens[2])
    A = tokens[3]
    B = tokens[4]
    
    diff = X - Y
    count = 0
    for i in range(T):
        a = A[i]
        b = B[i]
        if a == 'L':
            diff -= 1
        elif a == 'R':
            diff += 1
        if b == 'L':
            diff += 1
        elif b == 'R':
            diff -= 1
        if diff == 0:
            count += 1
    
    print(count)

main()

---

この解説は claude4.6opus-thinking によって生成されました。