APG4b Java版

テーマ

APG4b Java版 第2章: 実践的な書き方と計算量 ​

2.00. 第2章について ​

第1章の内容をマスターすることで、理論上すべての計算処理を行うプログラムを書けるようになりました。

第2章では、複雑な計算をどのように記述するか、また Java に固有の便利な書き方を説明します。さらに、実行時間の見積もりに使う「計算量」の概念を学びます。第2章をマスターすると、実際にほぼすべての計算処理プログラムを実用的に書けるようになります。

AtCoder での練習について:

  • AtCoder Beginner Contest (ABC) ... 毎週土曜夜に開催
  • AtCoder Daily Training (ADT) ... 過去問を使ったバーチャルコンテスト
  • AtCoder 強化プラン ... コンテストの復習や別の学習法

2.01. いろいろな for 文 ​

キーポイント ​

  • インデックス付き for: for (int i = 0; i < N; i++)
  • 拡張 for 文 (foreach): for (型 変数 : コレクション)
  • 複数リストを同時にループ: インデックスを使う
  • break でループを抜ける、continue で次のイテレーションへ

基本の for 文パターン ​

range(stop) の代わり:

java
for (int i = 0; i < 5; i++) {
    System.out.println(i);
}

実行結果:

0
1
2
3
4

range(start, stop) の代わり:

java
for (int i = 2; i < 5; i++) {
    System.out.println(i);
}

実行結果:

2
3
4

range(start, stop, step) の代わり:

java
for (int i = 4; i < 10; i += 2) {
    System.out.println(i);
}

実行結果:

4
6
8

逆順:

java
for (int i = 5; i >= 0; i--) {
    System.out.println(i);
}

実行結果:

5
4
3
2
1
0

配列・ArrayList に対する for 文 ​

拡張 for 文 (Python の for x in L: に相当):

java
int[] a = {3, 1, 4, 1, 5};
for (int x : a) {
    System.out.println(x);
}

文字列の各文字を処理:

java
String s = "AtCoder";
for (char c : s.toCharArray()) {
    System.out.println(c);
}

2次元配列のアンパック (Python の for a, b in [[5, 10], [6, 20]]:):

java
int[][] pairs = {{5, 10}, {6, 20}};
for (int[] pair : pairs) {
    int a = pair[0], b = pair[1];
    System.out.println(a + " " + b);
}

インデックスと値を同時に処理 (Python の enumerate()) ​

Java には enumerate() がないので、インデックスを手動で管理します:

java
int[] a = {10, 20, 30};
for (int i = 0; i < a.length; i++) {
    System.out.println(i + " " + a[i]);
}

実行結果:

0 10
1 20
2 30

逆順の for (Python の reversed()) ​

java
int[] a = {3, 1, 4, 1, 5};
for (int i = a.length - 1; i >= 0; i--) {
    System.out.println(a[i]);
}

複数配列の同時ループ (Python の zip()) ​

Java には zip() がないので、インデックスを使います:

java
int[] A = {1, 2, 3};
int[] B = {10, 20, 30};

for (int i = 0; i < A.length; i++) {
    System.out.println(A[i] + " " + B[i]);
}

実行結果:

1 10
2 20
3 30

break と continue ​

java
// break: ループを抜ける
for (int i = 0; i < 5; i++) {
    if (i == 3) break;
    System.out.println(i);
}
// 出力: 0, 1, 2

// continue: 次のイテレーションへスキップ
for (int i = 0; i < 5; i++) {
    if (i == 3) continue;
    System.out.println(i);
}
// 出力: 0, 1, 2, 4

ラベル付き break (Python には for-else があるが Java では別の方法) ​

Java ではラベル付き break で外側のループを抜けられます:

java
outer:
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        if (i + j == 5) {
            System.out.println("抜ける: " + i + " " + j);
            break outer;  // 外側のループも抜ける
        }
    }
}
System.out.println("終了");

練習問題 ​

EX14. 隣り合う同じ値を探す

2.02. 多重ループ ​

キーポイント ​

  • ループの中にさらにループを書くことを「多重ループ」という
  • 内側のループで break すると内側のループのみ抜ける
  • 複数段階のループを抜けるには「ラベル付き break」または「フラグ変数」を使う
  • Python と同様の書き方が使える

基本: 二重ループ ​

java
public class Main {
    public static void main(String[] args) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.println(i + " " + j);
            }
        }
    }
}

実行結果:

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

