APG4b Java版

テーマ

練習問題と解答 ​

APG4b Java版の全章の練習問題と解答をまとめたページです。各問題はリンク先の章の内容を理解した上で取り組んでください。

第1章の練習問題 ​

EX1. コードテストと出力の練習 ​

関連セクション: 1.01. 出力とコメント

問題:

以下の3行を出力してください。

Hello, world!
Java
AtCoder

制約:

  • 出力は上記の通り正確に3行

解答:

java
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello, world!");
        System.out.println("Java");
        System.out.println("AtCoder");
    }
}

解説:

System.out.println() を3回呼び出すことで、3行の出力を行います。各行末に自動で改行が挿入されます。

EX2. プログラムの書き方の練習 ​

関連セクション: 1.02. プログラムの書き方とエラー

問題:

以下のプログラムにはコンパイルエラーがあります。エラーを修正して、正しく AtCoder と出力されるようにしてください。

java
public class Main {
    public static void main(String[] args) {
        System.out.println("AtCoder")
        System.out.println("Programming")
        System.out.println("Guide")
    }
}

解答:

java
public class Main {
    public static void main(String[] args) {
        System.out.println("AtCoder");
        System.out.println("Programming");
        System.out.println("Guide");
    }
}

出力:

AtCoder
Programming
Guide

解説:

各 System.out.println() の末尾に ; (セミコロン) が抜けていることがエラーの原因です。Java では文の末尾に必ずセミコロンが必要です。

EX3. 計算問題 ​

関連セクション: 1.03. 四則演算と優先順位

問題:

整数 A, B が与えられます。以下の5つの計算結果をそれぞれ1行ずつ出力してください。

  1. A + B
  2. A - B
  3. A * B
  4. A / B (整数除算: 小数点以下切り捨て)
  5. A % B (A を B で割った余り)

制約:

  • 1 ≤ A ≤ 10^9
  • 1 ≤ B ≤ 10^9

入力形式:

A B

入力例:

7 2

出力例:

9
5
14
3
1

解答:

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();
        System.out.println(A + B);
        System.out.println(A - B);
        System.out.println(A * B);
        System.out.println(A / B);
        System.out.println(A % B);
    }
}

解説:

A, B が最大 10^9 なので、A * B が最大 10^18 になりえます。int の上限 (約 21億) を超えるため long を使います。

EX4. ◯年は何秒？ ​

関連セクション: 1.04. 変数と型

問題:

整数 N が与えられます。N 年は何秒かを出力してください。 ただし、1年は 365 日とします。

制約:

  • 1 ≤ N ≤ 10^6

入力形式:

N

入力例 1:

1

出力例 1:

31536000

入力例 2:

100

出力例 2:

3153600000

解答:

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long seconds = N * 365L * 24L * 60L * 60L;
        System.out.println(seconds);
    }
}

解説:

1年 = 365日 = 365 × 24時間 = 365 × 24 × 60分 = 365 × 24 × 60 × 60秒 = 31,536,000秒です。

N が最大 10^6 のとき、答えは約 3.15 × 10^13 になるため long が必要です。計算途中でもオーバーフローしないよう、リテラルに L を付けて long で計算します。

EX5. A足すB問題 ​

関連セクション: 1.05. 入力

問題:

整数 A, B が与えられます。A + B を出力してください。

制約:

  • 1 ≤ A, B ≤ 10^9

入力形式:

A B

入力例:

15 37

出力例:

52

解答:

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();
        System.out.println(A + B);
    }
}

解説:

競技プログラミングの最も基本的な問題です。Scanner で入力を受け取り、+ で計算して出力します。A, B が最大 10^9 なので long を使います (合計は最大 2×10^9 で int の上限を超える可能性があります)。

EX6. 電卓をつくろう ​

関連セクション: 1.06. if文・比較演算子・論理演算子

問題:

整数 A, B と演算子 op (+, -, *, /) が与えられます。A op B の計算結果を出力してください。ただし / は整数除算とし、B が 0 の場合の入力は与えられません。

制約:

  • -10^9 ≤ A, B ≤ 10^9
  • op は +, -, *, / のいずれか

入力形式:

A op B

入力例 1:

10 + 5

出力例 1:

15

入力例 2:

10 / 3

出力例 2:

3

