APG4b Java版 第4章: 標準ライブラリと応用

4.00. 第4章について

第3章をお疲れ様でした。この章はこれまでより内容が難しく感じられたかもしれませんが、特に重要と考えるポイントを厳選して紹介しました。

第4章では、競技プログラミングで頻繁に使われる Java の標準ライブラリや便利な機能について解説します。これらを使いこなすことで、実装の効率と正確さが向上します。

---

4.01. 順列・組み合わせ (itertools の代替)

キーポイント

• Java には Python の itertools に対応する標準ライブラリがない
• 順列・組み合わせは再帰で実装するか、int[] の操作で実現する
• 競技プログラミングでよく使うパターンを覚えておくと便利

itertools とは

Python では itertools.permutations() や itertools.combinations() を使うと、順列・組み合わせを簡単に列挙できます。Java にはこれに相当する標準ライブラリがないため、自分で実装する必要があります。

再帰を使うことで、任意の要素数の順列・組み合わせを列挙できます。

順列 (permutations)

n 個の要素のすべての順列を列挙します。

Python: itertools.permutations([1, 2, 3])

Java (再帰実装):

以下のプログラムは、配列の要素を swap (交換) しながら全順列を列挙します。start 番目以降の要素を順番に先頭 (start 番目) と交換し、残りの要素を再帰的に処理します。

import java.util.*;

public class Main {
    static void permutations(int[] arr, int start) {
        if (start == arr.length) {
            // すべての要素が確定したので出力
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            // arr[start] と arr[i] を交換
            int tmp = arr[start]; arr[start] = arr[i]; arr[i] = tmp;
            permutations(arr, start + 1);  // 再帰
            // 元に戻す (バックトラック)
            tmp = arr[start]; arr[start] = arr[i]; arr[i] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        permutations(arr, 0);
    }
}

実行結果:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

permutations(arr, 0) は:

• i=0: arr[0] と arr[0] を交換 → [1, 2, 3] → permutations(arr, 1) → ...
• i=1: arr[0] と arr[1] を交換 → [2, 1, 3] → permutations(arr, 1) → ...
• i=2: arr[0] と arr[2] を交換 → [3, 2, 1] → permutations(arr, 1) → ...

各再帰呼び出しの後で元に戻す (バックトラック) ことで、次の i の処理が正しく行われます。

N 個から K 個を選ぶ順列

N 個の要素から K 個を選んで並べる順列を列挙します。

import java.util.*;

public class Main {
    static int[] original = {1, 2, 3, 4};
    static boolean[] used = new boolean[4];
    static int[] perm = new int[2];  // K=2

    static void permK(int depth, int K) {
        if (depth == K) {
            // K 個が確定したので出力
            System.out.println(Arrays.toString(perm));
            return;
        }
        for (int i = 0; i < original.length; i++) {
            if (!used[i]) {       // まだ使っていない要素を選ぶ
                used[i] = true;   // 使用済みにする
                perm[depth] = original[i];
                permK(depth + 1, K);
                used[i] = false;  // 元に戻す (バックトラック)
            }
        }
    }

    public static void main(String[] args) {
        permK(0, 2);
    }
}

used[i] フラグで各要素が使用済みかどうかを管理します。

組み合わせ (combinations)

N 個の要素から K 個を選ぶ組み合わせを列挙します。順列と違い、選ぶ順序は考慮しません。

Python: itertools.combinations([1, 2, 3, 4], 2)

以下のプログラムは start 番目以降の要素から選ぶことで、重複なく組み合わせを列挙します。

import java.util.*;

public class Main {
    static int[] original = {1, 2, 3, 4};
    static int[] comb = new int[2];  // K=2

    static void combinations(int start, int depth, int K) {
        if (depth == K) {
            // K 個が確定したので出力
            System.out.println(Arrays.toString(comb));
            return;
        }
        for (int i = start; i < original.length; i++) {
            comb[depth] = original[i];
            combinations(i + 1, depth + 1, K);  // i+1 から探す (重複を避ける)
        }
    }

    public static void main(String[] args) {
        combinations(0, 0, 2);
    }
}

実行結果:

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

combinations(i + 1, ...) とすることで、次に選ぶ要素は必ず現在の要素より後ろにあるものになります。これにより [1, 2] と [2, 1] のような重複が防がれます。

直積 (product)

複数のリストから1つずつ要素を選ぶすべての組み合わせを列挙します。

Python: itertools.product(range(2), range(3))

public class Main {
    public static void main(String[] args) {
        // product(range(2), range(3))
        for (int x = 0; x < 2; x++) {
            for (int y = 0; y < 3; y++) {
                System.out.println(x + " " + y);
            }
        }
    }
}

ビット全探索 (product(range(2), repeat=N) の代替):

int N = 20;
for (int i = 0; i < (1 << N); i++) {
    // i のビットパターンで {0, 1}^N の全組み合わせを表現
    for (int j = 0; j < N; j++) {
        int bit = (i >> j) & 1;  // j ビット目が 0 か 1 か
    }
}

計算量の目安

操作	ループ回数
10個の順列 (10!)	3,628,800
26個から13個の組み合わせ	10,400,600

N が大きくなると急激に増加するため、N の制約から計算量を見積もることが重要です。

---

4.02. collections の代替 (ArrayDeque・HashMap・カウンター)

キーポイント

• Python の collections.deque → Java の ArrayDeque
• Python の collections.defaultdict(int) → Java の HashMap + getOrDefault
• Python の collections.Counter → Java の HashMap でカウント

ArrayDeque (両端キュー)

ArrayDeque は両端 (先頭と末尾) への追加・削除が O(1) で行えるデータ構造です。Python の collections.deque に対応します。

スタック (LIFO: 後入れ先出し) としても、キュー (FIFO: 先入れ先出し) としても使えます。

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque<Integer> q = new ArrayDeque<>(java.util.Arrays.asList(1, 2, 3, 4, 5, 6));
        // q = [1, 2, 3, 4, 5, 6]

