概要

反射をそのままシミュレーションするのではなく、台を左右に鏡映して並べた「展開図」を考えると、ボールの動きはただの直線移動になります。
各ショットについて「境界を何回またいだか」を数え、最後に位置を \([0,M]\) に折り返せば、最終位置と反射回数を \(O(1)\) で求められます。

考察

この問題で厄介なのは、1 回のショット中に反射が何度も起こることです。

例えば \(M=1\)、\(A_i=10^9\) なら、1 回のショットだけで非常に多くの反射が起こりえます。
そのため、

• 1 マスずつ動かす
• 1 回反射するたびに処理する

といった素朴な方法は到底間に合いません。

重要な気づき：反射は「展開図」で一直線になる

区間 \([0,M]\) を、端で折り返す代わりに、左右に鏡映してずっと並べていくことを考えます。

例えば \(M=5\) なら、展開図上では

• \([0,5]\)
• \([5,10]\) は左右反転
• \([10,15]\)
• \([15,20]\) は左右反転
• …

という形になります。

この展開図では、実際には反射している動きが、ただの直線移動として表せます。

例

\(M=5\)、位置 \(2\) から右に \(9\) 進むとします。

実際の台では

• \(2 \to 5\) で反射
• \(5 \to 0\) で反射
• \(0 \to 1\)

となります。

一方、展開図では単に

• \(2 \to 11\)

と一直線に進むだけです。
この間に \(5,10\) という「長さ \(M\) ごとの境界」を 2 回またぐので、反射回数は 2 回だと分かります。

---

ただし、端点から外向きに打つケースに注意

問題文には特別ルールがあります。

• 位置が \(0\) で L
• 位置が \(M\) で R

のときは、距離を消費せずにただちに反転し、これも 1 回の反射です。

例えば

• \(x=0\) で L, \(A=6\)

なら、まずその場で 1 回反射し、その後右に 6 進みます。

この「その場反射」は、展開図で境界をまたいだわけではないので、別に 1 回加算してから、向きを反転したものとして処理します。

また、\(A_i=0\) のときは問題文で「反射も起こらない」と明記されているので、これは最初に除外します。

---

反射回数は「\(M\) の倍数を何個またいだか」

展開図上で、ショット開始位置を \(y_0\)、終了位置を \(y_1\) とします。

このとき、反射は「\(0, M, 2M, 3M, \dots\) のような境界」を通過するたびに 1 回起こります。

ただし注意点が 1 つあります。

• 終点がちょうど境界でも、そこで移動が終わるなら反射しない

問題文でも「端点に到達し、まだ移動距離が残っている場合」に反射するとあります。
したがって、終点そのものの境界は数えない必要があります。

右向きに進むとき

\(y_0 < y_1\) なら、反射回数は

\[ \left\lfloor \frac{y_1-1}{M} \right\rfloor - \left\lfloor \frac{y_0}{M} \right\rfloor \]

です。

\(y_1-1\) としているのは、終点 \(y_1\) がちょうど境界のときに数えないためです。

左向きに進むとき

\(y_1 < y_0\) なら、反射回数は

\[ \left\lfloor \frac{y_0-1}{M} \right\rfloor - \left\lfloor \frac{y_1}{M} \right\rfloor \]

となります。

---

最後の位置は \(2M\) 周期で折り返す

展開図上の位置 \(y_1\) が求まっても、実際の台の位置は \([0,M]\) に戻す必要があります。

反射のパターンは長さ \(2M\) で繰り返すので、

\[ r = y_1 \bmod 2M \]

とすると、

• \(0 \le r \le M\) なら、そのまま \(r\)
• \(M < r < 2M\) なら、折り返して \(2M-r\)

が実際の位置です。

つまり

\[ x = \begin{cases} r & (r \le M) \\ 2M-r & (r > M) \end{cases} \]

です。

アルゴリズム

各ショットごとに次を行います。

1. \(A_i=0\) なら何もせず次へ進む。
2. 現在位置を \(x\) とし、展開図上の開始位置を \(y_0=x\) とする。
3. 方向に応じて展開図上の終了位置 \(y_1\) を決める。
   • L のとき
     • もし \(x=0\) なら、その場反射を 1 回加算し、右に進むので \(y_1=x+a\)
     • そうでなければ \(y_1=x-a\)
   • R のとき
     • もし \(x=M\) なら、その場反射を 1 回加算し、左に進むので \(y_1=x-a\)
     • そうでなければ \(y_1=x+a\)
4. \(y_0\) と \(y_1\) の間で \(M\) の倍数を何回またぐかを数え、反射回数に加算する。
   • \(y_0<y_1\) なら $\( \left\lfloor \frac{y_1-1}{M} \right\rfloor - \left\lfloor \frac{y_0}{M} \right\rfloor \)$
   • \(y_1<y_0\) なら $\( \left\lfloor \frac{y_0-1}{M} \right\rfloor - \left\lfloor \frac{y_1}{M} \right\rfloor \)$
5. \(y_1\) を \([0,M]\) に折り返して新しい位置 \(x\) にする。
   • \(r = y_1 \bmod 2M\)
   • \(r \le M\) なら \(x=r\)
   • そうでなければ \(x=2M-r\)

これを \(N\) 回繰り返せばよいです。

計算量

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

実装のポイント

• \(A_i=0\) は最優先で除外します。端点で外向きでも、この場合は反射しません。

• 端点で外向きに打つときのその場反射は、境界通過とは別に 1 回加算します。

• 終点がちょうど境界のときは反射しないので、反射回数の式で \(y_1-1\) や \(y_0-1\) を使って調整しています。

• 展開図上の座標は負になることがありますが、Python の // と % はそのまま使って問題ありません。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    N = int(next(it))
    M = int(next(it))
    x = int(next(it))

    total_reflections = 0
    period = 2 * M

    for _ in range(N):
        c = next(it)
        a = int(next(it))

        if a == 0:
            continue

        y0 = x

        if c == b'L':
            if x == 0:
                total_reflections += 1
                y1 = x + a
            else:
                y1 = x - a
        else:  # c == b'R'
            if x == M:
                total_reflections += 1
                y1 = x - a
            else:
                y1 = x + a

        if y0 < y1:
            total_reflections += (y1 - 1) // M - y0 // M
        else:
            total_reflections += (y0 - 1) // M - y1 // M

        r = y1 % period
        x = r if r <= M else period - r

    print(x, total_reflections)

if __name__ == "__main__":
    main()

---

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