解答:

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        String op = sc.next();
        long B = sc.nextLong();

        if (op.equals("+")) {
            System.out.println(A + B);
        } else if (op.equals("-")) {
            System.out.println(A - B);
        } else if (op.equals("*")) {
            System.out.println(A * B);
        } else {
            System.out.println(A / B);
        }
    }
}

解説:

op は文字列なので、比較には .equals() を使います。== ではなく .equals() を使う点が Java の重要なポイントです。

EX7. boolean値パズル ​

関連セクション: 1.07. 論理式の値と boolean 型

問題:

整数 X, Y が与えられます。以下の3つの条件式の評価結果 (true または false) を1行ずつ出力してください。

  1. X と Y が等しい
  2. X が正 (0より大きい) かつ Y が正
  3. X または Y の少なくともどちらかが 0

制約:

  • -100 ≤ X, Y ≤ 100

入力形式:

X Y

入力例:

5 0

出力例:

false
false
true

解答:

java
import java.util.Scanner;

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

        System.out.println(X == Y);
        System.out.println(X > 0 && Y > 0);
        System.out.println(X == 0 || Y == 0);
    }
}

解説:

条件式をそのまま System.out.println() に渡すと、true または false と出力されます。boolean 値を変数に格納してから出力することもできます。

EX8. たくさんのA足すB問題 ​

関連セクション: 1.08. while文

問題:

T 組の (A, B) が与えられます。各組について A + B を出力してください。

制約:

  • 1 ≤ T ≤ 100
  • 1 ≤ A, B ≤ 10^9

入力形式:

T
A_1 B_1
A_2 B_2
...
A_T B_T

入力例:

3
1 2
10 20
100 200

出力例:

3
30
300

解答:

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int i = 0;
        while (i < T) {
            long A = sc.nextLong();
            long B = sc.nextLong();
            System.out.println(A + B);
            i++;
        }
    }
}

解説:

while (i < T) で T 回繰り返します。各繰り返しで A, B を読み込み A + B を出力します。ループ変数 i を i++ でインクリメントしないと無限ループになるため忘れずに記述します。for 文を使うとインクリメントを書き忘れにくくなります。

EX9. 電卓をつくろう2 ​

関連セクション: 1.09. for文・break・continue

問題:

整数 N が与えられます。1 から N までのすべての整数の合計を出力してください。

制約:

  • 1 ≤ N ≤ 10^6

入力形式:

N

入力例:

10

出力例:

55

解答:

java
import java.util.Scanner;

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

        // 方法1: for ループ
        long sum = 0;
        for (long i = 1; i <= N; i++) {
            sum += i;
        }
        System.out.println(sum);

        // 方法2: 公式 (O(1))
        // System.out.println(N * (N + 1) / 2);
    }
}

解説:

for (long i = 1; i <= N; i++) で 1 から N まで順番に sum に加算します。N が最大 10^6 で答えが最大 5 × 10^11 になるため long を使います。公式 N * (N + 1) / 2 を使うと O(1) で計算できます。

EX10. 平均との差 ​

関連セクション: 1.10. 配列 (リスト)

問題:

N 個の整数 a_1, a_2, ..., a_N が与えられます。各要素と全要素の平均との差の絶対値を、小数点以下を切り捨てずに出力してください。

制約:

  • 1 ≤ N ≤ 1000
  • 0 ≤ a_i ≤ 10^9

入力形式:

N
a_1 a_2 ... a_N

入力例:

5
10 20 30 40 50

出力例:

20.0
10.0
0.0
10.0
20.0

解答:

java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        double[] a = new double[N];
        double sum = 0;

        for (int i = 0; i < N; i++) {
            a[i] = sc.nextDouble();
            sum += a[i];
        }

        double avg = sum / N;

        for (int i = 0; i < N; i++) {
            System.out.println(Math.abs(a[i] - avg));
        }
    }
}

解説:

まず全要素を読み込みながら合計を計算し、平均 avg = sum / N を求めます。次に各要素について Math.abs(a[i] - avg) で差の絶対値を計算します。

EX11. 文字列の処理 ​

関連セクション: 1.11. 文字列

問題:

文字列 S が与えられます。以下の4つを出力してください。

  1. S の長さ
  2. S の先頭の文字
  3. S の末尾の文字
  4. S を逆順にした文字列