実践例: 2つの数列に共通要素があるか判定 ​

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] A = new int[3];
        int[] B = new int[3];
        for (int i = 0; i < 3; i++) A[i] = sc.nextInt();
        for (int i = 0; i < 3; i++) B[i] = sc.nextInt();

        boolean answer = false;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (A[i] == B[j]) {
                    answer = true;
                }
            }
        }

        if (answer) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

break の動作: 内側のループのみ抜ける ​

java
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        if (j == 1) break;  // 内側の j ループのみ抜ける
        System.out.println(i + " " + j);
    }
}

実行結果:

0 0
1 0
2 0

複数段階のループから抜ける方法1: フラグ変数 ​

java
boolean finished = false;

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        System.out.println(i + " " + j);
        if (i == 1 && j == 1) {
            finished = true;
        }
        if (finished) break;
    }
    if (finished) break;
}

複数段階のループから抜ける方法2: ラベル付き break (Java の利点) ​

Python にはない Java の機能です。ラベルを使うとすっきり書けます:

java
outer:
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        System.out.println(i + " " + j);
        if (i == 1 && j == 1) {
            break outer;  // outer ラベルのループを抜ける
        }
    }
}

複数段階のループから抜ける方法3: メソッド化して return ​

java
public class Main {
    static void func() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == 1 && j == 1) return;  // メソッドを終了
                System.out.println(i + " " + j);
            }
        }
    }

    public static void main(String[] args) {
        func();
    }
}

練習問題 ​

EX15. 果物屋さんでお買い物

2.03. ループによるリスト生成 (内包表記の代替) ​

キーポイント ​

  • Java には Python のリスト内包表記がない
  • 代わりに for ループで ArrayList に add() するか、配列を使う
  • Java 8 以降の Stream API を使うと内包表記に近い書き方ができる
  • ただし競技プログラミングでは従来の for ループが読みやすく速い

Python の内包表記と Java の対応 ​

Python: [i * i for i in range(5)]

Java (forループ版):

java
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            result.add(i * i);
        }
        System.out.println(result);  // [0, 1, 4, 9, 16]
    }
}

Java (配列版):

java
int[] result = new int[5];
for (int i = 0; i < 5; i++) {
    result[i] = i * i;
}
// 出力: 0 1 4 9 16

条件付きフィルタリング (Python の [x for x in a if x % 2 == 0]) ​

java
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8};
        ArrayList<Integer> evens = new ArrayList<>();
        for (int x : a) {
            if (x % 2 == 0) {
                evens.add(x);
            }
        }
        System.out.println(evens);  // [2, 4, 6, 8]
    }
}

組み込み関数との組み合わせ ​

Python の sum([i*i for i in range(N)]):

java
int N = 5;
int sum = 0;
for (int i = 0; i < N; i++) {
    sum += i * i;
}
System.out.println(sum);  // 30

最大値・最小値:

java
int[] a = {3, 1, 4, 1, 5, 9, 2, 6};
int maxVal = a[0];
int minVal = a[0];
for (int x : a) {
    maxVal = Math.max(maxVal, x);
    minVal = Math.min(minVal, x);
}
System.out.println("max=" + maxVal + " min=" + minVal);

Stream API を使った内包表記風の書き方 (参考) ​

競技プログラミングでは使う場面が限られますが、Stream API で簡潔に書けます:

java
import java.util.Arrays;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) {
        // [i*i for i in range(5)]
        int[] result = IntStream.range(0, 5).map(i -> i * i).toArray();
        System.out.println(Arrays.toString(result));  // [0, 1, 4, 9, 16]

        // sum([i*i for i in range(5)])
        int sum = IntStream.range(0, 5).map(i -> i * i).sum();
        System.out.println(sum);  // 30

        // [x for x in a if x % 2 == 0]
        int[] a = {1, 2, 3, 4, 5, 6};
        int[] evens = Arrays.stream(a).filter(x -> x % 2 == 0).toArray();
        System.out.println(Arrays.toString(evens));  // [2, 4, 6]
    }
}

入力のリスト読み込み ​

Python の list(map(int, input().split())):

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = 5;
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }
    }
}

練習問題 ​

EX16. 英単語テストの練習

2.04. 多次元配列 ​

キーポイント ​

  • 2次元配列は int[][] a = new int[N][M] で宣言
  • a[i][j] で i 行 j 列の要素にアクセス
  • a.length で行数、a[0].length で列数を取得
  • ArrayList<ArrayList<Integer>> で可変長の2次元リストも作れる

2次元配列の基本 ​

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

        System.out.println(a[0][0]);  // 1
        System.out.println(a[1][1]);  // 4
        System.out.println(a[0][2]);  // 5 (最後の列)

        System.out.println(a.length);     // 2 (行数)
        System.out.println(a[0].length);  // 3 (列数)
    }
}

