概要

一次元のビリヤード台 \([0, M]\) 上で、各ショット後のボールの位置と、反射回数の合計を求めます。

反射を1回ずつシミュレーションすると距離 \(A_i\) が大きい場合に間に合わないため、「台を折り返さずに一直線に伸ばして考える」ことで、各ショットを \(O(1)\) で処理します。

考察

台を一直線に伸ばして考える

ビリヤードの反射は、次のように考えると扱いやすくなります。

区間 \([0, M]\) を何度も鏡のように反転して並べると、反射しながら動くボールは、伸ばした直線上ではただまっすぐ進んでいるだけとみなせます。

例えば、右向きに距離 \(A\) だけ進む場合、現在位置を \(pos\) とすると、伸ばした直線上での到達点は

\(pos + A\)

です。

左向きなら

\(pos - A\)

です。

あとは、その座標を元の区間 \([0, M]\) に折り返せば、実際の位置が分かります。

周期は \(2M\) なので、座標 \(x\) に対して

• \(r = x \bmod 2M\)
• \(r \leq M\) なら位置は \(r\)
• \(r > M\) なら位置は \(2M - r\)

となります。

例えば \(M = 10\) のとき、伸ばした座標と実際の位置は次のようになります。

伸ばした座標	実際の位置
\(0\)	\(0\)
\(5\)	\(5\)
\(10\)	\(10\)
\(12\)	\(8\)
\(17\)	\(3\)
\(20\)	\(0\)

反射回数の数え方

反射は、ボールが端点 \(0\) または \(M\) に到達し、まだ移動距離が残っているときに発生します。

伸ばした直線上では、端点に対応する場所はすべて

\(M\) の倍数

です。

つまり、移動中に通過する \(M\) の倍数の個数を数えれば、反射回数が分かります。

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

• ショットの最後にちょうど端点に着いた場合は、そこで移動が終わるので反射しない
• 端点から外向きにショットした場合は、移動距離を消費せずに即反射し、これも数える
• \(A_i = 0\) の場合は、反射も移動も発生しない

そのため、数える区間の端を少し調整する必要があります。

素朴な方法が遅い理由

反射するたびに位置と方向を更新する方法では、1回のショットで最大 \(A_i / M\) 回程度の反射が発生します。

制約では

\(A_i \leq 10^9\), \(N \leq 2 \times 10^5\)

なので、反射を1回ずつ処理すると最悪で非常に大きな回数になり、TLEになります。

そこで、各ショットについて「何個の \(M\) の倍数を通過するか」を数式で一気に求めます。

アルゴリズム

現在位置を \(pos\)、反射回数の合計を \(reflections\) とします。

また、周期を

\(period = 2M\)

とします。

\(M\) の倍数の個数を数える

整数区間 \([lo, hi]\) に含まれる \(M\) の倍数の個数を求める関数を考えます。

これは

\(\left\lfloor \frac{hi}{M} \right\rfloor - \left\lceil \frac{lo}{M} \right\rceil + 1\)

で求められます。

コードでは次の関数です。

def count_multiples(lo, hi):
    if lo > hi:
        return 0
    return hi // M - ((lo + M - 1) // M) + 1

\(lo > hi\) の場合は空区間なので \(0\) 個です。

右向きのショット

右向き、距離 \(A\) の場合、伸ばした直線上での終点は

\(end = pos + A\)

です。

反射は \(M\) の倍数を通過したときに発生します。

ただし、最後の点 \(end\) がちょうど \(M\) の倍数でも、そこでは移動が終わるので反射しません。

したがって、基本的には \([pos+1, end-1]\) にある \(M\) の倍数を数えます。

ただし、開始位置が \(M\) で右向きの場合は、外向きなので即反射します。

その場合は開始点 \(pos\) も含めて数えます。

if c == b'R':
    end = pos + A

    if pos == M:
        reflections += count_multiples(pos, end - 1)
    else:
        reflections += count_multiples(pos + 1, end - 1)

左向きのショット

左向き、距離 \(A\) の場合、伸ばした直線上での終点は

\(end = pos - A\)

です。

左向きでは座標が減っていくので、通過する範囲は \([end, pos]\) です。

ただし、最後の点 \(end\) は反射しないため除外します。

基本的には \([end+1, pos-1]\) にある \(M\) の倍数を数えます。

ただし、開始位置が \(0\) で左向きの場合は、外向きなので即反射します。

その場合は開始点 \(pos\) も含めて数えます。

else:
    end = pos - A

    if pos == 0:
        reflections += count_multiples(end + 1, pos)
    else:
        reflections += count_multiples(end + 1, pos - 1)

最終位置の更新

伸ばした直線上での終点 \(end\) が分かったら、周期 \(2M\) で折り返します。

r = end % period

if r <= M:
    pos = r
else:
    pos = period - r

Python の % は負の数に対しても非負の余りを返すため、左向きに進んで \(end\) が負になってもそのまま使えます。

計算量

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

各ショットを定数時間で処理するため、全体で \(O(N)\) です。

実装のポイント

• \(A_i = 0\) のショットでは、位置も反射回数も変化しないため、最初に continue します。

• ショットの最後に端点へ到達しても反射は数えないので、終点は反射回数のカウント範囲から除外します。

• 端点から外向きにショットする場合は、開始時点での反射を数える必要があります。

• 反射回数は大きくなる可能性があるため、他言語では long long など 64 bit 整数を使う必要があります。

  ソースコード

import sys

input = sys.stdin.buffer.readline

N, M, pos = map(int, input().split())
period = 2 * M
reflections = 0

def count_multiples(lo, hi):
    if lo > hi:
        return 0
    return hi // M - ((lo + M - 1) // M) + 1

for _ in range(N):
    c, a = input().split()
    A = int(a)
    if A == 0:
        continue

    if c == b'R':
        end = pos + A
        if pos == M:
            reflections += count_multiples(pos, end - 1)
        else:
            reflections += count_multiples(pos + 1, end - 1)

        r = end % period
    else:
        end = pos - A
        if pos == 0:
            reflections += count_multiples(end + 1, pos)
        else:
            reflections += count_multiples(end + 1, pos - 1)

        r = end % period

    if r <= M:
        pos = r
    else:
        pos = period - r

print(pos, reflections)

---

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