制約:

  • 1 ≤ |S| ≤ 100
  • S は英小文字のみからなる

入力形式:

S

入力例:

atcoder

出力例:

7
a
r
redocta

解答:

java
import java.util.Scanner;

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

        // 1. 長さ
        System.out.println(S.length());

        // 2. 先頭の文字
        System.out.println(S.charAt(0));

        // 3. 末尾の文字
        System.out.println(S.charAt(S.length() - 1));

        // 4. 逆順
        StringBuilder sb = new StringBuilder(S);
        System.out.println(sb.reverse().toString());
    }
}

解説:

S.length() で長さを、S.charAt(i) で i 番目の文字を取得します。逆順は StringBuilder の reverse() メソッドで簡単に求められます。

EX12. Find the Fastest Runner ​

関連セクション: 1.12. 組み込み関数

問題:

N 人のランナーのタイム (秒) が与えられます。最速 (タイムが最小) のランナーの番号 (1-indexed) を出力してください。タイムが同じランナーが複数いる場合は、番号が最も小さいものを出力してください。

制約:

  • 1 ≤ N ≤ 1000
  • 1 ≤ タイム ≤ 10^6

入力形式:

N
t_1 t_2 ... t_N

入力例:

5
300 250 280 250 310

出力例:

2

解答:

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[] t = new int[N];

        for (int i = 0; i < N; i++) {
            t[i] = sc.nextInt();
        }

        int minIdx = 0;
        for (int i = 1; i < N; i++) {
            if (t[i] < t[minIdx]) {
                minIdx = i;
            }
        }

        System.out.println(minIdx + 1);  // 1-indexed
    }
}

解説:

最初のランナーを仮の最速とし (minIdx = 0)、2番目以降のランナーのタイムと比較しながら最速のインデックスを更新します。< (strictly less than) を使うため、同タイムの場合は先にあるインデックスが保持されます。出力は 1-indexed なので minIdx + 1 とします。

EX13. 三人兄弟へのプレゼント ​

関連セクション: 1.13. 関数 (メソッド)

問題:

3人の兄弟に、それぞれ好きな数のキャンディーをプレゼントします。兄弟 i のキャンディーの個数 a_i が与えられたとき、合計個数、最大個数、最小個数をそれぞれ出力してください。

これらを求めるメソッドを定義して使用してください。

制約:

  • 0 ≤ a_1, a_2, a_3 ≤ 1000

入力形式:

a_1 a_2 a_3

入力例:

10 25 7

出力例:

42
25
7

解答:

java
import java.util.Scanner;

public class Main {
    static int sum(int a, int b, int c) {
        return a + b + c;
    }

    static int max(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    static int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        System.out.println(sum(a, b, c));
        System.out.println(max(a, b, c));
        System.out.println(min(a, b, c));
    }
}

解説:

3つの引数を受け取るメソッドを sum, max, min として定義します。Math.max(a, Math.max(b, c)) で3つの値の最大値を求めます。

第2章の練習問題 ​

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

関連セクション: 2.01. いろいろな for 文

問題:

N 個の整数からなる数列 a_1, a_2, ..., a_N が与えられます。隣り合う要素で等しいペア (a_i = a_{i+1} となる i) が存在するかどうかを判定してください。存在すれば Yes、そうでなければ No と出力してください。

制約:

  • 2 ≤ N ≤ 1000
  • 1 ≤ a_i ≤ 1000

入力形式:

N
a_1 a_2 ... a_N

入力例 1:

5
1 2 2 3 4

出力例 1:

Yes

入力例 2:

4
1 2 3 4

出力例 2:

No

解答:

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[] a = new int[N];

        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }

        boolean found = false;
        for (int i = 0; i < N - 1; i++) {
            if (a[i] == a[i + 1]) {
                found = true;
                break;
            }
        }

        System.out.println(found ? "Yes" : "No");
    }
}

解説:

for (int i = 0; i < N - 1; i++) で隣り合う要素のペアをすべてチェックします。一つでも見つかれば found = true にして break します。最後に三項演算子で出力します。

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

関連セクション: 2.02. 多重ループ

問題:

リンゴの値段 A 円、バナナの値段 B 円、所持金 M 円が与えられます。リンゴとバナナをそれぞれ 0 個以上買えるとき、合計金額がちょうど M 円になる買い方の組み合わせの数を出力してください。

