円環状の配列探索を簡単に!

今回の問題

「数値がN個入っている配列から連続したX個を取り出して合算したとき、最も高い合算値はいくらか」 といった問題です。

背景にある考え方

回転寿司のレーンのような円環状の配列を扱う場合、配列のインデックスが範囲を超えたときに最初に戻るという操作をどう効率的に処理するかがポイントになります。

例えば、N 枚の寿司が並んでいるとき、インデックスが N を越えると、処理としては 0 番目に戻りたい という状況です。このような場合に使われるのが 「剰余」 の計算です。

剰余を使うと

インデックスが配列の範囲を越えた場合、剰余(%) を使うと配列の先頭 に戻ることができます。
例えば、配列の長さが 5 のとき。
インデックスが 5 になると範囲外参照となりますが、インデックス % 配列の長さを計算すると5 % 5 = 0となり、インデックスが先頭に戻ります。
6 になっても 6 % 5 = 1 、7になっても 7 % 5 = 2 のように、配列内のインデックスに変換できます。
これを利用すると、円勘定の配列を簡単に探索できるようになります。

剰余を活用したコード例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 寿司の枚数
        int K = sc.nextInt(); // 取る寿司の枚数
        int[] P = new int[N];

        // 寿司の価格を入力
        for (int i = 0; i < N; i++) {
            P[i] = sc.nextInt();
        }

        // 最初のK枚の寿司の合計を計算
        int currentSum = 0;
        for (int i = 0; i < K; i++) {
            currentSum += P[i];
        }

        // 最大合計金額
        int maxSum = currentSum;

        // スライディングウィンドウで次のK枚の合計を計算
        for (int i = 1; i < N; i++) {
            // 剰余演算を使って、円形の配列を扱う
            currentSum -= P[i - 1]; // 前の寿司を引く
            currentSum += P[(i + K - 1) % N]; // 次の寿司を足す

            // 最大合計金額を更新
            maxSum = Math.max(maxSum, currentSum);
        }

        // 結果を出力
        System.out.println(maxSum);
    }
}

(i + k - 1) % nが今回の注目ポイントです。

i + k - 1:

これは、i 番目の寿司から K 枚目の寿司を見つけるための計算です。

% n:

インデックスが配列のサイズ n を越えたときに、再び 0 番目に戻すために、剰余を取ります。i + k - 1 が n より大きければ、それを n で割った余りを取ることで、インデックスが配列内に収まるようになります。

ちなみに
今回の式でfor文条件iの初期値は1となっていますが、これはスライディングウィンドウ法を用いているためです (別記事で解説しています)。
初期値を0とした場合でも実装は可能ですが、最初のK枚の寿司の合計をもう一度計算することになってしまい無駄な計算となります。

まとめ

剰余を使うと、円環状にの配列探索をシンプルに実装できるようになります。
ぜひ使ってみてください!