二重ループと2次元配列 ​

java
int[][] a = {{1, 3, 5}, {2, 4, 6}};
for (int i = 0; i < a.length; i++) {
    System.out.print("リストの第 " + i + " 成分は [");
    for (int j = 0; j < a[i].length; j++) {
        if (j > 0) System.out.print(", ");
        System.out.print(a[i][j]);
    }
    System.out.println("]");
}

入力から2次元配列を作成 ​

方法1 (ループで代入):

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] a = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                a[i][j] = sc.nextInt();
            }
        }
    }
}

すべて 0 の N×M 配列 ​

java
int N = 2, M = 3;
int[][] a = new int[N][M];  // 自動的に 0 で初期化される

可変長の2次元リスト ​

java
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        int N = 4;
        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            a.add(new ArrayList<>());
        }

        a.get(0).add(10);
        a.get(0).add(20);
        a.get(2).add(30);
        a.get(3).add(40);
        a.get(3).add(50);
        a.get(3).add(60);

        // 結果: [[10, 20], [], [30], [40, 50, 60]]
        for (ArrayList<Integer> row : a) {
            System.out.println(row);
        }
    }
}

注意: 2次元配列の初期化 ​

Java の int[][] はデフォルトで 0 で初期化されます。Python の [[0]*M]*N のような罠はありません:

java
int N = 3, M = 2;
int[][] a = new int[N][M];  // 各行が独立した配列 (安全)
a[0][0] = 1;
System.out.println(a[1][0]);  // 0 (他の行は影響を受けない)

3次元配列 ​

java
int N = 2, M = 2, D = 2;
int[][][] lst3d = new int[N][M][D];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        for (int k = 0; k < D; k++) {
            lst3d[i][j][k] = i * 100 + j * 10 + k;
        }
    }
}

練習問題 ​

EX17. ゲーム大会

2.05. 再帰メソッド ​

キーポイント ​

  • メソッドが自分自身を呼び出すことを「再帰呼び出し」という
  • 再帰メソッドには「ベースケース」と「再帰呼び出し」の2つの部分がある
  • Java のデフォルトのスタックサイズは JVM に依存 (約 500〜1000 回程度が安全)
  • 深い再帰には StackOverflowError が発生する

再帰メソッドの基本 ​

java
public class Main {
    static long sumTriangle(int n) {
        if (n == 0) return 0;       // ベースケース
        long s = sumTriangle(n - 1); // 再帰呼び出し
        return s + n;               // 答えの計算
    }

    public static void main(String[] args) {
        System.out.println(sumTriangle(10));  // 55
    }
}

再帰メソッドの3つの部分 ​

  1. ベースケース: 再帰呼び出しなしに直接答えを求める最小ケース
  2. 再帰呼び出し: より小さなケースを呼び出す
  3. 答えの計算: 再帰結果を利用して最終答えを計算

階乗 ​

java
static long factorial(int n) {
    if (n == 0 || n == 1) return 1;  // ベースケース
    return n * factorial(n - 1);     // 再帰
}

フィボナッチ数 ​

java
static long fib(int n) {
    if (n == 0 || n == 1) return 1;  // ベースケース
    return fib(n - 1) + fib(n - 2); // 再帰
}

各桁の和 ​

java
static int digitSum(int n) {
    if (n <= 9) return n;            // ベースケース
    int ones = n % 10;
    int other = n / 10;
    return digitSum(other) + ones;   // 再帰
}

例題: 報告書の伝達時間 ​

java
import java.util.*;

public class Main {
    static ArrayList<ArrayList<Integer>> children;

    static int completeTime(int x) {
        if (children.get(x).isEmpty()) return 0;
        int maxTime = 0;
        for (int y : children.get(x)) {
            maxTime = Math.max(maxTime, completeTime(y) + 1);
        }
        return maxTime;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] p = new int[N];
        p[0] = -1;
        for (int i = 1; i < N; i++) p[i] = sc.nextInt();

        children = new ArrayList<>();
        for (int i = 0; i < N; i++) children.add(new ArrayList<>());
        for (int i = 1; i < N; i++) children.get(p[i]).add(i);

        System.out.println(completeTime(0));
    }
}

入力: 6 / 0 0 1 1 4出力: 3

再帰メソッドの注意点 ​

スタックオーバーフロー:

java
// 深い再帰は StackOverflowError を引き起こす
static void infiniteRecursion() {
    infiniteRecursion();  // 無限再帰 → StackOverflowError
}

