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

4.00. 第4章について

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

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

---

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

キーポイント

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

順列 (permutations)

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

Java (再帰実装):

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++) {
            // swap
            int tmp = arr[start]; arr[start] = arr[i]; arr[i] = tmp;
            permutations(arr, start + 1);
            // swap back
            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]

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) {
            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);
    }
}

組み合わせ (combinations)

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

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) {
            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);
        }
    }

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

実行結果:

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

直積 (product)

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 を表す
}

計算量の目安

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

---

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

キーポイント

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

ArrayDeque (両端キュー)

Python の collections.deque に対応:

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));

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

        q.addLast(10);                      // 右端に追加 (append)
        q.addFirst(20);                     // 左端に追加 (appendleft)
        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 (末尾を参照)
    }
}

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 (幅優先探索) での使い方

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);
        dist[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]
    }
}

defaultdict の代替

Python: defaultdict(int) → 存在しないキーにアクセスすると 0 が返る

Java: getOrDefault() または putIfAbsent() を使う

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
        d.put("x", d.getOrDefault("x", 0) + 10);   // d["x"] = 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);
        }
        System.out.println(counter);
    }
}

Counter の代替

Python: collections.Counter(vals)

Java:

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
        System.out.println(c.getOrDefault(10, 0)); // 0 (存在しないキーは 0)

        // 出現頻度でソート (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());
        }
    }
}

Counter 同士の演算の代替

HashMap<String, Integer> c1 = new HashMap<>();
for (char ch : "aaabbc".toCharArray()) c1.merge(String.valueOf(ch), 1, Integer::sum);

HashMap<String, Integer> c2 = new HashMap<>();
for (char ch : "abbbd".toCharArray()) c2.merge(String.valueOf(ch), 1, Integer::sum);

// 和 (c1 + c2)
HashMap<String, Integer> sum = new HashMap<>(c1);
for (var entry : c2.entrySet()) {
    sum.merge(entry.getKey(), entry.getValue(), Integer::sum);
}
System.out.println(sum);

// 差 (c1 - c2): 0以下は除外
HashMap<String, Integer> diff = new HashMap<>();
for (var entry : c1.entrySet()) {
    int val = entry.getValue() - c2.getOrDefault(entry.getKey(), 0);
    if (val > 0) diff.put(entry.getKey(), val);
}
System.out.println(diff);

---

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

キーポイント

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

PriorityQueue (優先度付きキュー)

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);         // [4, 6, 8] (heapifyされた状態)

        pq.add(2);
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");  // 2 4 6 8
        }
        System.out.println();
    }
}

PriorityQueue の操作一覧

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

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

import java.util.*;

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 (最大値)

Python の「負数にして最小ヒープ」と同様の方法 (int の場合):

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, データ0 (task_A)
        pq.add(new int[]{10, 1});  // 優先度10, データ1 (task_B)
        pq.add(new int[]{20, 2});  // 優先度20, データ2 (task_C)

        System.out.println(Arrays.toString(pq.poll()));  // [10, 1] (task_B)
        pq.add(new int[]{25, 3});  // task_D
        System.out.println(Arrays.toString(pq.poll()));  // [20, 2] (task_C)
    }
}

二分探索 (bisect の代替)

Arrays.binarySearch:

import java.util.Arrays;

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

        // 挿入位置を求める (bisect_left の代替)
        int pos = Arrays.binarySearch(a, 30);
        // 見つからない場合: -(挿入位置) - 1 が返る
        if (pos < 0) pos = -(pos + 1);
        System.out.println(pos);  // 2 (bisect_left(a, 30) と同じ)
    }
}

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
        System.out.println(bisectRight(a, 60));  // 4
    }
}

TreeSet を使った bisect の代替

TreeSet の floor(), ceiling(), lower(), higher() が特定の用途では有効です:

import java.util.TreeSet;

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 クラス

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        // GCD / LCM
        System.out.println(gcd(10, 15));  // 5
        System.out.println(lcm(10, 15));  // 30

        // 組み合わせ (comb)
        System.out.println(comb(100, 20));  // 535983370403809682970...

        // 階乗
        System.out.println(factorial(20));  // 2432902008176640000

        // 数学関数
        System.out.println(Math.log(Math.E));   // 1.0 (自然対数)
        System.out.println(Math.log10(100));     // 2.0
        System.out.println(Math.log(8) / Math.log(2));  // 3.0 (log2(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
    }

    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;
    }

    // 複数値の gcd
    static long gcd(long[] vals) {
        long g = vals[0];
        for (long v : vals) g = gcd(g, v);
        return g;
    }

    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;
        long result = 1;
        for (int i = 0; i < k; i++) {
            result = result * (n - i) / (i + 1);
        }
        return result;
    }
}

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

Python の多倍長整数の代わり:

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger a = BigInteger.valueOf(3).pow(1000);
        System.out.println(a);  // 3^1000 (478桁の数)

        // GCD
        BigInteger x = BigInteger.valueOf(12);
        BigInteger y = BigInteger.valueOf(8);
        System.out.println(x.gcd(y));  // 4

        // 組み合わせ (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;
    }
}

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〜1 の乱数
        System.out.println(rng.nextInt(5) + 5);    // 5〜9 の整数乱数
        System.out.println(rng.nextInt(3));         // 0, 1, 2 のいずれか

        // リストからランダム選択
        int[] choices = {1, 2, 3};
        int chosen = choices[rng.nextInt(choices.length)];
        System.out.println(chosen);

        // 配列をシャッフル
        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));
    }
}

