APG4b Java版

テーマ

APG4b Java版 第3章: 言語機能 ​

3.00. 第3章について ​

第2章をすべて完了したあなたは、実際にすべての「計算処理」を行うプログラムを書ける程の知識を身につけました。

第3章では、競技プログラミングで実用的にプログラムを書くために必要な Java の言語機能について解説します。この章をマスターすると、より多くの競技プログラミングの問題を解けるようになります。

3.01. Java で使える機能の整理 ​

キーポイント ​

  • Java のコードは「自分で定義したもの」「標準で使えるもの」「import したもの」の3つに分類できる
  • java.lang.* は自動的にインポートされる (String, Math, System など)
  • それ以外のクラスは import 文で明示的にインポートが必要

Java コードの3つの要素 ​

要素1: 自分で定義した変数・メソッド

java
public class Main {
    static int a = 0;
    static int[] l = {3, 2, 1, 1};

    static int func(int x) {
        return 2 * x;
    }

    public static void main(String[] args) {
        System.out.println(a);
        System.out.println(func(a));
    }
}

要素2: 標準で使えるクラス (java.lang パッケージ)

インポートなしで使えるクラス:

  • String - 文字列
  • Math - 数学関数
  • System - 入出力
  • Integer, Long, Double - プリミティブ型のラッパー
  • StringBuilder - 可変文字列
java
// import なしで使える
int[] sorted = {1, 3, 2};
String s = String.valueOf(42);
double d = Math.sqrt(16.0);
System.out.println(d);  // 4.0

要素3: import が必要なクラス

java
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.*;  // java.util の全クラスをインポート

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        Scanner sc = new Scanner(System.in);
    }
}

よく使う import 一覧 ​

java
import java.util.*;          // Scanner, ArrayList, HashMap, Arrays, Collections 等
import java.io.*;            // BufferedReader, PrintWriter 等 (高速入出力)
import java.math.BigInteger; // 多倍長整数
import java.math.BigDecimal; // 高精度浮動小数点

競技プログラミングでは import java.util.*; と import java.io.*; を最初に書いておくと便利です。

コードの読み方 ​

見慣れない識別子が出てきたら:

  1. 自分で定義した変数・メソッドか？ (= や static を探す)
  2. java.lang パッケージの標準クラスか？ (ドキュメント確認)
  3. import されたクラスか？ (ファイル先頭の import を確認)

3.02. コレクション (組み込みコンテナ) ​

キーポイント ​

  • Java の主要コレクション: int[] / ArrayList, HashSet, HashMap
  • Python の list → Java の int[] (固定長) または ArrayList<Integer> (可変長)
  • Python の set → Java の HashSet<T>
  • Python の dict → Java の HashMap<K, V>
  • TreeSet / TreeMap はソート済みを保証する

ArrayList (Python の list に対応) ​

操作JavaPython計算量
値のアクセスlist.get(i)l[i]O(1)
値の変更list.set(i, x)l[i] = xO(1)
末尾に追加list.add(x)l.append(x)O(1)
途中に挿入list.add(i, x)l.insert(i, x)O(N)
末尾を削除list.remove(list.size()-1)l.pop()O(1)
途中を削除list.remove(i) (インデックス指定)l.pop(i)O(N)
サイズlist.size()len(l)O(1)
存在確認list.contains(x)x in lO(N)
出現回数Collections.frequency(list, x)l.count(x)O(N)

コード例:

java
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> l = new ArrayList<>();
        l.add(3); l.add(1); l.add(7); l.add(1); l.add(5);

        System.out.println(l.get(2));      // 7
        l.set(2, 7);
        System.out.println(l);            // [3, 1, 7, 1, 5]
        l.add(9);
        System.out.println(l);            // [3, 1, 7, 1, 5, 9]
        l.add(3, 8);                      // インデックス3に8を挿入
        System.out.println(l);            // [3, 1, 7, 8, 1, 5, 9]
        l.remove(l.size() - 1);           // 末尾削除
        System.out.println(l);            // [3, 1, 7, 8, 1, 5]
        l.remove(0);                      // 先頭削除
        System.out.println(l);            // [1, 7, 8, 1, 5]
        System.out.println(l.size());     // 5
        System.out.println(l.contains(1)); // true
        System.out.println(l.contains(3)); // false
    }
}