        System.out.println(q.pollLast());    // 6 (右端を取り出す)
        System.out.println(q.pollLast());    // 5
        System.out.println(q.pollFirst());   // 1 (左端を取り出す)
        System.out.println(q.pollFirst());   // 2
        System.out.println(q);              // [3, 4]

        q.addLast(10);                       // 右端に追加
        q.addFirst(20);                      // 左端に追加
        System.out.println(q);              // [20, 3, 4, 10]
        System.out.println(q.size());       // 4
        System.out.println(q.peekFirst());  // 20 (先頭を参照するが取り出さない)
        System.out.println(q.peekLast());   // 10 (末尾を参照するが取り出さない)
    }
}

poll は取り出し (削除あり)、peek は参照 (削除なし) です。

ArrayDeque の操作一覧

操作	Java (ArrayDeque)	Python (deque)	計算量
右端に追加	q.addLast(x)	q.append(x)	O(1)
左端に追加	q.addFirst(x)	q.appendleft(x)	O(1)
右端を取り出す	q.pollLast()	q.pop()	O(1)
左端を取り出す	q.pollFirst()	q.popleft()	O(1)
右端を参照	q.peekLast()	q[-1]	O(1)
左端を参照	q.peekFirst()	q[0]	O(1)
サイズ	q.size()	len(q)	O(1)

注意: ArrayDeque はインデックスによるランダムアクセスができません。i 番目の要素にアクセスしたい場合は ArrayList を使います。

キューとしての使い方 (BFS)

ArrayDeque はキュー (先入れ先出し) として使うことで、BFS (幅優先探索) を実装できます。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // グラフの BFS の例
        int N = 5;
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N; i++) graph.add(new ArrayList<>());
        // 辺: 0-1, 0-2, 1-3, 2-4
        graph.get(0).add(1); graph.get(0).add(2);
        graph.get(1).add(3); graph.get(2).add(4);

        int[] dist = new int[N];
        Arrays.fill(dist, -1);  // -1 = 未訪問
        dist[0] = 0;            // スタートの距離は 0

        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.addLast(0);  // スタートをキューに追加

        while (!queue.isEmpty()) {
            int v = queue.pollFirst();       // キューから取り出す
            for (int u : graph.get(v)) {
                if (dist[u] == -1) {         // 未訪問なら
                    dist[u] = dist[v] + 1;   // 距離を設定
                    queue.addLast(u);         // キューに追加
                }
            }
        }
        System.out.println(Arrays.toString(dist));  // [0, 1, 1, 2, 2]
    }
}

BFS では「先に入れたものを先に取り出す」必要があるため、addLast() で追加して pollFirst() で取り出します。

defaultdict の代替

Python の defaultdict(int) は、存在しないキーにアクセスすると自動的に 0 (デフォルト値) が設定されます。Java では getOrDefault() メソッドで同様の動作が実現できます。

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> d = new HashMap<>();

        // getOrDefault: キーが存在しなければデフォルト値を返す
        System.out.println(d.getOrDefault("a", 0));   // 0 (キー "a" が存在しない)
        d.put("x", d.getOrDefault("x", 0) + 10);      // 0 + 10 = 10
        System.out.println(d.get("x"));                // 10

        // merge: より簡潔な書き方
        int[] values = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
        HashMap<Integer, Integer> counter = new HashMap<>();
        for (int v : values) {
            counter.merge(v, 1, Integer::sum);  // v のカウントを 1 増やす
        }
        System.out.println(counter);
    }
}

counter.merge(v, 1, Integer::sum) は「キー v が存在しなければ値 1 をセット、存在すれば既存の値と 1 を Integer::sum (加算) する」という処理です。

Counter の代替

Python の collections.Counter(vals) は要素の出現回数を数えます。Java では HashMap で実装します。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] vals = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

        // 出現回数をカウント
        HashMap<Integer, Integer> c = new HashMap<>();
        for (int v : vals) {
            c.merge(v, 1, Integer::sum);
        }

        System.out.println(c.getOrDefault(9, 0));   // 1 (9 の出現回数)
        System.out.println(c.getOrDefault(10, 0));  // 0 (10 は存在しない)

        // 出現頻度でソート (most_common の代替)
        ArrayList<Map.Entry<Integer, Integer>> entries = new ArrayList<>(c.entrySet());
        entries.sort((a, b) -> b.getValue() - a.getValue());  // 頻度降順
        for (var entry : entries) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

---

4.03. PriorityQueue と二分探索 (heapq・bisect の代替)

キーポイント

• Python の heapq → Java の PriorityQueue (デフォルトで最小ヒープ)
• Python の bisect_left/right → Java の Arrays.binarySearch() または手動実装
• TreeSet の floor(), ceiling() が bisect の代替になる場面も多い

PriorityQueue (優先度付きキュー)

PriorityQueue は「常に最小値 (または最大値) を素早く取り出せるデータ構造」です。Python の heapq に対応します。