制約:

  • 1 ≤ A, B ≤ 1000
  • 1 ≤ M ≤ 10^6

入力形式:

A B M

入力例:

100 150 500

出力例:

2

(リンゴ5個・バナナ0個 = 500円、リンゴ2個・バナナ2個 = 500円)

解答:

java
import java.util.Scanner;

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

        int count = 0;
        for (int i = 0; i * A <= M; i++) {        // リンゴの個数
            for (int j = 0; j * B <= M; j++) {    // バナナの個数
                if (i * A + j * B == M) {
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}

解説:

リンゴの個数 i とバナナの個数 j を二重ループで全探索します。i * A <= M の条件でリンゴだけで M 円を超える場合はループを終了します。

EX16. 英単語テストの練習 ​

関連セクション: 2.03. ループによるリスト生成

問題:

N 問の英単語テストがあります。正解の単語 w_i と生徒の解答 a_i が与えられます。正解した問題数を出力してください。

制約:

  • 1 ≤ N ≤ 100
  • 各単語は英小文字のみからなり、長さは 1 以上 20 以下

入力形式:

N
w_1 a_1
w_2 a_2
...
w_N a_N

入力例:

4
apple apple
banana bananaa
cherry cherry
dog cat

出力例:

2

解答:

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 correct = 0;
        for (int i = 0; i < N; i++) {
            String w = sc.next();
            String a = sc.next();
            if (w.equals(a)) {
                correct++;
            }
        }

        System.out.println(correct);
    }
}

解説:

各問題について正解 w と解答 a を読み込み、.equals() で比較します。文字列の比較には必ず .equals() を使います。Java では == を使うと文字列の内容ではなくメモリ上の参照先 (オブジェクトが同一かどうか) を比較するため、内容が同じでも false になる場合があります。

EX17. ゲーム大会 ​

関連セクション: 2.04. 多次元配列

問題:

N 人でリーグ戦 (全員が全員と1回ずつ対戦) を行います。試合結果が与えられます。最も多く勝ったプレイヤーの番号 (1-indexed) と勝利数を出力してください。同点の場合は番号が小さいプレイヤーを出力してください。

試合結果は N×N の行列 r で表され、r[i][j] = 1 はプレイヤー i がプレイヤー j に勝ったことを意味します (r[i][i] = 0, r[i][j] + r[j][i] = 1)。

制約:

  • 2 ≤ N ≤ 100

入力形式:

N
r[0][0] r[0][1] ... r[0][N-1]
r[1][0] r[1][1] ... r[1][N-1]
...
r[N-1][0] ... r[N-1][N-1]

入力例:

3
0 1 0
0 0 1
1 0 0

出力例:

1 1

(全員1勝のため番号が最小の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[][] r = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                r[i][j] = sc.nextInt();
            }
        }

        int maxWins = -1;
        int winner = 0;

        for (int i = 0; i < N; i++) {
            int wins = 0;
            for (int j = 0; j < N; j++) {
                wins += r[i][j];  // i が j に勝った数
            }
            if (wins > maxWins) {
                maxWins = wins;
                winner = i;
            }
        }

        System.out.println((winner + 1) + " " + maxWins);
    }
}

解説:

各プレイヤー i の勝利数は r[i][j] の行和で求められます。最大勝利数とそのプレイヤーのインデックスを更新しながらループします。> を使うことで同点の場合は番号が小さい方が保持されます。

EX18. 報告書の枚数 ​

関連セクション: 2.05. 再帰メソッド

問題:

N 人の社員が木構造の組織に属しています。各社員は1枚の報告書を書き、自分の上司に渡します。上司はすべての部下からの報告書と自分の報告書をまとめて自分の上司に渡します。

社員の親 (上司) の番号が与えられます (社員0はルートで親を持たない)。社員0が最終的に受け取る報告書の枚数を出力してください。

制約:

  • 1 ≤ N ≤ 1000
  • 木構造が保証される

入力形式:

N
p_1 p_2 ... p_{N-1}

(p_i は社員 i の親の番号)

入力例:

5
0 0 1 1

出力例:

5

(全員の報告書が最終的に0に集まる)

解答:

java
import java.util.*;

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

    // x の部下の総数 + 1 (x 自身を含む) を返す
    static int countReports(int x) {
        int total = 1;  // 自分の報告書
        for (int child : children.get(x)) {
            total += countReports(child);
        }
        return total;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        children = new ArrayList<>();
        for (int i = 0; i < N; i++) children.add(new ArrayList<>());

        for (int i = 1; i < N; i++) {
            int p = sc.nextInt();
            children.get(p).add(i);
        }

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

解説:

各ノード x が最終的に受け取る報告書の枚数は「自分の1枚 + すべての子ノードが受け取る枚数の合計」です。再帰的に計算します。ルートが全員分の報告書を受け取るので、答えは N 枚です。

EX19. 計算量の見積もり ​

関連セクション: 2.06. 計算量

問題:

N 個の整数からなる数列 a が与えられます。数列中に同じ値の要素が2つ以上存在するかどうかを判定してください。存在すれば Yes、そうでなければ No と出力してください。

制約:

  • 1 ≤ N ≤ 10^5
  • 1 ≤ a_i ≤ 10^9

なお、O(N²) のアルゴリズムでは TLE になる制約です。O(N log N) 以下の解法を考えてください。

入力形式:

N
a_1 a_2 ... a_N

入力例 1:

5
3 1 4 1 5

出力例 1:

Yes

入力例 2:

4
1 2 3 4

出力例 2:

No

解答:

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        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();

        // O(N log N): ソートして隣接要素を比較
        Arrays.sort(a);
        boolean found = false;
        for (int i = 0; i < N - 1; i++) {
            if (a[i] == a[i + 1]) {
                found = true;
                break;
            }
        }
        System.out.println(found ? "Yes" : "No");

        // O(N): HashSet を使う方法
        // HashSet<Integer> set = new HashSet<>();
        // for (int x : a) {
        //     if (!set.add(x)) { System.out.println("Yes"); return; }
        // }
        // System.out.println("No");
    }
}

解説:

N ≤ 10^5 のため O(N²) のナイーブな全探索は TLE します。ソート (O(N log N)) してから隣接要素を比較するか、HashSet (O(N)) を使います。O(N²) vs O(N log N) の違いを体感できる問題です。

第3章の練習問題 ​

EX20. 最頻値 ​

関連セクション: 3.02. コレクション

問題:

N 個の整数が与えられます。最も多く出現する値 (最頻値) とその出現回数を出力してください。最頻値が複数存在する場合は、最小の値を出力してください。

制約:

  • 1 ≤ N ≤ 10^5
  • 1 ≤ a_i ≤ 10^9

入力形式:

N
a_1 a_2 ... a_N

入力例:

8
3 1 4 1 5 9 2 6

出力例:

1 2

解答:

java
import java.util.*;

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

        TreeMap<Integer, Integer> counter = new TreeMap<>();
        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            counter.merge(a, 1, Integer::sum);
        }

        int maxCount = 0;
        int mode = 0;
        for (var entry : counter.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                mode = entry.getKey();
            }
        }

        System.out.println(mode + " " + maxCount);
    }
}

解説:

TreeMap を使うことでキーが自動的に昇順ソートされます。entrySet() でイテレーションするとキーの昇順で処理されるため、同出現回数の場合は自動的に小さいキーが最初に見つかります。> (strictly greater) を使うことで同出現回数のときは最小値が保持されます。

EX21. Bitwise Exclusive Or ​

関連セクション: 3.04. ビット演算

問題:

N 個の整数が与えられます。これらすべての XOR (排他的論理和) を求めて出力してください。

制約:

  • 1 ≤ N ≤ 10^5
  • 0 ≤ a_i ≤ 10^9

入力形式:

N
a_1 a_2 ... a_N

入力例:

4
3 1 4 1

出力例:

7

(3 XOR 1 = 2, 2 XOR 4 = 6, 6 XOR 1 = 7)

解答:

java
import java.util.Scanner;

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

        long result = 0;
        for (int i = 0; i < N; i++) {
            long a = sc.nextLong();
            result ^= a;  // XOR を累積
        }

        System.out.println(result);
    }
}

解説:

XOR は累積演算なので、result ^= a と順に XOR を取ることで全要素の XOR が求まります。XOR の性質として a ^ a = 0、a ^ 0 = a があるため、同じ値が偶数個あればキャンセルされます。