HashSet (Python の set に対応) ​

操作JavaPython計算量
追加s.add(x)s.add(x)O(1)
削除s.remove(x)s.remove(x)O(1)
サイズs.size()len(s)O(1)
存在確認s.contains(x)x in sO(1)

コード例:

java
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<Integer> s = new HashSet<>();
        s.add(1); s.add(3); s.add(5);
        s.add(2);
        System.out.println(s);            // [1, 2, 3, 5] (順不定)
        s.remove(3);
        System.out.println(s.size());     // 3
        System.out.println(s.contains(2)); // true
        System.out.println(s.contains(3)); // false
    }
}

注意: HashSet は順序を保証しません。順序が必要な場合は TreeSet を使います。

Set 演算 (和集合・積集合・差集合) ​

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        HashSet<Integer> s = new HashSet<>(Arrays.asList(1, 2));
        HashSet<Integer> t = new HashSet<>(Arrays.asList(1, 3));

        // 和集合 (s | t)
        HashSet<Integer> union = new HashSet<>(s);
        union.addAll(t);
        System.out.println(union);  // [1, 2, 3]

        // 積集合 (s & t)
        HashSet<Integer> inter = new HashSet<>(s);
        inter.retainAll(t);
        System.out.println(inter);  // [1]

        // 差集合 (s - t)
        HashSet<Integer> diff = new HashSet<>(s);
        diff.removeAll(t);
        System.out.println(diff);   // [2]
    }
}

TreeSet (ソート済み Set) ​

java
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> s = new TreeSet<>();
        s.add(5); s.add(2); s.add(8); s.add(1);
        System.out.println(s);        // [1, 2, 5, 8] (昇順ソート)
        System.out.println(s.first()); // 1 (最小値)
        System.out.println(s.last());  // 8 (最大値)

        // x 未満の最大要素
        System.out.println(s.lower(5));  // 2
        // x 以下の最大要素
        System.out.println(s.floor(5));  // 5
        // x より大きい最小要素
        System.out.println(s.higher(5)); // 8
        // x 以上の最小要素
        System.out.println(s.ceiling(3)); // 5
    }
}

リストの重複除去 (Python の list(set(l))) ​

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] a = {30, 10, 40, 10, 50};
        ArrayList<Integer> list = new ArrayList<>();
        for (int x : a) list.add(x);

        // 重複除去 (順序不定)
        HashSet<Integer> set = new HashSet<>(list);
        System.out.println(set);  // [50, 10, 30, 40] など

        // 重複除去 + ソート
        TreeSet<Integer> sorted = new TreeSet<>(list);
        System.out.println(sorted);  // [10, 30, 40, 50]
    }
}

HashMap (Python の dict に対応) ​

操作JavaPython計算量
値のアクセスd.get(k)d[k]O(1)
値の追加・更新d.put(k, v)d[k] = vO(1)
キーの削除d.remove(k)d.pop(k)O(1)
サイズd.size()len(d)O(1)
キー存在確認d.containsKey(k)k in dO(1)
デフォルト値で取得d.getOrDefault(k, def)d.get(k, def)O(1)

コード例:

java
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> d = new HashMap<>();
        d.put("Alice", 100);
        d.put("Bob", 89);
        d.put("Charlie", 95);

        System.out.println(d.get("Alice"));  // 100
        d.put("Dave", 77);
        d.put("Charlie", 59);
        d.remove("Bob");

        for (var entry : d.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

defaultdict の代わり (存在しないキーにデフォルト値を使う):

java
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        int[] l = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
        HashMap<Integer, Integer> counter = new HashMap<>();
        for (int x : l) {
            counter.put(x, counter.getOrDefault(x, 0) + 1);
        }
        for (var entry : counter.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

または merge を使った書き方:

java
counter.merge(x, 1, Integer::sum);  // x のカウントを1増やす

TreeMap (ソート済み Map) ​

java
import java.util.TreeMap;

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "three");
map.put(1, "one");
map.put(4, "four");
System.out.println(map);  // {1=one, 3=three, 4=four} (キーで昇順ソート)
System.out.println(map.firstKey());  // 1
System.out.println(map.lastKey());   // 4

for 文での列挙 ​

java
HashMap<String, Integer> d = new HashMap<>();
d.put("Alice", 100); d.put("Bob", 89);

// キーのみ
for (String k : d.keySet()) System.out.println(k);

// 値のみ
for (int v : d.values()) System.out.println(v);

// キーと値
for (var entry : d.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

練習問題 ​

EX20. 最頻値

3.03. 書式付き出力 (String.format と printf) ​

キーポイント ​

  • String.format() で書式付き文字列を作成 (Python の f"..." に相当)
  • System.out.printf() で書式付き出力
  • 小数点桁数、進数、ゼロパディングなどの書式指定が可能

String.format の基本 ​

java
String name = "Takahashi";
System.out.println(String.format("Hello, %s!", name));
// 出力: Hello, Takahashi!
java
int intVal = 123;
double floatVal = 3.1415;
String strVal = "Hello";
System.out.printf("%d %.2f %s%n", intVal, floatVal, strVal);
// 出力: 123 3.14 Hello

書式指定子一覧 ​

指定子意味Python 対応
%d整数 (10進数)%d
%f浮動小数点%f
%.2f小数点以下2桁:.2f
%e指数形式:e
%s文字列%s
%x16進数 (小文字):x
%X16進数 (大文字):X
%o8進数:o
%n改行\n

小数点以下の桁数指定 ​

java
double val = 3.1415;
System.out.printf("%.2f%n", val);  // 3.14
System.out.printf("%.3f%n", val);  // 3.142
System.out.printf("%.8f%n", val);  // 3.14150000

進法変換 ​

java
int value = 29;
System.out.printf("%s%n", Integer.toBinaryString(value)); // 2進法: 11101
System.out.printf("%o%n", value);  // 8進法: 35
System.out.printf("%x%n", value);  // 16進法: 1d
System.out.printf("%X%n", value);  // 16進法: 1D

ゼロパディングと桁数指定 ​

java
int val = 42;
System.out.printf("%05d%n", val);  // 00042 (5桁、ゼロ埋め)
System.out.printf("%-10d|%n", val); // 42        | (左詰め10桁)
System.out.printf("%+d%n", val);    // +42 (符号付き)
System.out.printf("%,d%n", 1234567); // 1,234,567 (3桁カンマ)

String.format を使った文字列生成 ​

java
int a = 10, b = 20;
String s = String.format("%d + %d = %d", a, b, a + b);
System.out.println(s);  // 10 + 20 = 30

Python の f-string との比較 ​

Python f-stringJava
f"Hello, {name}!"String.format("Hello, %s!", name)
f"{val:.2f}"String.format("%.2f", val)
f"{val:b}"Integer.toBinaryString(val)
f"{val:x}"String.format("%x", val)
f"{val:05d}"String.format("%05d", val)
f"{val:>10}"String.format("%10d", val)
f"{val:<10}"String.format("%-10d", val)

書式付き出力のチートシート ​

java
double pi = Math.PI;
System.out.printf("%.13f%n", pi);  // 小数点以下13桁
System.out.printf("%e%n", pi);     // 指数形式
System.out.printf("%o%n", 255);    // 8進数
System.out.printf("%x%n", 255);    // 16進数 (ff)
System.out.printf("%08d%n", 42);   // ゼロパディング (00000042)
System.out.printf("%+d%n", 42);    // 符号付き (+42)
System.out.printf("%.2f%%%n", 75.5); // パーセント (75.50%)
System.out.printf("%,d%n", 1000000); // カンマ区切り (1,000,000)
System.out.printf("%15d%n", 42);   // 右詰め15桁
System.out.printf("%-15d|%n", 42); // 左詰め15桁

3.04. ビット演算 ​

キーポイント ​

  • Java のビット演算子は Python とほぼ同じ
  • & (AND), | (OR), ^ (XOR), << (左シフト), >> (右シフト), ~ (NOT)
  • >>> (符号なし右シフト) は Java 固有の演算子
  • Python と異なり、Java の >> は符号ビットを保持する (算術シフト)

ビット演算の種類 ​

演算演算子意味例 (10進)例 (2進)
AND&両方が1なら16 & 3 → 2110 & 011 = 010
OR|一方が1なら16 | 3 → 7110 | 011 = 111
XOR^一方だけが1なら16 ^ 3 → 5110 ^ 011 = 101
左シフト<<ビット列を左にずらす3 << 2 → 1211 → 1100
右シフト>>符号付き右シフト13 >> 2 → 31101 → 11
符号なし右シフト>>>符号ビットも0で埋める-1 >>> 1 → 2^31-1
NOT~ビットを反転~6 → -700110 → 11001

AND・OR・XOR 演算 ​

java
public class Main {
    public static void main(String[] args) {
        System.out.println(6 & 3);   // 2
        System.out.println(6 | 3);   // 7
        System.out.println(6 ^ 3);   // 5
    }
}

ビットシフト ​

java
System.out.println(3 << 2);    // 12 (3 * 2^2)
System.out.println(13 >> 2);   // 3  (13 / 2^2)
System.out.println(-3 << 2);   // -12
System.out.println(-13 >> 2);  // -4 (Python と同じ)
System.out.println(-1 >>> 1);  // 2147483647 (符号なし右シフト)

NOT 演算 ​

java
System.out.println(~6);    // -7
System.out.println(~(-7)); // 6
System.out.println(~~100); // 100
// ~x = -(x+1) と等価

演算子の優先順位 (上ほど高い) ​

~ (単項) > * / % > + - > << >> >>> > & > ^ > | > 比較演算子 > && > ||

java
System.out.println(1 << 5 - 1);      // 16  (5-1=4, 1<<4)
System.out.println((1 << 5) - 1);    // 31
System.out.println(1 & 2 + 3);       // 1   (2+3=5, 1&5=1)
System.out.println((1 & 2) + 3);     // 3

ビットの取得 ​

java
int x = 13;  // 2進法で 1101
for (int i = 0; i < 5; i++) {
    System.out.println((x >> i) & 1);
}
// 出力: 1 0 1 1 0 (ビット 0, 1, 2, 3, 4)

ビット全探索 ​

N 個の要素の全部分集合を列挙します (2^N 通り):

java
public class Main {
    public static void main(String[] args) {
        int N = 3;
        for (int i = 0; i < (1 << N); i++) {
            ArrayList<Integer> L = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                if (((i >> j) & 1) == 1) {
                    L.add(j);
                }
            }
            System.out.println(i + " " + L);
        }
    }
}

実行結果:

0 []
1 [0]
2 [1]
3 [0, 1]
4 [2]
5 [0, 2]
6 [1, 2]
7 [0, 1, 2]

最下位ビットの取得 ​

java
int x = 12;  // 1100
System.out.println(x & (-x));   // 4  (最下位の1ビット)
int y = 99;  // 1100011
System.out.println(y & (-y));   // 1

集合のビット演算 (ナップサック問題の例) ​

java
public class Main {
    public static void main(String[] args) {
        int[] A = {3, 5, 7, 11};
        int W = 20;

        // long を使ってビット列で到達可能な重量を管理
        long s = 1;  // ビット0が立っている = 重量0が実現可能
        for (int a : A) {
            s |= s << a;
        }

        // W以下の実現可能な重量を出力
        for (int w = 0; w <= W; w++) {
            if (((s >> w) & 1) == 1) {
                System.out.println(w + " は実現可能");
            }
        }
    }
}

練習問題 ​

EX21. Bitwise Exclusive Or

3.05. 発展的な文法 ​

キーポイント ​

  • 三項演算子: 条件 ? X : Y (Python の X if 条件 else Y に対応)
  • 短絡評価: && で左が false なら右は評価されない
  • ラムダ式: (引数) -> 処理 で1行のメソッドを表現 (Python の lambda に対応)
  • デフォルト引数はない → メソッドオーバーロードで代替

三項演算子 ​

「条件が true であれば X、そうでなければ Y」を返す式:

java
public class Main {
    public static void main(String[] args) {
        int[] result = new int[10];
        for (int i = 0; i < 10; i++) {
            result[i] = (i % 2 == 0) ? i : i * 100;
        }
        // 出力: [0, 100, 2, 300, 4, 500, 6, 700, 8, 900]
        for (int x : result) System.out.print(x + " ");
        System.out.println();
    }
}

Python の内包表記との比較:

  • Python: [i if i%2==0 else i*100 for i in range(10)]
  • Java: 配列 + ループ + 三項演算子

短絡評価 (ショートサーキット) ​

java
public class Main {
    static boolean hello() {
        System.out.println("Hello");
        return true;
    }

    public static void main(String[] args) {
        if (true || hello()) {       // hello() は呼ばれない
            System.out.println("条件式はtrue");
        }
        if (false && hello()) {      // hello() は呼ばれない
            System.out.println("条件式はfalse");
        }
    }
}

実行結果:

条件式はtrue

|| で左が true なら右は評価されず、&& で左が false なら右は評価されません。

ラムダ式 ​

Java 8以降では (引数) -> 処理 の形でラムダ式を書けます。

java
import java.util.function.Function;

public class Main {
    // 通常のメソッド
    static int func1(int a) {
        return a + 10;
    }

    public static void main(String[] args) {
        // ラムダ式 (Python の lambda a: a+10 に対応)
        Function<Integer, Integer> func2 = a -> a + 10;

        System.out.println(func1(1));       // 11
        System.out.println(func2.apply(1)); // 11
    }
}

ラムダ式は主に Comparator などに渡す場合に使います:

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(2, 6, 11, 100));

        // 1の位でソート
        list.sort((x, y) -> (x % 10) - (y % 10));
        System.out.println(list);  // [100, 11, 2, 6]
    }
}