競技プログラミングでは再帰が深くなる場合、反復 (ループ) に書き換えるか、スタック (ArrayDeque) を使って手動で管理することを検討します。

クイックソートの例 ​

java
import java.util.*;

public class Main {
    static ArrayList<Integer> quickSort(ArrayList<Integer> a) {
        if (a.isEmpty()) return new ArrayList<>();

        int p = a.remove(a.size() - 1);
        ArrayList<Integer> lo = new ArrayList<>();
        ArrayList<Integer> hi = new ArrayList<>();

        for (int x : a) {
            if (x < p) lo.add(x);
            else hi.add(x);
        }

        ArrayList<Integer> result = quickSort(lo);
        result.add(p);
        result.addAll(quickSort(hi));
        return result;
    }

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6));
        System.out.println(quickSort(list));  // [1, 1, 2, 3, 4, 5, 6, 9]
    }
}

練習問題 ​

EX18. 報告書の枚数

2.06. 計算量 ​

キーポイント ​

  • アルゴリズム: 処理の計算手順
  • 計算量: 入力に対して必要な計算時間・メモリがどう変化するかの指標
  • 時間計算量: 計算ステップ数の変化
  • 空間計算量: メモリ使用量の変化
  • オーダー記法 O(...): 計算量を大まかに表す記法
  • Java は Python より定数倍が速い (同じ O(N) でも 10〜100 倍速)

アルゴリズム ​

「ある処理を行うときに、どのような計算を行っていくかという計算手順」をアルゴリズムといいます。

例: 1から100までの総和

  • アルゴリズムA: 順に足す (99回の計算)
  • アルゴリズムB: 公式を使う (3回の計算) N * (N + 1) / 2

オーダー記法の求め方 ​

  1. 係数を省略する (定数については 1 とする)
  2. N を大きくしたとき一番影響が大きい項を取り出し、O(項) と書く

例:

  • N + 100 → O(N)
  • 10N + N³ → O(N³)
  • 3 + 5 → O(1)
  • 2ᴺ + N² → O(2ᴺ)

計算量の例 ​

O(1) の例:

java
Scanner sc = new Scanner(System.in);
long N = sc.nextLong();
long s = N * (N + 1) / 2;
System.out.println(s);

O(N) の例:

java
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] a = new int[N];
for (int i = 0; i < N; i++) a[i] = sc.nextInt();

int cnt = 0;
for (int x : a) {
    if (x % 2 == 0) cnt++;
}
System.out.println(cnt);

O(N²) の例:

java
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] table = new int[N][N];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        table[i][j] = (i + 1) * (j + 1);
    }
}
for (int[] row : table) {
    StringBuilder sb = new StringBuilder();
    for (int j = 0; j < row.length; j++) {
        if (j > 0) sb.append(" ");
        sb.append(row[j]);
    }
    System.out.println(sb);
}

O(log N) の例:

java
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int cnt = 0;
while (N % 2 == 0) {
    cnt++;
    N /= 2;
}
System.out.println(cnt);

計算量の大小関係 ​

O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2ᴺ)

入力 N と実行時間の目安 ​

NO(1)O(log N)O(N)O(N log N)O(N²)O(2ᴺ)
1一瞬一瞬一瞬一瞬一瞬一瞬
10一瞬一瞬一瞬一瞬一瞬一瞬
1,000一瞬一瞬一瞬一瞬0.01秒地球爆発
10⁶一瞬一瞬0.01秒0.2秒3時間地球爆発
10⁸一瞬一瞬1秒30秒3年地球爆発
10¹⁶一瞬一瞬3年170年地球爆発地球爆発

AtCoder の問題では実行時間制約が 2秒〜5秒であることが多いです。Java では 1秒あたり約 10⁸ 回の計算ができます (Python の約 10〜50 倍速)。

Java の高速化のヒント ​

出力を高速化する (StringBuilder を使う):

java
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        for (int i = 0; i < 100000; i++) {
            pw.println(i);
        }
        pw.flush();
    }
}

入力を高速化する (BufferedReader を使う):

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
    }
}

よく使う操作の計算量 ​

操作クラス計算量
a.length配列O(1)
list.size()ArrayListO(1)
list.get(i)ArrayListO(1)
list.add(x)ArrayListO(1)
list.contains(x)ArrayListO(N)
Arrays.sort(a)ArraysO(N log N)
Collections.sort(list)CollectionsO(N log N)
Arrays.binarySearch(a, v)ArraysO(log N)

練習問題 ​

EX19. 計算量の見積もり

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

Based on AtCoder Programming Guide for Python