EX22. 2つ目の値でソート ​

関連セクション: 3.06. いろいろなソート

問題:

N 個のペア (x_i, y_i) が与えられます。y_i の昇順でソートし、y_i が同じ場合は x_i の昇順でソートして出力してください。

制約:

  • 1 ≤ N ≤ 10^5
  • 1 ≤ x_i, y_i ≤ 10^9

入力形式:

N
x_1 y_1
x_2 y_2
...
x_N y_N

入力例:

4
3 1
1 2
2 1
4 3

出力例:

2 1
3 1
1 2
4 3

解答:

java
import java.util.*;

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

        for (int i = 0; i < N; i++) {
            pairs[i][0] = sc.nextInt();
            pairs[i][1] = sc.nextInt();
        }

        // y の昇順、y が同じなら x の昇順
        Arrays.sort(pairs, (a, b) -> {
            if (a[1] != b[1]) return a[1] - b[1];  // y で比較
            return a[0] - b[0];                      // x で比較
        });

        for (int[] p : pairs) {
            System.out.println(p[0] + " " + p[1]);
        }
    }
}

解説:

Arrays.sort() にラムダ式で比較関数を渡します。まず y (2番目の要素) で比較し、等しければ x (1番目の要素) で比較します。

第4章の練習問題 ​

EX23. 再帰関数1 ​

関連セクション: 4.05. メモ化

問題:

以下の関数 f(n) を計算して出力してください。

  • f(0) = 0
  • f(1) = 1
  • f(2) = 1
  • f(n) = f(n-1) + f(n-2) + f(n-3) (n ≥ 3 のとき)

制約:

  • 0 ≤ n ≤ 50

入力形式:

n

入力例 1:

0

出力例 1:

0

入力例 2:

10

出力例 2:

149

解答:

java
import java.util.*;

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

    static long f(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 1;
        if (memo.containsKey(n)) return memo.get(n);

        long result = f(n - 1) + f(n - 2) + f(n - 3);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(f(n));
    }
}

解説:

トリボナッチ数列 (Tribonacci) と呼ばれる漸化式です。f(0), f(1), f(2) の3つをベースケースとして返し、それ以降は再帰的に計算します。

ベースケースが3つ必要な理由は、f(n-3) が n=2 のとき f(-1) となり未定義になるためです。if (n == 2) return 1; を明示することでこれを防ぎます。

メモ化なしだと同じ値が指数的に何度も計算されます。HashMap でメモ化することで各 n について1回だけ計算でき、O(n) の時間計算量になります。

数列の最初の値: f(0)=0, f(1)=1, f(2)=1, f(3)=2, f(4)=4, f(5)=7, f(6)=13, f(7)=24, f(8)=44, f(9)=81, f(10)=149

EX24. 再帰関数2 ​

関連セクション: 4.05. メモ化

問題:

整数 N が与えられます。N 段の階段を、1段または2段ずつ上る方法が何通りあるかを出力してください。ただし、答えが非常に大きくなる可能性があるため、10^9 + 7 で割った余りを出力してください。

制約:

  • 1 ≤ N ≤ 10^6

入力形式:

N

入力例 1:

3

出力例 1:

3

(1+1+1, 1+2, 2+1 の3通り)

入力例 2:

10

出力例 2:

89

解答:

java
import java.util.Scanner;

public class Main {
    static final long MOD = 1_000_000_007L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        // dp[i] = i 段目に上る方法の数
        long[] dp = new long[N + 1];
        dp[0] = 1;  // 0段目 (スタート) は1通り
        if (N >= 1) dp[1] = 1;

        for (int i = 2; i <= N; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        System.out.println(dp[N]);
    }
}

解説:

「N 段目に到達する方法数」は「N-1 段目からの1段上がり + N-2 段目からの2段上がり」なので、dp[i] = dp[i-1] + dp[i-2] というフィボナッチ数列と同じ漸化式になります。

N が最大 10^6 のとき、メモ化再帰では再帰の深さが 10^6 に達しスタックオーバーフローが発生します。配列を使ったボトムアップ DP なら再帰を使わないためこの問題が起きません。10^9+7 で割ることで各ステップで数値を小さく保ち、オーバーフローを防ぎます。

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

Based on AtCoder Programming Guide for Python