デフォルト引数の代替: メソッドオーバーロード ​

Python の def func(a, start=0): に対応する Java の書き方:

java
public class Main {
    static void addVals(int[] a) {
        addVals(a, 0);  // デフォルト値 0 でもう一方を呼ぶ
    }

    static void addVals(int[] a, int start) {
        for (int i = 0; i < a.length; i++) {
            a[i] += i + start;
        }
    }

    public static void main(String[] args) {
        int[] a = {3, 1, 2};
        int[] b = {4, 5, 6};
        int[] c = {3, 3, 1};

        addVals(a);        // start = 0 (デフォルト)
        addVals(b);
        addVals(c, 1);     // start = 1

        System.out.println(Arrays.toString(a));  // [3, 2, 4]
        System.out.println(Arrays.toString(b));  // [4, 6, 8]
        System.out.println(Arrays.toString(c));  // [4, 5, 4]
    }
}

キーワード引数の代替 ​

Java にはキーワード引数がないため、オーバーロードや Builder パターンで対応します。

3.06. いろいろなソート ​

キーポイント ​

  • Arrays.sort(a) は配列を昇順にソート (in-place)
  • Collections.sort(list) は ArrayList を昇順にソート (in-place)
  • 降順ソートは Comparator.reverseOrder() を使う
  • カスタムソートは Comparator または ラムダ式で定義

