S歩すすんでT歩もどる系の問題

　ややこしいですよね。

- 最初は $0$ メートルの位置にいる
- 奇数回目のステップでは $3$ メートル進む
- 偶数回目のステップでは $2$ メートル戻る
- 累計ではじめて $6$ メートル以上進むのは何ステップ目か？

　こういうやつ。
 
　重要な事実として、「新記録を更新する際は必ず**奇数回目となる**」ことがあります。なぜなら、$2$ 以上の偶数回目である位置にいる場合、必ずそれ以前に戻った記録があるはずだからです。
 
　なので、答えとなるステップ数は必ず「$1,3,5,...,2k+1,...$」のどれかになります。

　あるステップ数 $2k+1$ に対し、進んだ距離は $(3-2)k+3=k+3$ なので、$k+3 \geq 6$ を満たす最小の整数 $k$ を求めた後の $2k+1$ が答えになります。上の例では、$2 \times 3+1 =7$ となります。

　実際に、各ステップごとの直後の位置は $(3,1,4,2,5,3,6)$ となり、正しいです。

# 一般化

　やや一般化します。

- 最初は $0$ メートルの位置にいる
- 奇数回目のステップでは $S$ メートル進む
- 偶数回目のステップでは $T$ メートル戻る（ただし、$S-T>0$）
- 累計ではじめて $L$ メートル以上進むのは何ステップ目か？

　これも同様に考えればよくて、サイクルをある回数 $k$ 繰り返した後に必ず奇数回のステップで目的を達成します。この $k$ は、

```math
k(S-T)+S\geq L
```
```math
k\geq\frac{L-S}{S-T}
```

　を満たす $0$ 以上の最小の整数なので、$\max(0,\lceil\frac{L-S}{S-T}\rceil)$ となります。
　よって、答えは、

 ```math
 2\cdot \max(0,\lceil\frac{L-S}{S-T}\rceil)+1
 ```

　となります。

# さらに一般化

　さらに一般化します。

- $(S_1,S_2,\cdots,S_N)$ というサイクルでステップを繰り返す（ただし、これらのステップの合計を $\sum S$ として、$\sum S>0$ ）
- 累計ではじめて $L$ 以上進むのは何ステップ目か？

 　$1$ 回のサイクルの中でピークに達するときの距離を $P$ とします。
 
　このとき、$k \sum S + P \geq L$ を満たす $0$ 以上の最小の $k$ について、$k+1$ 回目のサイクルで必ず初めて $L$ 以上に到達します。

 <details><summary>証明</summary>
まず、$L$ が $P$ 以下である場合を考えます。

これは、$P$ の定義から、確実に $1$ 回目のサイクルのどこかで到達します。

また、$P$ の定義から、逆も成り立ちます。つまり、$L$ が $P$ を超える場合、必ず $1$ 回を超えるサイクルが必要になります。

$1$ 回のサイクルを終えた後、歩行距離は $\sum S$ だけ進んでいます。

このとき、$L$ が $\sum S+P$ 以下である場合、確実 $2$ 回目のサイクルのどこかで到達します。 

同様の議論を繰り返していけば、$k \sum S + P \geq L$ を満たすような最小の $k$ について、$k+1$ 回目のサイクルで初めて目標に到達できます。 

</details>

　前段までと同じ計算により、$k$ は、

```math
k \sum S+P\geq L
```
```math
k\geq\frac{L-P}{\sum S}
```

　を満たす $0$ 以上の整数なので、$\max(0,\lceil\frac{L-P}{\sum S}\rceil)$ となります。

　サイクルの長さを $N$、その周期の中でちょうど目標を達成するインデックスを $\text{idx}$ とすると、答えは、

```math
N \cdot \max(0,\lceil\frac{L-P}{\sum S}\rceil) + \text{idx}
```

　となります。$P$ と $\text{idx}$ は配列によって変わるのでシミュレーションして確かめる必要はありますが、たかだか $N$ 回です。

# 検証

```python
from itertools import product

def naive(N,S,L):
    total = 0
    ans = 0
    idx = 0
    while total < L:
        total += S[idx%N]
        ans += 1
        idx += 1
    return ans

def fast(N,S,L):
    sum = [0]*(N+1)
    for i in range(N):
        sum[i+1] = sum[i]+S[i]
    P = max(sum)
    k = max(0,(L-P+sum[N]-1)//sum[N])
    L -= k*sum[N]
    total = 0
    idx = 0
    while total < L:
        total += S[idx]
        idx += 1
    return k*N+idx

for N in range(2,5):
    for S in product(range(-5,5),repeat=N):
        if sum(S)<=0:
            continue
        for L in range(1,20):
            ans_naive = naive(N,S,L)
            ans_fast = fast(N,S,L)
            assert(ans_naive==ans_fast)
```

　AI によるコメントましましバージョン

```python
from itertools import product

# シンプルなシミュレーションによる解法
# 指定されたサイクル S（長さ N のリスト）を順に繰り返し、累積和が L 以上になるまでのステップ数を返す
def naive(N, S, L):
    total = 0  # 現在までの累積和
    ans = 0    # ステップ数のカウンタ
    idx = 0    # 現在のステップのインデックス（サイクルを回るため idx % N を使用）
    # 累積和が目標 L に達するまでループ
    while total < L:
        total += S[idx % N]  # サイクル内で順番に加算する
        ans += 1             # ステップ数を1つ進める
        idx += 1             # 次のステップに移動
    return ans  # 累積和が L 以上になったときのステップ数を返す

# 証明に基づいた高速解法
def fast(N, S, L):
    # 1サイクル内での累積和のリストを作成する
    # sum[i] は S[0] から S[i-1] までの累積和となる（sum[0] = 0）
    cum_sum = [0] * (N + 1)
    for i in range(N):
        cum_sum[i + 1] = cum_sum[i] + S[i]
    
    # 1サイクル内の最大進行距離 P（サイクル中に到達できるピーク値）
    P = max(cum_sum)
    
    # 1サイクル全体で進む距離（S の全要素の和）
    cycle_total = cum_sum[N]
    
    # もし L が P 以下なら、1サイクル中で必ず達成できるが、
    # L > P の場合は k サイクル分進めた後、次のサイクルで到達する
    # k は最小の整数で、 k*cycle_total + P >= L を満たす
    # (L - P) を cycle_total で割り切り上げたものが k になる
    k = max(0, (L - P + cycle_total - 1) // cycle_total)
    
    # k サイクル分進めた後の残りの距離に更新する
    L -= k * cycle_total
    
    # 残りの距離 L を達成するために、1サイクル内で何ステップ必要かシミュレーション
    total = 0  # 1サイクル内の累積和
    idx = 0    # ステップ数
    while total < L:
        total += S[idx]
        idx += 1
    
    # 総ステップ数は k サイクル分のステップ数 (k * N) に、追加で必要な idx ステップを加える
    return k * N + idx

# テストコード:
# N = 2 から 4 の場合、S は -5 から 4 の範囲の数値の全組み合わせ（長さ N）を試す
# ただし、サイクル全体の和が正になるもののみを対象（sum(S) > 0）
# L の値は 1 から 19 まで試し、naive と fast の結果が一致することを確認する
for N in range(2, 5):
    for S in product(range(-5, 5), repeat=N):
        if sum(S) <= 0:
            continue  # サイクル全体の和が正でなければスキップ
        for L in range(1, 20):
            ans_naive = naive(N, S, L)
            ans_fast = fast(N, S, L)
            # 両方の方法で計算したステップ数が一致することを確認する
            assert(ans_naive == ans_fast)
```