Overview

This problem can be solved by updating the current positions of the two people each minute and counting how many times their coordinates coincide.
Whether they pass each other in between does not matter — it suffices to only check at integer times \(1,2,\dots,T\).

Analysis

The key point in this problem is that a “meeting” is only counted at the moment after each minute’s movement is completed.

For example, consider:

• Takahashi: starts at coordinate \(0\), moves R
• Aoki: starts at coordinate \(1\), moves L

In this case, they pass each other during the movement, but:

• At time \(0\): positions are \(0\) and \(1\)
• At time \(1\): positions are \(1\) and \(0\)

Their positions do not coincide at any integer time. Therefore, in this case, the number of meetings is \(0\).

---

The displacement for each character can be interpreted as follows:

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

Then, at each minute, we simply:

• Update Takahashi’s current position
• Update Aoki’s current position

and check whether the two positions are equal after the update.

Naive Approach

For each time \(i\), one could compute the position by summing up all movements from time \(0\) to \(i\) from scratch.
However, doing this every time would cost up to \(O(T)\) per time step, resulting in \(O(T^2)\) overall.

Since the constraint is \(T \le 10^6\), \(O(T^2)\) is far too slow.

How to Solve It

As long as we know the current position, the position one minute later can be determined by just applying a single character’s update.
In other words, by incrementally updating the positions, each minute takes \(O(1)\), and the total time complexity becomes \(O(T)\).

Algorithm

1. Initialize Takahashi’s current position to \(X\) and Aoki’s current position to \(Y\).
2. Set the answer ans to \(0\).
3. For \(i=0\) to \(T-1\) in order:
   • Update Takahashi’s position according to \(A[i]\)
   • Update Aoki’s position according to \(B[i]\)
   • After the update, if the two positions are equal, increment ans by 1
4. Output ans.

Concrete Example

For instance, suppose:

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

The positions at each time are as follows:

• Time \(1\):
  • Takahashi: \(0 \to 1\)
  • Aoki: \(2 \to 1\)
  • They coincide, so count \(1\)
• Time \(2\):
  • Takahashi: \(1 \to 1\)
  • Aoki: \(1 \to 0\)
  • They do not coincide
• Time \(3\):
  • Takahashi: \(1 \to 0\)
  • Aoki: \(0 \to 0\)
  • They coincide, so count another \(1\)

The answer is \(2\).

Complexity

• Time complexity: \(O(T)\)
• Space complexity: \(O(1)\)

Implementation Tips

• Creating a function delta that converts L, R, S to \(-1, +1, 0\) respectively makes the implementation easier.

• Since the input size can be large, using sys.stdin.readline in Python is recommended for safety.

• strip() is used to remove trailing newline characters from the string.

• Time \(0\) is not counted, so the key point is to advance one character, update the positions, and then check for equality.

  Source Code

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()

---

This editorial was generated by gpt-5.4-high.