時間計測

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 > 1000) break;  // 1秒経過で終了
}

---

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

キーポイント

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

メモ化の基本

Python:

from functools import cache

@cache
def fib(n):
    if n <= 0: return 0
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

Java (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 (高速)
    }
}

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

import java.util.HashMap;

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

    // encode(i, j) でキーを作る
    static long encode(int i, int j) {
        return (long) i * 100000 + 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 (格子上の経路数)
    }
}

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

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];
        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);
        System.out.println(fib(50));  // 12586269025
    }
}

練習問題

EX23. 再帰関数1

---

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

キーポイント

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

BigDecimal (Decimal の代替)

import java.math.BigDecimal;

public class Main {
    public static void main(String[] args) {
        // 浮動小数点の問題
        System.out.println(0.1 + 0.2 == 0.3);  // false

        // 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
    }
}

重要: new BigDecimal(0.1) は誤差あり。new BigDecimal("0.1") が正確です。

有理数クラスの自前実装

public class Main {
    static class Fraction {
        long num, den;  // 分子, 分母

        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 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);
        Fraction y = new Fraction(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
    }
}

---

4.07. TreeSet・TreeMap (sortedcontainers の代替)

キーポイント

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

TreeSet (SortedSet の代替)

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));

        // bisect_left の代替: x 以上の最小要素のインデックス
        // → ceiling(x) で x 以上の最小要素を直接取得
        System.out.println(s.ceiling(4));   // 5 (bisect_left(s, 4)番目の要素)
        System.out.println(s.floor(4));     // 3 (4以下の最大値)

        s.add(6);
        s.remove(5);
        System.out.println(s.ceiling(4));   // 6

        // 最小値・最大値
        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 (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);

        // 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);
    }

    static void remove(int x) {
        int cnt = multiset.getOrDefault(x, 0);
        if (cnt == 1) multiset.remove(x);
        else multiset.put(x, cnt - 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);
        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
    }
}

---

4.08. クラス

キーポイント

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

基本的なクラス定義

class Person {
    String name;
    int age;

    // コンストラクタ
    Person(String name, int age) {
        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
    }
}

メソッドの定義

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 + ".");
    }
}

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

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

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.add(w));  // (x=13.0, y=24.0)
    }
}

実用例: 合計付きリスト

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]
    }
}

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

クラスのオブジェクトをソートしたい場合は Comparable<T> を実装します:

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) {
        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);
        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 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 * int の結果が long に入っても int でオーバーフローする
int x = 100000;
long bad = x * x;       // 1410065408 (オーバーフロー後の値が long に入る)
long good = (long)x * x; // 10000000000 (正しい)

文字列の比較 (★★★)

// 悪い例
String a = new String("Hello");
String b = new String("Hello");
System.out.println(a == b);       // false (参照の比較)

// 良い例
System.out.println(a.equals(b));  // true (内容の比較)

// null チェックが必要な場合
String s = null;
// s.equals("Yes")  → NullPointerException
"Yes".equals(s);    // false (null セーフ)

Scanner の 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() が空文字を返す
        sc.nextLine();     // 改行を読み捨てる
        String s = sc.nextLine();  // 正しく読める
        System.out.println(n);
        System.out.println(s);
    }
}

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

// 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 と同じ結果を得る方法 (負の数の floor 除算)
int a = -7, b = 2;
int floorDiv = Math.floorDiv(a, b);  // -4 (Python の // と同じ)
int floorMod = Math.floorMod(a, b);  // 1  (Python の % と同じ)

ArrayList の remove (★★)

import java.util.*;

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

// list.remove(2) はインデックス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[0] = 100;
System.out.println(a[0]);  // 100 (a も変わる！)

// 正しいコピー
int[] c = Arrays.copyOf(a, a.length);  // 新しい配列にコピー
// または
int[] d = a.clone();

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

大量に System.out.println() を呼ぶと遅くなります:

import java.io.*;

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

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

// または PrintWriter + BufferedWriter
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
for (int i = 0; i < 100000; i++) {
    pw.println(i);
}
pw.flush();

再帰の深さ (★)

Java のデフォルトのスタックサイズは JVM に依存します (通常 500〜10000 回程度)。深い再帰には StackOverflowError が発生します。

// 深すぎる再帰は StackOverflowError
static void deep(int n) {
    if (n == 0) return;
    deep(n - 1);
}

// 対策: 反復に書き換える or スタックサイズを増やす
// AtCoder では通常問題なし (多くの問題では再帰深さは O(log N) 程度)

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

Integer a = 1000;
Integer b = 1000;
System.out.println(a == b);       // false (Integer は -128〜127 以外は参照比較)
System.out.println(a.equals(b));  // true (内容比較)

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

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

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

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();
    }
}

練習問題

EX24. 再帰関数2

---

付録: AtCoder Java テンプレート

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

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

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

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

    }
}

高速入出力版:

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());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        pw.println(a + b);
        pw.flush();
    }
}