デフォルトでは最小ヒープ (最小値が先頭にくる) です。

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();  // 最小ヒープ
        pq.add(4); pq.add(6); pq.add(1); pq.add(8);

        System.out.println(pq.peek());   // 1 (最小値を参照するが取り出さない)
        System.out.println(pq.poll());   // 1 (最小値を取り出す)
        System.out.println(pq.peek());   // 4 (次の最小値)

        pq.add(2);
        // 小さい順に取り出す
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");  // 2 4 6 8
        }
        System.out.println();
    }
}

実行結果:

1
1
4
2 4 6 8

PriorityQueue は内部でヒープ構造を管理しているため、どの順序で追加しても、取り出すときは常に最小値が先に出てきます。

PriorityQueue の操作一覧

メソッド	意味	計算量
pq.add(x)	要素を追加	O(log N)
pq.poll()	最小値を取り出す	O(log N)
pq.peek()	最小値を参照 (取り出さない)	O(1)
pq.size()	要素数	O(1)
pq.isEmpty()	空かどうか確認	O(1)

最大ヒープ (最大値優先)

Comparator.reverseOrder() を使うと、最大値を先に取り出せる最大ヒープになります。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
        maxPQ.add(4); maxPQ.add(6); maxPQ.add(1); maxPQ.add(8);
        System.out.println(maxPQ.poll());  // 8 (最大値)
        System.out.println(maxPQ.poll());  // 6
    }
}

Python の「負数にして最小ヒープで最大ヒープを実現する」テクニックと同様に、Java でも負数を使う方法があります:

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(-4); pq.add(-6); pq.add(-1); pq.add(-8);
int maxVal = -pq.poll();  // 8 (最大値)

タプルで優先度とデータを紐付け

ダイクストラ法などでは、優先度 (コスト) とデータ (ノード) をセットで管理したいことがあります。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // [優先度, データ] の配列を PriorityQueue に格納
        // 比較は最初の要素 (優先度) で行う
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{30, 0});  // 優先度30, タスクA
        pq.add(new int[]{10, 1});  // 優先度10, タスクB
        pq.add(new int[]{20, 2});  // 優先度20, タスクC

        System.out.println(Arrays.toString(pq.poll()));  // [10, 1] (タスクB)
        pq.add(new int[]{25, 3});  // タスクD を追加
        System.out.println(Arrays.toString(pq.poll()));  // [20, 2] (タスクC)
    }
}

Python の heapq.heappush(pq, (30, task_A)) に対応します。

二分探索 (bisect の代替)

二分探索は、ソート済み配列から特定の値を O(log N) で検索するアルゴリズムです。Python の bisect モジュールに対応します。

Arrays.binarySearch の使い方:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {10, 20, 40, 60, 90};

        // 値 30 の挿入位置を求める (bisect_left の代替)
        int pos = Arrays.binarySearch(a, 30);
        // 見つからない場合: -(挿入位置) - 1 が返る
        if (pos < 0) pos = -(pos + 1);  // 挿入位置に変換
        System.out.println(pos);  // 2 (30 は a[2]=40 の前に挿入すべき)
    }
}

Arrays.binarySearch() は値が見つかればそのインデックスを、見つからなければ -(挿入位置) - 1 を返します。

bisect_left / bisect_right の手動実装:

より柔軟な使い方のために、自前で実装することも多いです。

// bisect_left: v 未満の要素数 (v が挿入されるべき左端の位置)
static int bisectLeft(int[] a, int v) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] < v) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// bisect_right: v 以下の要素数 (v が挿入されるべき右端の位置)
static int bisectRight(int[] a, int v) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] <= v) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

使用例:

public class Main {
    static int bisectLeft(int[] a, int v) {
        int lo = 0, hi = a.length;
        while (lo < hi) { int m = (lo+hi)/2; if (a[m] < v) lo = m+1; else hi = m; }
        return lo;
    }
    static int bisectRight(int[] a, int v) {
        int lo = 0, hi = a.length;
        while (lo < hi) { int m = (lo+hi)/2; if (a[m] <= v) lo = m+1; else hi = m; }
        return lo;
    }

    public static void main(String[] args) {
        int[] a = {10, 20, 40, 60, 90};
        System.out.println(bisectLeft(a, 30));   // 2
        System.out.println(bisectRight(a, 30));  // 2
        System.out.println(bisectLeft(a, 60));   // 3 (60の左端)
        System.out.println(bisectRight(a, 60));  // 4 (60の右端)

        // 値 v の個数: bisectRight(a,v) - bisectLeft(a,v)
        System.out.println(bisectRight(a, 60) - bisectLeft(a, 60));  // 1 (60が1個)
    }
}

TreeSet を使った bisect の代替

TreeSet の floor(), ceiling(), lower(), higher() で、ある値の近傍を求めることができます。

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> s = new TreeSet<>(java.util.Arrays.asList(10, 20, 40, 60, 90));

        System.out.println(s.floor(30));    // 20 (30以下の最大値)
        System.out.println(s.ceiling(30));  // 40 (30以上の最小値)
        System.out.println(s.lower(40));    // 20 (40未満の最大値)
        System.out.println(s.higher(40));   // 60 (40より大きい最小値)
    }
}

---

4.04. Math・Random・時間計測 (math・random・time の代替)

キーポイント

• Python の math → Java の Math クラス (インポート不要)
• Python の random → Java の Random クラス
• Python の time.time() → Java の System.currentTimeMillis()

