ややこしいですよね。
- 最初は $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$ は、
k(S-T)+S\geq L
k\geq\frac{L-S}{S-T}
を満たす $0$ 以上の最小の整数なので、$\max(0,\lceil\frac{L-S}{S-T}\rceil)$ となります。
よって、答えは、
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$ 以上に到達します。
証明
まず、$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$ 回目のサイクルで初めて目標に到達できます。
前段までと同じ計算により、$k$ は、
k \sum S+P\geq L
k\geq\frac{L-P}{\sum S}
を満たす $0$ 以上の整数なので、$\max(0,\lceil\frac{L-P}{\sum S}\rceil)$ となります。
サイクルの長さを $N$、その周期の中でちょうど目標を達成するインデックスを $\text{idx}$ とすると、答えは、
N \cdot \max(0,\lceil\frac{L-P}{\sum S}\rceil) + \text{idx}
となります。$P$ と $\text{idx}$ は配列によって変わるのでシミュレーションして確かめる必要はありますが、たかだか $N$ 回です。
検証
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 によるコメントましましバージョン
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)