Pythonで配列の要素が最後にゼロになるインデックスを求める方法

問題概要

n個の数値を持つ配列Aと、別の入力Kが与えられたとします。このとき、指定された操作を繰り返し実行した結果、最後にゼロへ減少する要素のインデックスを見つける必要があります。

操作のルール

操作は次のように定義されています。

• A[0]からA[N-1]まで順番に、各要素を A[i] = A[i] - K として更新する。
• A[i] < K となった場合は A[i] = 0 とする。
• 一度0になった要素には、それ以降の操作を行わない。

この操作をすべての要素が0になるまで繰り返し、最後にゼロとなる要素のインデックスを返します。

具体例で確認

例えば、入力が A = [4, 3, 6, 8, 3, 10]、K = 4 の場合、出力は 5 になります。操作の流れは以下の通りです。

操作1回目: A = {0, 0, 2, 4, 0, 6}
操作2回目: A = {0, 0, 0, 0, 0, 2}
操作3回目: A = {0, 0, 0, 0, 0, 0}

最後まで残るのはインデックス5の要素（初期値10）であるため、答えは5となります。

解法の考え方

実際に操作を一つずつシミュレーションしなくても、「各要素が0になるまでに必要な操作回数」を計算すればよいことがポイントです。要素 A[i] が0になるまでの操作回数は、切り上げ除算を用いて (A[i] + K - 1) / K で求められます。

アルゴリズムの手順は以下の通りです。

• n := 配列Aのサイズとする
• idx := -1 で初期化する
• x := -10⁹ など非常に小さい値で初期化する
• i を 0 から n-1 までループする
  • A[i] := (A[i] + k - 1) / k（切り上げ除算）
• 再び i を 0 から n-1 までループする
  • A[i] >= x の場合
    • x := A[i]
    • idx := i
• idx を返す

この方法により、必要な操作回数が最大の要素（同じ回数の場合は最も右側の要素）のインデックスを、O(n)の計算量で効率よく求められます。

Pythonでの実装例

それでは、上記のアプローチをPythonで実装してみましょう。

def search_index(A, k):
    n = len(A)
    idx = -1
    x = -10**9
    for i in range(n):
        A[i] = (A[i] + k - 1) // k
    for i in range(n):
        if (A[i] >= x):
            x = A[i]
            idx = i
    return idx

arr = [4, 3, 6, 8, 3, 10]
K = 4
print(search_index(arr, K))

入力

[4, 3, 6, 8, 3, 10], 4

出力

5

まとめ

本記事では、配列の各要素からKを繰り返し減算していき、最後にゼロになるインデックスを求める問題を扱いました。切り上げ除算を使って各要素を「必要な操作回数」に変換し、その最大値の位置を特定することで、シンプルかつ効率的に解けることを確認しました。同様の考え方は、リソース消費やラウンド処理を伴うシミュレーション問題にも応用できます。