Math クラス

Math クラスは java.lang パッケージに含まれているため、import なしで使えます。

GCD・LCM:

Python では math.gcd() が使えますが、Java ではユークリッドの互除法を自前で実装します。

static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);  // ユークリッドの互除法
}

static long lcm(long a, long b) {
    return a / gcd(a, b) * b;  // LCM = a * b / GCD (オーバーフローを避けるため先に割る)
}

数学関数:

System.out.println(Math.log(Math.E));        // 1.0 (自然対数 ln(e))
System.out.println(Math.log10(100));          // 2.0 (常用対数)
System.out.println(Math.log(8) / Math.log(2)); // 3.0 (log₂(8))
System.out.println(Math.sin(Math.PI / 2));   // 1.0
System.out.println(Math.cos(0));             // 1.0
System.out.println(Math.sqrt(2));            // 1.4142135623730951
System.out.println(Math.PI);                 // 3.141592653589793
System.out.println(Math.E);                  // 2.718281828459045
System.out.println(Math.abs(-5));            // 5
System.out.println(Math.pow(2, 10));         // 1024.0
System.out.println(Math.floorDiv(-7, 2));    // -4 (Python の // と同じ)
System.out.println(Math.floorMod(-7, 2));    // 1  (Python の % と同じ)

組み合わせ・階乗:

static long factorial(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

static long comb(int n, int k) {
    if (k > n - k) k = n - k;  // k > n/2 なら n-k を使う方が効率的
    long result = 1;
    for (int i = 0; i < k; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

BigInteger を使った大きな数の演算

Python では整数のサイズに制限がありませんが、Java では long 型の上限 (約 922京) を超えると BigInteger が必要です。

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        // 3^1000 (long では扱えない大きな数)
        BigInteger a = BigInteger.valueOf(3).pow(1000);
        System.out.println(a);  // 478桁の数

        // BigInteger の四則演算
        BigInteger x = BigInteger.valueOf(100);
        BigInteger y = BigInteger.valueOf(7);
        System.out.println(x.add(y));       // 107
        System.out.println(x.subtract(y));  // 93
        System.out.println(x.multiply(y));  // 700
        System.out.println(x.divide(y));    // 14 (整数除算)
        System.out.println(x.mod(y));       // 2

        // GCD
        System.out.println(x.gcd(y));  // 1

        // 比較
        System.out.println(x.compareTo(y));  // 1 (x > y)

        // 組み合わせ (nCk) を BigInteger で
        System.out.println(bigComb(100, 20));
    }

    static BigInteger bigComb(int n, int k) {
        BigInteger result = BigInteger.ONE;
        for (int i = 0; i < k; i++) {
            result = result.multiply(BigInteger.valueOf(n - i))
                           .divide(BigInteger.valueOf(i + 1));
        }
        return result;
    }
}

BigInteger のメソッドは + などの演算子が使えず、add(), subtract(), multiply(), divide() などのメソッドを使います。

Random クラス

乱数を生成するには java.util.Random クラスを使います。

import java.util.Random;

public class Main {
    public static void main(String[] args) {
        Random rng = new Random(0);  // seed=0 で固定 (再現性あり)

        System.out.println(rng.nextDouble());     // 0.0〜1.0 の乱数
        System.out.println(rng.nextInt(5) + 5);   // 5〜9 の整数乱数
        System.out.println(rng.nextInt(3));        // 0, 1, 2 のいずれか

        // 配列からランダムに1要素を選ぶ
        int[] choices = {10, 20, 30, 40};
        int chosen = choices[rng.nextInt(choices.length)];
        System.out.println(chosen);

        // ArrayList をシャッフル
        Integer[] arr = {1, 2, 3, 4, 5};
        java.util.Collections.shuffle(java.util.Arrays.asList(arr), rng);
        System.out.println(java.util.Arrays.toString(arr));
    }
}

new Random(seed) でシード値を固定すると、毎回同じ乱数列が生成されます (テスト・デバッグに便利)。

時間計測

アルゴリズムの実行時間を計測したい場合は System.currentTimeMillis() を使います。

public class Main {
    public static void main(String[] args) {
        long t0 = System.currentTimeMillis();  // 開始時刻 (ミリ秒)

        long s = 0;
        for (int i = 0; i < 100_000_000; i++) {
            s += i;
        }

        long t1 = System.currentTimeMillis();  // 終了時刻
        System.out.println((t1 - t0) + " ms");  // 経過時間
        System.out.println(s);
    }
}

制限時間内に処理を打ち切る:

インタラクティブ問題や近似アルゴリズムで有用です。

long t0 = System.currentTimeMillis();
while (true) {
    // 処理
    if (System.currentTimeMillis() - t0 > 1900) break;  // 1.9秒経過で終了
}

---

4.05. メモ化 (functools.cache の代替)

キーポイント

• Python の @functools.cache → Java では HashMap を使って手動でメモ化
• 再帰関数の計算結果をキャッシュして重複計算を避ける

メモ化とは

再帰関数では、同じ引数で何度も同じ計算が行われることがあります。一度計算した結果を「メモ」しておき、次回同じ引数が来たときはメモから結果を取り出すことで高速化する手法を「メモ化」といいます。

例えば、再帰でフィボナッチ数を求めると fib(50) に 10^10 回以上の計算が必要ですが、メモ化すると 50 回で済みます。

メモ化なしの問題:

static long fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);  // 同じ値を何度も計算
}
// fib(50) を呼ぶと膨大な時間がかかる

