Pythonプログラム：ベビーステップとジャイアントステップで目的地に到達するための最小ステップ数を求める

問題の概要

クエリのリスト Q が与えられ、各クエリ Q[i] は [a_i, b_i, d_i] という3つの値から構成されているとします。初期位置は (0, 0) であり、1ステップごとに、現在位置 (x1, y1) から2点間のユークリッド距離が a 以上 b 以下となる任意の点 (x2, y2) へ移動できます。各クエリに対して、(0, 0) から (d_i, 0) へ到達するために必要な最小ステップ数を求めるのがこの問題の目的です。

たとえば、入力が Q = [(2,3,1), (1,2,0), (3,4,11)] の場合、出力は [2, 0, 3] となります。その理由は以下の通りです。

• 1つ目のクエリ：(0, 0) から (1/2, √15/2) へ移動し、次に (1, 0) へ移動するため、2ステップが必要です。
• 2つ目のクエリ：d = 0 なので移動は一切不要であり、答えは 0 です。
• 3つ目のクエリ：a = 3、b = 4 のとき、(0, 0) → (4, 0) → (8, 0) → (11, 0) と移動できるため、3ステップで到達できます。

解法のアプローチ

この問題を効率的に解くには、以下の手順に従います。

1. steps() 関数を定義します。この関数は a、b、d を引数として受け取ります。
2. mmin := a と b の最小値、mmax := a と b の最大値とします。
3. d が 0 の場合は、移動が不要なので 0 を返します。
4. d が mmin または mmax と一致する場合は、1ステップで直接到達できるので 1 を返します。
5. d が mmax より小さい場合は、直接は届かないため、いったん前方の点へ進んでから折り返す 2 ステップが必要になります。よって 2 を返します。
6. それ以外の場合は、最大ステップ幅 mmax を使って目的地へ向かう回数、すなわち ceil(d / mmax)(切り上げ)を返します。

メイン処理では、リスト内の各クエリについて上記の steps() 関数を呼び出し、結果を新しいリストに追加していき、最後にそのリストを返します。

Pythonでの実装例

以下の実装を見ると、仕組みがより理解しやすいでしょう。

from math import ceil

def steps(a, b, d):
    mmin = min(a, b)
    mmax = max(a, b)
    if d == 0:
        return 0
    if d == mmin or d == mmax:
        return 1
    if d < mmax:
        return 2
    return ceil(d / mmax)

def solve(Q):
    res = []
    for q in Q:
        a, b, d = q
        res.append(steps(a, b, d))
    return res

Q = [(2,3,1), (1,2,0), (3,4,11)]
print(solve(Q))

入力

[(2,3,1), (1,2,0), (3,4,11)]

出力

[2, 0, 3]

アルゴリズムのポイント

この解法はクエリごとに O(1) で処理でき、非常に効率的です。核心となる考え方は次の通りです。

• 目的地までの距離 d が最大ステップ幅 mmax 以上の場合は、mmax ずつ前進し、残りを切り上げで処理するのが最短経路になります。
• 距離がステップ幅の境界(mmin または mmax)と一致する場合は、1ステップで正確に到達できます。
• 距離が短すぎて直接届かない場合は、一度遠くの点へ移動してから折り返すことで、ちょうど2ステップで目的地に着けます。