見出し画像

貪欲法：multiple array

堀川圭一

この記事は、chatGPTが書いています。
貪欲法の3回目です。
リンク先のnotebookで動作確認できます。ぜひ、動かしてみてください。


【貪欲法解説記事・第3回】multiple array の問題をPythonで解いてみよう！

みなさん、こんにちは！
前回までに、コイン問題や区間スケジューリング問題など、貪欲法（Greedy Algorithm）の定番例を2つ学んできました。
今回は、その締めくくりとして、やや変わり種の 「multiple array の問題」 を取り上げます。
ここでも 「貪欲法 + 単調性」 の考え方が活きてきますので、じっくりと見ていきましょう！

1. multiple array の問題とは？

1-1. 問題設定

  • 2つの配列 A と B が与えられる。

  • それぞれ要素数は N。

  • 配列 AAA の各要素を、好きな回数だけ +1 できる操作 を行い、最終的にすべての A[i]A[i]A[i] が B[i]B[i]B[i] の倍数になる ことを目指す。

  • 目標は「+1 操作の合計回数を最小化」すること。

例

  • A=[2, 7, 4]

  • B=[3, 5, 2]

  • それぞれの要素  A[i] が、B[i] の倍数になるようにするには、一体何回 +1 が必要なのか？

1-2. ポイント

  • ひと口に「+1 操作」と言っても、配列の要素すべてに影響を及ぼす場合や、ある特定の要素だけに加算できる場合など、問題設定によって状況が変わります。

  • 今回のサンプルコードでは、右から左へ順番に要素を「その都度、倍数に合わせる」 という手法で、全要素を最終的に倍数に揃えています。

  • 制約として、右の要素を+1すると、それより左の要素も+1される（影響を及ぼす）とします。

  • 貪欲法が成立する理由としては、「一度決めた分の +1 操作は、まだ見ていない要素（左側）にも影響するが、右側の要素を後から再調整しなくてよい単調性がある」ことが挙げられます。

2. コード例

以下の multiple_array_adjustment 関数では、「+1 操作の合計回数」 を計算しています。
スクリプト全体を眺めながら、どのように「右から左へ」処理していくか確認してください。

def multiple_array_adjustment(N, A, B):
    """
    multiple array の問題を解く関数。
    A[i] が B[i] の倍数になるように +1 操作を行うとき、
    必要となる合計の +1 操作回数を返す。

    Args:
        N (int): 配列の要素数
        A (list of int): 元の配列
        B (list of int): A を割る対象（倍数条件）となる配列

    Returns:
        int: 合計の +1 操作回数
    """

    total_sum = 0  # これまでに行った +1 操作の総数

    # 右端 (N-1) から左端 (0) に向かって逆順に処理
    for i in range(N - 1, -1, -1):
        # すでに行われた +1 操作は A[i] にも全て影響しているため、
        # これまでの操作回数 total_sum を加算
        A[i] += total_sum

        # A[i] が B[i] の倍数になっているかをチェック (余りを求める)
        remainder = A[i] % B[i]

        # 余りがあれば、あと何回 +1 すれば B[i] の倍数になるか計算
        D = 0
        if remainder != 0:
            D = B[i] - remainder

        # 今回必要な +1 回数を total_sum に加え、
        # 次の要素 (より左の要素) でも継続的に影響が及ぶ
        total_sum += D

    return total_sum

# --- 動作確認コード ---
if __name__ == "__main__":
    N = 3
    A = [2, 7, 4]
    B = [3, 5, 2]
    result = multiple_array_adjustment(N, A, B)
    print(result)  # 必要な +1 操作の合計回数が表示される

3. コードの流れ（貪欲法の仕組み）

3-1. 右から左へ逆順に見る理由

  • 右端の要素 A[N−1] をまず倍数に調整するときに、追加で必要となる +1 操作数を求めます。

  • この操作数は、左側の要素（インデックスが小さい方）にも同じだけ影響を与えるけれども、後でもう一度右端をいじることはありません。

  • つまり、右端から順に確定させていくと、一度確定した部分を再度変更する必要がなくなり、無駄な操作が増えません。これが “貪欲法で最適解になる” 大きな理由です。

3-2. 「単調性」がカギ

貪欲法が成功するための条件として、「単調性」 がしばしば挙げられます。
今回の問題では、

  • 一度決定した +1 回数は、それ以降（左側要素を処理する段階）に さらに上書きされる ことはあっても、減らす ことはありません。

  • 右端が整ってしまえば、もう右端に戻ってやり直す必要もない。

このように、右から左へ「部分解を確定していく」進め方が自然に成り立つため、局所的な最適解 を積み重ねるだけで全体の最適解に到達します。

4. 動作イメージ

仮に、

  • N=3

  • A=[2,7,4]

  • B=[3,5,2]

としましょう。

  1. i = 2（配列の右端）

    • A[2] = 4, B[2] = 2

    • ここで total_sum は 0 の状態。

    • A[2] % B[2] = 4 → すでに倍数。追加操作不要。→ D=0

    • total_sum += 0 → total_sum は 0 のまま。

  2. i = 1

    • A[1] = 7, B[1] = 5

    • これまでの操作回数 total_sum=0 を加える → A[1] = 7 + 0 = 7

    • 余り 7 → あと 5 - 2 = 3 回 +1 すれば倍数(10)になる。

    • total_sum += 3 → total_sum=3

  3. i = 0

    • A[0] = 2 だけど、いま total_sum=3 を加算 → A[0] = 2 + 3 = 5

    • 余り 5 → あと 3 - 2 = 1 回 +1 すれば倍数(6)になる。

    • total_sum += 1 → total_sum=4