HashMap によるメモ化

import java.util.HashMap;

public class Main {
    static HashMap<Integer, Long> memo = new HashMap<>();

    static long fib(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (memo.containsKey(n)) return memo.get(n);  // 既に計算済みならキャッシュを返す
        long result = fib(n - 1) + fib(n - 2);         // 計算
        memo.put(n, result);                            // 結果をキャッシュに保存
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fib(5));   // 5
        System.out.println(fib(6));   // 8
        System.out.println(fib(7));   // 13
        System.out.println(fib(50));  // 12586269025 (高速で計算できる)
    }
}

Python では @functools.cache デコレータを付けるだけでメモ化できますが、Java では HashMap を使って明示的に実装します。

memo.containsKey(n) でキャッシュに値があるか確認し、あれば即座に返します。なければ計算して memo.put(n, result) で保存します。

多引数のメモ化 (2次元)

引数が2つある場合は、2次元のキーを使います。

import java.util.HashMap;

public class Main {
    static HashMap<Long, Long> memo = new HashMap<>();

    // (i, j) → long にエンコード
    static long encode(int i, int j) {
        return (long) i * 100000 + j;
    }

    // (0,0) から (i,j) までのグリッド経路数を求める
    static long dp(int i, int j) {
        if (i == 0 && j == 0) return 1;
        if (i < 0 || j < 0) return 0;
        long key = encode(i, j);
        if (memo.containsKey(key)) return memo.get(key);
        long result = dp(i - 1, j) + dp(i, j - 1);  // 上から来るか、左から来るか
        memo.put(key, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(dp(5, 5));  // 252 (6×6 グリッドの経路数)
    }
}

2つの整数 (i, j) を1つの long にエンコードすることでキーとして使えます。i * 100000 + j は j < 100000 を前提としています。

配列を使ったメモ化 (より高速)

引数の範囲が事前にわかっている場合、HashMap より配列の方が高速です。

public class Main {
    static long[] memo;

    static long fib(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (memo[n] != -1) return memo[n];  // キャッシュに値があれば返す (-1 は未計算を示す)
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        int MAX = 100;
        memo = new long[MAX];
        java.util.Arrays.fill(memo, -1);  // -1 で初期化 (未計算を示す)
        System.out.println(fib(50));  // 12586269025
    }
}

配列は HashMap より定数倍が速く、インデックスが整数のときはこちらを使うのがお勧めです。

練習問題

EX23. 再帰関数1

---

4.06. その他のライブラリ (fractions・decimal の代替)

キーポイント

• Python の fractions.Fraction → Java には標準の有理数クラスがない (自前実装)
• Python の decimal.Decimal → Java の BigDecimal

BigDecimal (Decimal の代替)

浮動小数点数 (double) は計算誤差が生じることがあります。正確な10進数演算が必要な場合は BigDecimal を使います。

import java.math.BigDecimal;

public class Main {
    public static void main(String[] args) {
        // double の問題: 0.1 + 0.2 が正確に 0.3 にならない
        System.out.println(0.1 + 0.2 == 0.3);  // false
        System.out.println(0.1 + 0.2);          // 0.30000000000000004

        // BigDecimal なら正確に計算できる
        BigDecimal a = new BigDecimal("0.1");   // 文字列で初期化することが重要!
        BigDecimal b = new BigDecimal("0.2");
        BigDecimal c = new BigDecimal("0.3");
        System.out.println(a.add(b).equals(c));  // true

        // 四則演算
        System.out.println(a.add(b));       // 0.3
        System.out.println(a.multiply(b));  // 0.02
        System.out.println(c.subtract(a)); // 0.2
    }
}

重要: new BigDecimal(0.1) ではなく new BigDecimal("0.1") (文字列) で初期化してください。new BigDecimal(0.1) は double の誤差を引き継いでしまいます。

有理数クラスの自前実装

Python の fractions.Fraction に対応するクラスを自前で実装します。

public class Main {
    static class Fraction {
        long num, den;  // 分子 (numerator), 分母 (denominator)

        Fraction(long num, long den) {
            long g = gcd(Math.abs(num), Math.abs(den));
            if (den < 0) { num = -num; den = -den; }  // 分母を正にする
            this.num = num / g;
            this.den = den / g;
        }

        static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }

        Fraction add(Fraction other) {
            return new Fraction(num * other.den + other.num * den, den * other.den);
        }

        Fraction subtract(Fraction other) {
            return new Fraction(num * other.den - other.num * den, den * other.den);
        }

        Fraction multiply(Fraction other) {
            return new Fraction(num * other.num, den * other.den);
        }

        Fraction divide(Fraction other) {
            return new Fraction(num * other.den, den * other.num);
        }

        @Override
        public String toString() { return den == 1 ? num + "" : num + "/" + den; }
    }

    public static void main(String[] args) {
        Fraction x = new Fraction(1, 2);  // 1/2
        Fraction y = new Fraction(1, 3);  // 1/3
        System.out.println(x.add(y));       // 5/6
        System.out.println(x.multiply(y));  // 1/6
        System.out.println(x.divide(y));    // 3/2
        System.out.println(new Fraction(1, 2).add(new Fraction(1, 2))); // 1
    }
}

コンストラクタで GCD を取って約分しているため、常に既約分数で管理されます。

---

4.07. TreeSet・TreeMap (sortedcontainers の代替)

