概要

ビリヤード台 \([0, M]\) 上で、各ショット後のボールの位置と反射回数を求める問題です。
距離を 1 ずつシミュレーションせず、反射を「直線上の移動」として考えることで各ショットを \(O(1)\) で処理します。

考察

反射をそのままシミュレーションすると、例えば \(M=1, A_i=10^9\) のような場合に、1 回のショットだけで非常に多くの反射が起こります。
\(N\) も最大 \(2 \times 10^5\) なので、反射を 1 回ずつ処理すると間に合いません。

重要な考え方は、ビリヤード台を左右に鏡のように無限に並べることです。

例えば、台の長さが \(M\) のとき、実際の位置は次のように周期 \(2M\) で表せます。

• 無限直線上の座標を \(y\) とする
• \(y\) を \(2M\) で割った余りを \(r\) とする
• \(0 \leq r \leq M\) なら実際の位置は \(r\)
• \(M < r < 2M\) なら実際の位置は \(2M-r\)

つまり、反射しながら進む動きは、無限直線上をまっすぐ進む動きとして扱えます。

たとえば、現在位置が \(pos\) のとき、

• 右に距離 \(A\) 進むなら、無限直線上では \(pos + A\)
• 左に距離 \(A\) 進むなら、無限直線上では \(pos - A\)

を考えればよいです。

あとは、その座標を \([0,M]\) に折り返して戻せば、最終位置が分かります。

一方、反射回数は「無限直線上で \(M\) の倍数を通過した回数」として数えられます。
端点 \(0, M\) は、無限直線上では \(0, M, 2M, 3M, \dots\) のような \(M\) の倍数に対応します。

ただし、問題文の条件に注意が必要です。

• ショットの最後にちょうど端点に到達した場合、残り距離がないので反射しない
• 開始時に端点にいて、外向きに打つ場合は即座に反射し、1 回と数える
• ただし \(A_i=0\) の場合は、反射も移動も一切発生しない

このため、反射回数を数える区間の端点を慎重に扱います。

アルゴリズム

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

各ショットについて、まず \(A=0\) なら何もせず次に進みます。

位置の更新

無限直線上の座標 \(y\) に対して、実際の位置を返す関数を考えます。

周期は \(2M\) です。

\[ r = y \bmod 2M \]

ただし、\(y\) が負の場合もあるので、\(r\) は \(0 \leq r < 2M\) になるように調整します。

そのうえで、

\[ \text{pos} = \begin{cases} r & (r \leq M) \\ 2M-r & (r > M) \end{cases} \]

とすれば、反射後の実際の位置になります。

右に進む場合は \(y=pos+A\)、左に進む場合は \(y=pos-A\) として更新します。

反射回数の計算

右向きの場合

右向きに距離 \(A\) 進む場合、無限直線上では区間

\[ [pos, pos+A) \]

に含まれる \(M\) の倍数を数えます。

終点 \(pos+A\) は、そこで距離を使い切っていれば反射しないため含めません。

整数区間としては、\(M\) の倍数を

\[ pos \leq kM \leq pos+A-1 \]

の範囲で数えます。

これは次の式で求められます。

\[ \left\lfloor \frac{pos+A-1}{M} \right\rfloor - \left\lfloor \frac{pos-1}{M} \right\rfloor \]

ただし、\(pos=0\) かつ右向きの場合、開始地点 \(0\) は外向きではなく内向きに進むので反射ではありません。
そのため、この場合は \(1\) を引きます。

左向きの場合

左向きに距離 \(A\) 進む場合、無限直線上では区間

\[ (pos-A, pos] \]

に含まれる \(M\) の倍数を数えます。

終点 \(pos-A\) は含めません。
一方で、開始地点は外向きなら即時反射として数える可能性があるため含めます。

よって、個数は次の式です。

\[ \left\lfloor \frac{pos}{M} \right\rfloor - \left\lfloor \frac{pos-A}{M} \right\rfloor \]

ただし、\(pos=M\) かつ左向きの場合、開始地点 \(M\) から左に進むのは内向きなので反射ではありません。
そのため、この場合は \(1\) を引きます。

処理の流れ

各ショットについて次を行います。

1. \(A=0\) ならスキップ
2. 方向に応じて反射回数を \(O(1)\) で計算
3. 無限直線上で \(pos \pm A\) した座標を、折り返し関数で \([0,M]\) に戻す
4. 反射回数を合計に加える

計算量

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

各ショットを定数時間で処理するため、十分高速です。

実装のポイント

C++ の整数除算は、負の数に対して数学的な床関数 \(\lfloor x/y \rfloor\) ではなく、0 に近い方向へ切り捨てます。

今回の式では \(pos-A\) などが負になることがあるため、数学的な床除算を行う関数 floor_div を用意しています。

ll floor_div(ll a, ll b) {
    if (a >= 0) return a / b;
    return - ((-a + b - 1) / b);
}

また、負の座標を \(2M\) で割った余りも、C++ の % では負になることがあります。
そのため、折り返し関数では余りが負なら \(2M\) を足して、必ず \(0 \leq r < 2M\) になるようにしています。

ll reflect_pos(ll y, ll M) {
    ll mod = 2 * M;
    ll r = y % mod;
    if (r < 0) r += mod;
    if (r <= M) return r;
    return 2 * M - r;
}

反射回数の合計は最大で非常に大きくなるため、long long 型を使う必要があります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll floor_div(ll a, ll b) {
    if (a >= 0) return a / b;
    return - ((-a + b - 1) / b);
}

ll reflect_pos(ll y, ll M) {
    ll mod = 2 * M;
    ll r = y % mod;
    if (r < 0) r += mod;
    if (r <= M) return r;
    return 2 * M - r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll M, pos;
    cin >> N >> M >> pos;

    ll total = 0;

    for (int i = 0; i < N; i++) {
        char C;
        ll A;
        cin >> C >> A;

        if (A == 0) continue;

        ll cnt = 0;

        if (C == 'R') {
            cnt = floor_div(pos + A - 1, M) - floor_div(pos - 1, M);
            if (pos == 0) cnt--;
            pos = reflect_pos(pos + A, M);
        } else {
            cnt = floor_div(pos, M) - floor_div(pos - A, M);
            if (pos == M) cnt--;
            pos = reflect_pos(pos - A, M);
        }

        total += cnt;
    }

    cout << pos << ' ' << total << '\n';
    return 0;
}

---

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