メソッドの違い ​

  • Arrays.sort(a): 配列の中身を昇順に変更
  • Arrays.sort(a, comparator): 配列を指定した順序でソート (プリミティブ配列では使えない)
java
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] a = {5, 4, 1, 3, 2};
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));  // [1, 2, 3, 4, 5]
    }
}

ArrayList のソート ​

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(5, 4, 1, 3, 2));

        ArrayList<Integer> sorted = new ArrayList<>(list);
        Collections.sort(sorted);
        System.out.println(list);    // [5, 4, 1, 3, 2] (変化なし)
        System.out.println(sorted);  // [1, 2, 3, 4, 5]

        list.sort(null);  // 昇順ソート (in-place)
        System.out.println(list);    // [1, 2, 3, 4, 5]
    }
}

文字列・タプルなどのソート ​

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 文字列のソート (辞書順)
        ArrayList<String> words = new ArrayList<>(Arrays.asList("banana", "apple", "cherry"));
        Collections.sort(words);
        System.out.println(words);  // [apple, banana, cherry]

        // int[] の配列 (行ごとに先頭要素でソート)
        int[][] pairs = {{3, 5}, {1, 8}, {2, 3}};
        Arrays.sort(pairs, (x, y) -> x[0] - y[0]);
        for (int[] p : pairs) System.out.println(Arrays.toString(p));
        // [1, 8], [2, 3], [3, 5]
    }
}

