競技プログラミングでの数列の基本とJavaでの実装

競技プログラミングでの数列の基本とJavaでの実装。
この記事では、Javaを使った数列の基本的な実装と、よく使われるアルゴリズムを紹介します。

1. 等差数列

1.1 等差数列の定義
隣り合う2つの項の差が一定の数列。

1.2 Javaでの等差数列の実装

public class ArithmeticSequence {
    // n番目の項を計算するメソッド
    public static int nthTerm(int a1, int d, int n) {
        return a1 + (n - 1) * d;
    }

    public static void main(String[] args) {
        int a1 = 1;  // 初項
        int d = 2;   // 公差
        int n = 5;   // 求めたい項数
        System.out.println("n番目の項: " + nthTerm(a1, d, n)); // 出力: 9
    }
}

等差数列の和の計算

public static int arithmeticSum(int a1, int d, int n) {
    int an = nthTerm(a1, d, n);  // 最後の項
    return n * (a1 + an) / 2;
}

2. 等比数列

2.1 等比数列の定義
各項が一定の比で変化する数列。

2.2 Javaでの等比数列の実装

public class GeometricSequence {
    public static int nthTerm(int a1, int r, int n) {
        return a1 * (int)Math.pow(r, n - 1);
    }

    public static void main(String[] args) {
        int a1 = 2;  // 初項
        int r = 3;   // 公比
        int n = 4;   // 求めたい項数
        System.out.println("n番目の項: " + nthTerm(a1, r, n)); // 出力: 54
    }
}

3. フィボナッチ数列

3.1 フィボナッチ数列の定義
各項が直前2つの項の和となる数列。

3.2 Javaでのフィボナッチ数列の実装（再帰）

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("F(" + n + ") = " + fibonacci(n)); // 出力: 55
    }
}

メモ化を使った高速化

import java.util.HashMap;

public class FibonacciMemo {
    private static HashMap<Integer, Integer> memo = new HashMap<>();

    public static int fibonacci(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);

        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("F(" + n + ") = " + fibonacci(n)); // 出力: 55
    }
}

4. 部分和の計算（累積和）

累積和を使うと、数列の任意の部分区間の和を高速に求めることができます。

4.1 累積和の実装

public class PrefixSum {
    public static int[] prefixSum(int[] arr) {
        int n = arr.length;
        int[] prefix = new int[n + 1];  // 0番目は0で初期化

        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int[] prefix = prefixSum(arr);

        // 区間 [1, 3] の和を求める（2 + 3 + 4）
        System.out.println(prefix[4] - prefix[1]); // 出力: 9
    }
}

5. 最長増加部分列（LIS）

最長増加部分列とは、与えられた数列の中で、要素が単調増加する部分列のうち、最も長いものを求める問題です。

LISのDPによる実装

import java.util.Arrays;

public class LongestIncreasingSubsequence {
    public static int lis(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  // 各要素を1で初期化

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("LISの長さ: " + lis(arr)); // 出力: 4
    }
}

6. まとめ

競技プログラミングでは、数列に関連する問題が頻出します。

Javaでは、強力な標準ライブラリを活用しつつ、効率的なアルゴリズムを実装することで、競技プログラミングの問題に対応できます。

毎日更新していますので、@y-t0910をフォローしていただけると嬉しいです。