キーポイント

• Python の SortedList / SortedSet → Java の TreeSet
• Python の SortedDict → Java の TreeMap
• これらは Java 標準ライブラリに含まれており、サードパーティ不要

TreeSet (ソート済み Set)

TreeSet は要素を常にソートされた状態で管理する Set です。Python の sortedcontainers.SortedList または SortedSet に対応します。

追加・削除・検索がすべて O(log N) で行えます。

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> s = new TreeSet<>(java.util.Arrays.asList(7, 3, 1, 5));
        // s = {1, 3, 5, 7} (自動的にソートされる)

        // ある値以上の最小要素を取得 (bisect の代替)
        System.out.println(s.ceiling(4));   // 5 (4以上の最小値)
        System.out.println(s.floor(4));     // 3 (4以下の最大値)
        System.out.println(s.lower(5));     // 3 (5未満の最大値)
        System.out.println(s.higher(5));    // 7 (5より大きい最小値)

        s.add(6);    // 6 を追加 → {1, 3, 5, 6, 7}
        s.remove(5); // 5 を削除 → {1, 3, 6, 7}
        System.out.println(s.ceiling(4));   // 6 (4以上の最小値)

        // 最小値・最大値
        System.out.println(s.first());  // 1
        System.out.println(s.last());   // 7

        // 昇順イテレーション
        for (int x : s) System.out.print(x + " ");  // 1 3 6 7
        System.out.println();

        // 降順イテレーション
        for (int x : s.descendingSet()) System.out.print(x + " ");  // 7 6 3 1
        System.out.println();
    }
}

TreeMap (ソート済み Map)

TreeMap はキーを常にソートされた状態で管理します。Python の sortedcontainers.SortedDict に対応します。

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, Integer> d = new TreeMap<>();
        d.put(7, 49); d.put(3, 9); d.put(1, 1); d.put(5, 25);
        // d = {1=1, 3=9, 5=25, 7=49} (キーで昇順)

        // k 以上の最小キーとその値
        System.out.println(d.ceilingKey(4));     // 5
        System.out.println(d.ceilingEntry(4));    // 5=25

        d.put(6, 36);
        d.remove(5);
        System.out.println(d.ceilingEntry(4));    // 6=36

        // 最小・最大キー
        System.out.println(d.firstKey());  // 1
        System.out.println(d.lastKey());   // 7

        // キーと値のイテレーション (キー昇順)
        for (var entry : d.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

多重集合 (同じ値を複数格納)

TreeSet は重複を許しません。同じ値を複数管理したい場合は TreeMap<値, 個数> で代替します。

import java.util.TreeMap;

public class Main {
    static TreeMap<Integer, Integer> multiset = new TreeMap<>();

    // 要素を追加
    static void add(int x) {
        multiset.merge(x, 1, Integer::sum);  // カウントを 1 増やす
    }

    // 要素を1つ削除
    static void remove(int x) {
        int cnt = multiset.getOrDefault(x, 0);
        if (cnt == 1) multiset.remove(x);     // カウントが 1 なら削除
        else multiset.put(x, cnt - 1);         // カウントを 1 減らす
    }

    static int min() { return multiset.firstKey(); }
    static int max() { return multiset.lastKey(); }

    public static void main(String[] args) {
        add(3); add(1); add(4); add(1); add(5);
        // multiset: {1:2, 3:1, 4:1, 5:1}
        System.out.println(min());  // 1
        System.out.println(max());  // 5
        remove(1);
        System.out.println(min());  // 1 (まだ1つ残っている)
        remove(1);
        System.out.println(min());  // 3 (1がなくなった)
    }
}

この実装で O(log N) で最小値・最大値の取得と要素の追加・削除ができます。

---

4.08. クラス

キーポイント

• Java はオブジェクト指向言語であり、クラスが基本単位
• コンストラクタは クラス名(引数) の形で定義
• インスタンス変数・メソッドへのアクセスは this.変数名
• 特殊メソッドは toString(), equals(), compareTo() など

クラスとは

「クラス」とは、データ (フィールド) とそのデータを操作する処理 (メソッド) をまとめたものです。Python のクラスと似ていますが、すべてのフィールドに型を指定する必要があります。

基本的なクラス定義

class Person {
    String name;  // フィールド (属性)
    int age;

    // コンストラクタ: オブジェクトを作成するときに呼ばれる
    Person(String name, int age) {
        this.name = name;  // this.name はフィールド、name は引数
        this.age = age;
    }
}

public class Main {
    public static void main(String[] args) {
        Person p = new Person("Taro", 18);  // オブジェクトの作成
        System.out.println(p.name);  // Taro
        System.out.println(p.age);   // 18
    }
}

this.name の this は「このオブジェクト自身」を指します。フィールド名と引数名が同じ場合に区別するために使います。

メソッドの定義

クラスにはデータを操作するメソッドを定義できます。

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // メソッド: 挨拶を出力する
    void sayHello() {
        System.out.println("Hello, I'm " + name + ".");
    }

    // メソッド: 年齢を確認する
    boolean isAdult() {
        return age >= 18;
    }
}

public class Main {
    public static void main(String[] args) {
        Person p = new Person("Taro", 18);
        p.sayHello();            // Hello, I'm Taro.
        System.out.println(p.isAdult()); // true
    }
}

toString() の定義 (__str__ の代替)