降順ソート ​

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
        list.sort(Comparator.reverseOrder());
        System.out.println(list);  // [4, 3, 2, 1]

        // int 配列の降順ソート (プリミティブ配列は reverseOrder が使えないのでひと工夫)
        int[] a = {3, 1, 4, 1, 5};
        Integer[] boxed = Arrays.stream(a).boxed().toArray(Integer[]::new);
        Arrays.sort(boxed, Comparator.reverseOrder());
        System.out.println(Arrays.toString(boxed));  // [5, 4, 3, 1, 1]
    }
}

カスタムソート (key 引数の代替) ​

Python の l.sort(key=lambda x: x%10) に対応:

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(2, 6, 11, 100));

        // 1の位でソート
        list.sort((x, y) -> (x % 10) - (y % 10));
        System.out.println(list);  // [100, 11, 2, 6]
    }
}

比較関数によるソート (Comparator) ​

java
import java.util.*;

public class Main {
    // 絶対値でソートする比較関数
    static int compareByAbs(int x, int y) {
        return Math.abs(x) - Math.abs(y);
    }

    public static void main(String[] args) {
        ArrayList<Integer> A = new ArrayList<>(Arrays.asList(-3, 1, 4, 2, -5));
        A.sort((x, y) -> compareByAbs(x, y));
        System.out.println(A);  // [1, 2, -3, 4, -5]
    }
}

多項目ソート (複数のキーでソート) ​

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // [名前, 得点] の2次元配列を得点降順、得点が同じなら名前昇順でソート
        String[][] data = {{"Alice", "85"}, {"Bob", "90"}, {"Carol", "85"}};
        Arrays.sort(data, (a, b) -> {
            int scoreA = Integer.parseInt(a[1]);
            int scoreB = Integer.parseInt(b[1]);
            if (scoreA != scoreB) return scoreB - scoreA;  // 得点降順
            return a[0].compareTo(b[0]);                    // 名前昇順
        });
        for (String[] d : data) System.out.println(Arrays.toString(d));
    }
}

実行結果:

[Bob, 90]
[Alice, 85]
[Carol, 85]

練習問題 ​

EX22. 2つ目の値でソート

APG4bPython の教材を Java 向けに書き直したものです。

Based on AtCoder Programming Guide for Python