最終的に total_sum=4。つまり、4回 +1操作を行えば、全ての要素がそれぞれ対応する B[i]の倍数になるわけです。

補足： 実際の操作の仕方を細かく追うと、(右から左へ順に) 「足りない分を都度プラス」しているイメージです。中身がどう変わっていくかを手で計算してみると、より実感を得られます。

5. まとめ

  • multiple array の問題では、配列の各要素がそれぞれ別の値 B[i] の倍数になるように調整する必要があります。

  • 今回の実装では、右端から順に「必要な +1 回数」を求め、それを左へと伝播させる形で貪欲法を使っています。

  • ポイントは「単調性」：右端から確定していくことで、後戻りや再調整が発生しないようになっています。

  • これが「一度確定した局所解（右側要素の倍数化）を崩さなくても済む → 全体の最適解につながる」という仕組みのカギです。

6. 貪欲法シリーズ最終回

これで、コイン問題 → 区間スケジューリング → multiple array と続いた貪欲法シリーズはおしまいです！
どれも、局所的に最適な選択を積み重ねるだけで最終的な最適解に到達できる、という貪欲法の特徴が見えてきたのではないでしょうか？
もちろん、すべての問題に貪欲法が通用するわけではありませんが、うまくハマる場面では非常にシンプルかつ効率的に解けることがわかります。
これまで学んだ例をもとに、ぜひいろいろな問題に挑戦してみてください。

次回：データ構造を学ぼう

次回からは、いよいよ 「データ構造」 を扱います。
スタック、キュー、ヒープなど、アルゴリズムの実装や効率化に欠かせないアイテムを順番に紹介しながら、実践的な例もお見せする予定です。
ぜひ楽しみにしていてください！

実行してみよう！

初心者の方は、まずは下記のコードをコピーして試してみてください。

N = 3
A = [2, 7, 4]
B = [3, 5, 2]
print(multiple_array_adjustment(N, A, B))

  • 自分で A や B の値を変えたり、N を増やしてみたりすると、さらに理解が深まります。

  • 経験者の方は、問題設定をアレンジしてみるのも面白いですよ。

それでは、最後まで読んでいただきありがとうございました！
貪欲法の学習が、みなさんのプログラミングスキル向上に少しでも役立てば幸いです。次回の「データ構造」シリーズもお楽しみに！

補足：print文で動作過程を可視化

動作過程がよくわかると思います。

def multiple_array_adjustment(N, A, B):
    """
    multiple array の問題を解く関数。
    A[i] が B[i] の倍数になるように +1 操作を行うとき、
    必要となる合計の +1 操作回数を返す。

    Args:
        N (int): 配列の要素数
        A (list of int): 元の配列
        B (list of int): A を割る対象（倍数条件）となる配列

    Returns:
        int: 合計の +1 操作回数
    """

    total_sum = 0  # これまでに行った +1 操作の総数
    print("初期状態: A =", A, " B =", B)
    print("-" * 50)

    # 右端 (N-1) から左端 (0) に向かって逆順に処理
    for i in range(N - 1, -1, -1):
        print(f"処理開始 index {i}:")

        # これまでに加えた操作 total_sum が A[i] に反映される
        before = A[i]
        A[i] += total_sum
        print(f"  もともとの A[{i}] = {before} に、これまでの操作数 total_sum = {total_sum} を加えて A[{i}] = {A[i]}")

        # A[i] が B[i] の倍数かどうかをチェック
        remainder = A[i] % B[i]
        print(f"  A[{i}] を B[{i}] = {B[i]} で割った余りは {remainder}")

        # 余りがあれば、あと何回 +1 すれば B[i] の倍数になるか計算
        if remainder != 0:
            D = B[i] - remainder
            print(f"  A[{i}] を B[{i}] の倍数にするには {D} 回の +1 操作が必要")
        else:
            D = 0
            print(f"  A[{i}] はすでに B[{i}] の倍数になっているので、追加の操作は不要")

        # 今回必要な操作 D を total_sum に加える (左側の要素にも影響)
        total_sum += D
        print(f"  合計操作回数 total_sum が更新され {total_sum} になった")
        print("-" * 50)

    print("最終結果: 必要な +1 操作の合計回数 =", total_sum)
    return total_sum

# --- 動作確認コード ---
if __name__ == "__main__":
    N = 3
    A = [2, 7, 4]
    B = [3, 5, 2]
    result = multiple_array_adjustment(N, A, B)
    print("結果:", result)

解説

  1. 初期状態の表示

    • 最初に、元の配列 A と B を表示します。

  2. 逆順のループ処理

    • 配列の右端から左端へ処理を進めます。各インデックスで、これまでの +1 操作の総数 total_sum を A[i] に加えた状態を表示します。

  3. 倍数条件の確認と必要操作の計算

    • A[i] を B[i] で割った余りを表示し、もし余りがあれば、その分だけ +1 操作が必要なことを示します。

  4. 合計操作回数の更新

    • 必要な操作回数 D を total_sum に加えて更新し、更新後の total_sum を表示します。

  5. 最終結果の表示

    • 最終的な合計の +1 操作回数を表示し、結果として返します。


いいなと思ったら応援しよう！