Python の __str__ に対応するのが Java の toString() メソッドです。System.out.println(obj) を呼ぶと自動的に toString() が使われます。

class Vector2d {
    double x, y;

    Vector2d(double x, double y) {
        this.x = x;
        this.y = y;
    }

    Vector2d add(Vector2d other) {
        return new Vector2d(this.x + other.x, this.y + other.y);
    }

    @Override
    public String toString() {
        return "(x=" + x + ", y=" + y + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        Vector2d v = new Vector2d(3, 4);
        Vector2d w = new Vector2d(10, 20);
        System.out.println(v);         // (x=3.0, y=4.0)
        System.out.println(v.add(w));  // (x=13.0, y=24.0)
    }
}

@Override は「親クラスのメソッドをオーバーライドする」という宣言です。Object クラスの toString() を上書きしています。

実用例: 合計付きリスト

競技プログラミングでは、複数の情報をまとめて管理したいときにクラスを使います。

import java.util.ArrayList;

class ListWithSum {
    ArrayList<Integer> array;
    int sum;  // 合計を常に管理する

    ListWithSum(int[] initial) {
        array = new ArrayList<>();
        sum = 0;
        for (int x : initial) {
            array.add(x);
            sum += x;
        }
    }

    void append(int x) {
        array.add(x);
        sum += x;  // 追加したらすぐに合計を更新
    }

    int pop() {
        int x = array.remove(array.size() - 1);
        sum -= x;  // 削除したらすぐに合計を更新
        return x;
    }

    int getSum() { return sum; }

    @Override
    public String toString() { return array.toString(); }
}

public class Main {
    public static void main(String[] args) {
        ListWithSum a = new ListWithSum(new int[]{20, 30, 10});
        System.out.println(a.getSum());  // 60
        a.append(60);
        System.out.println(a.getSum());  // 120
        a.pop();
        System.out.println(a.getSum());  // 60
        System.out.println(a);           // [20, 30, 10]
    }
}

sum フィールドを常に最新状態に保つことで、毎回ループで合計を計算するより O(1) で合計を取得できます。

Comparable インターフェース (ソート対応)

クラスのオブジェクトを Collections.sort() などでソートしたい場合は Comparable<T> インターフェースを実装します。Python の __lt__ に対応します。

import java.util.*;

class Student implements Comparable<Student> {
    String name;
    int score;

    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    @Override
    public int compareTo(Student other) {
        // 戻り値が負: this が先 (this < other)
        // 戻り値が0: 同じ
        // 戻り値が正: other が先 (this > other)
        return this.score - other.score;  // 得点昇順
    }

    @Override
    public String toString() { return name + ":" + score; }
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Student> students = new ArrayList<>();
        students.add(new Student("Alice", 85));
        students.add(new Student("Bob", 70));
        students.add(new Student("Carol", 90));
        Collections.sort(students);  // compareTo に従ってソート
        System.out.println(students);  // [Bob:70, Alice:85, Carol:90]
    }
}

---

4.09. Javaの罠 (よくある間違いと注意点)

キーポイント

• int 型のオーバーフローに注意 (約21億を超えると long が必要)
• 文字列の比較は == ではなく .equals() を使う
• Scanner の nextInt() 後に nextLine() を使うと空文字が返る
• 配列の初期値は int が 0、boolean が false、オブジェクト型が null
• 整数除算の切り捨て方向が Python と異なる

---

int のオーバーフロー (★★★ 最重要)

int 型は約 ±21億 (2^31 - 1 = 2,147,483,647) までしか格納できません。この範囲を超えると「オーバーフロー」が発生し、計算結果が意図しない値になります。

// 悪い例: int 同士の計算がオーバーフロー
int a = 2000000000;
int b = 2000000000;
System.out.println(a + b);  // -294967296 (オーバーフロー！)

// 良い例: long を使う
long la = 2000000000L;
long lb = 2000000000L;
System.out.println(la + lb);  // 4000000000 (正しい)

特に注意が必要なのは「int 同士の計算結果を long に代入する」パターンです。代入する前に計算がオーバーフローしてしまいます。

// 罠: int * int の結果が int でオーバーフローしてから long に代入される
int x = 100000;
long bad = x * x;        // x * x が int で計算され -727379968 になる (オーバーフロー!)
long good = (long)x * x; // (long)x でキャストしてから計算 → 10000000000 (正しい)

対策: 競技プログラミングでは、整数は基本的に long を使うと安全です。

文字列の比較 (★★★)

Java で文字列を比較するとき、== は「同じオブジェクトを指しているか」を比較します。文字列の内容を比較するには必ず .equals() を使ってください。

// 悪い例: == で文字列を比較
String a = new String("Hello");
String b = new String("Hello");
System.out.println(a == b);       // false (異なるオブジェクト)

// 良い例: .equals() で文字列を比較
System.out.println(a.equals(b));  // true (内容が等しい)

// Scanner で読んだ文字列との比較 (必ず .equals() を使う)
Scanner sc = new Scanner(System.in);
String s = sc.next();
if (s.equals("Yes")) {
    System.out.println("一致!");
}

// null の可能性がある場合は文字列リテラルを先に書く (null セーフ)
String t = null;
// t.equals("Yes")  → NullPointerException!
"Yes".equals(t);    // false (null セーフ)

Scanner の nextInt() 後に nextLine() (★★)

nextInt() は整数を読み込みますが、その後の改行文字を読み込みません。次に nextLine() を呼ぶと、その改行文字だけを読んで空文字列が返ります。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();     // ← 改行文字を読み捨てる (これがないと次の nextLine() が空文字を返す)
        String s = sc.nextLine();  // 正しく次の行を読める
        System.out.println(n);
        System.out.println(s);
    }
}

入力:

5
Hello

sc.nextLine() (改行読み捨て) を入れると: n = 5, s = "Hello" と正しく読み込めます。 入れないと: n = 5, s = "" (空文字) になってしまいます。

整数除算の切り捨て方向 (★★)

Java の整数除算は「0方向への切り捨て」、Python の // は「負の無限大方向への切り捨て」です。

// Python: -7 // 2 = -4 (負の無限大方向)
// Java:   -7 / 2 = -3 (0方向)
System.out.println(-7 / 2);   // -3 (Python とは異なる！)
System.out.println(-7 % 2);   // -1 (Python は 1)

// Python と同じ結果を得る方法
int a = -7, b = 2;
int floorDiv = Math.floorDiv(a, b);  // -4 (Python の // と同じ)
int floorMod = Math.floorMod(a, b);  // 1  (Python の % と同じ)

ArrayList の remove (★★)

ArrayList<Integer> に対して list.remove(2) を呼ぶと、「インデックス 2 の要素」が削除されます。値 2 を削除したい場合は Integer.valueOf(2) に変換する必要があります。

import java.util.*;

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));

// インデックス2の要素 (= 値3) を削除
list.remove(2);
System.out.println(list);  // [1, 2, 4, 5]

// 値2を削除したい場合は Integer にキャスト
list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
list.remove(Integer.valueOf(2));
System.out.println(list);  // [1, 3, 4, 5]

配列のコピー (★)

配列を = で代入すると、コピーではなく「参照のコピー」になります。一方を変更すると他方も変わります。

int[] a = {1, 2, 3};
int[] b = a;       // b は a と同じ配列を指す (参照コピー)
b[0] = 100;
System.out.println(a[0]);  // 100 (a も変わる！)

// 正しいコピーの方法
int[] c = Arrays.copyOf(a, a.length);  // 新しい配列にコピー
c[0] = 999;
System.out.println(a[0]);  // 100 (a は変わらない)
// または
int[] d = a.clone();

出力のバッファリング (★★)

大量に System.out.println() を呼ぶと TLE になることがあります。

import java.io.*;

// 悪い例 (100000 回の println は遅い)
for (int i = 0; i < 100000; i++) {
    System.out.println(i);
}

// 良い例1 (StringBuilder でまとめる)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 100000; i++) {
    sb.append(i).append('\n');
}
System.out.print(sb);

// 良い例2 (PrintWriter + BufferedWriter)
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
for (int i = 0; i < 100000; i++) {
    pw.println(i);
}
pw.flush();  // 最後に flush を忘れずに

再帰の深さ (★)

Java のデフォルトのスタックサイズには制限があり、再帰が深すぎると StackOverflowError が発生します。通常は数千回の再帰まで問題ありませんが、問題によってはイテレーション (ループ) に書き換える必要があります。

// 深すぎる再帰は StackOverflowError を引き起こす
static void deep(int n) {
    if (n == 0) return;
    deep(n - 1);  // n が大きいと StackOverflowError
}

AtCoder ではスタックサイズは問題ないことが多いですが、木の深さが O(N) になるような問題では注意が必要です。

オートボクシングの落とし穴 (★)

Integer (ラッパー型) を == で比較すると、値が -128〜127 の範囲では正しく動作しますが、それ以外では予期しない結果になります。

Integer a = 1000;
Integer b = 1000;
System.out.println(a == b);       // false (1000 はキャッシュ範囲外)
System.out.println(a.equals(b));  // true (内容比較)

// -128〜127 はキャッシュされるので == でも true になる (偶然の一致)
Integer x = 100;
Integer y = 100;
System.out.println(x == y);  // true (たまたまキャッシュが効く)

Integer の比較には必ず .equals() を使ってください。

double の精度 (★)

System.out.println(0.1 + 0.2 == 0.3);  // false (浮動小数点誤差)
System.out.println(0.1 + 0.2);          // 0.30000000000000004

// 誤差を許容した比較
double eps = 1e-9;
System.out.println(Math.abs(0.1 + 0.2 - 0.3) < eps);  // true

浮動小数点同士の等値比較は避け、許容誤差 (epsilon) を使って比較します。

よく使う高速入出力テンプレート

競技プログラミングで TLE を避けるために、入出力を高速化したテンプレートです。

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int N = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] a = new long[N];
        for (int i = 0; i < N; i++) a[i] = Long.parseLong(st.nextToken());

        // 処理
        long ans = 0;
        for (long x : a) ans += x;

        pw.println(ans);
        pw.flush();  // 必ず最後に flush する
    }
}

練習問題

EX24. 再帰関数2

---

付録: AtCoder Java テンプレート

以下は AtCoder での Java プログラムの基本テンプレートです。

シンプル版 (Scanner 使用):

import java.util.*;
import java.io.*;

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

        // ここに解法を書く
        int N = sc.nextInt();
        // ...

    }
}

高速入出力版 (BufferedReader / PrintWriter 使用):

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        // 1行から整数を1つ読む
        int N = Integer.parseInt(br.readLine().trim());

        // 1行からスペース区切りの複数の整数を読む
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        // ここに解法を書く
        pw.println(a + b);
        pw.flush();  // 忘れずに!
    }
}