競技プログラミングをjavaでよく使うものなどをアウトプットもかねて記事にしてみました。

1. Scannerでの入力処理

基本的な使用方法

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();
        System.out.println(a + b);
    }
}

このプログラムは、2つの数字を足し算する簡単なJavaのプログラムです。基本的に、ユーザーから2つの数字を入力してもらい、その合計を表示する仕組みになっています。

それぞれの部分を説明します

import java.util.Scanner;

ここでは、Scannerというクラスを使うために、そのクラスをインポートしています。Scannerは、キーボードからの入力（ユーザーが入力する値）を読み取るためのツールです。

public class Main { ... }

これがプログラム全体の「枠組み」です。Javaでは、すべてのプログラムはクラスという枠の中で書かれます。Mainという名前は、このプログラムの名前です。

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

ここがプログラムのメイン部分です。プログラムが実行されると、この部分の中に書かれた命令が順番に実行されます。

Scanner sc = new Scanner(System.in);

ここでは、Scannerというツールを使って、キーボードから入力を受け付ける準備をしています。

int a = sc.nextInt();

ユーザーが入力した最初の数字を受け取り、その数字をaという名前の箱（変数）に入れます。

int b = sc.nextInt();

同じように、2つ目の数字をユーザーから受け取って、それをbという名前の箱に入れます。

System.out.println(a + b);

aとbに入れた数字を足し算して、その結果を画面に表示します。System.out.printlnは、画面にメッセージや結果を表示するための命令です。

2. 効率的なデータ構造

Javaの標準ライブラリには、効率的なデータ構造が多数用意されています。これらを使いこなすことで、データの管理や処理を素早く行えます。

リスト (ArrayList)

用途: 順序付きの可変サイズのリスト。
特徴: O(1)で末尾に要素を追加。ランダムアクセスもO(1)でできる。

ArrayList<Integer> list = new ArrayList<>();
list.add(1); // 末尾に追加
int x = list.get(0); // ランダムアクセス

セット (HashSet)

用途: 一意な要素の集合。
特徴: 挿入・削除・検索はO(1)。

HashSet<Integer> set = new HashSet<>();
set.add(1); // 要素を追加
set.contains(1); // 要素が存在するかチェック

マップ (HashMap)

用途: キーと値のペアを保持するハッシュマップ。
特徴: 挿入・削除・検索はO(1)。

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1); // キーに対応する値を設定
int value = map.get("apple"); // キーから値を取得

キュー (PriorityQueue)

用途: 優先度付きのキュー（最小値・最大値の管理）。
特徴: 挿入O(log n)、取り出しO(log n)。

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3); // 要素を追加
pq.add(1); // 最小値を優先
int min = pq.poll(); // 最小値を取り出す

3. アルゴリズムとその実装

競技プログラミングでは、アルゴリズムの効率性が求められます。以下は、よく使われるアルゴリズムとそのJavaでの実装例です。

3.1. ソートアルゴリズム
Javaには標準ライブラリにソート機能が組み込まれています。

import java.util.Arrays;

int[] arr = {5, 3, 8, 1};
Arrays.sort(arr); // 昇順ソート

逆順にソートする場合は、

Collections.reverseOrder()を使います。

Arrays.sort(arr, Collections.reverseOrder());

3.2. 二分探索
Arrays.binarySearch()を使うことで、ソートされた配列に対する二分探索が可能です。

int[] arr = {1, 3, 5, 7};
int index = Arrays.binarySearch(arr, 5); // 要素5の位置を返す

3.3. 深さ優先探索 (DFS) と幅優先探索 (BFS)
DFS (深さ優先探索): 再帰を使ったグラフの探索。

void dfs(int node, boolean[] visited, List<List<Integer>> adj) {
    visited[node] = true;
    for (int neighbor : adj.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adj);
        }
    }
}

BFS (幅優先探索): キューを使ったグラフの探索。

void bfs(int start, boolean[] visited, List<List<Integer>> adj) {
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.add(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

3.4. 最短経路アルゴリズム (ダイクストラ法)
重み付きグラフの最短経路を求めるダイクストラ法の基本実装。

class Node implements Comparable<Node> {
    int id, cost;
    public Node(int id, int cost) {
        this.id = id;
        this.cost = cost;
    }
    public int compareTo(Node other) {
        return this.cost - other.cost;
    }
}

void dijkstra(int start, int[] dist, List<List<Node>> adj) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(start, 0));
    dist[start] = 0;
    
    while (!pq.isEmpty()) {
        Node current = pq.poll();
        int currentId = current.id;
        int currentCost = current.cost;
        
        if (currentCost > dist[currentId]) continue;
        
        for (Node neighbor : adj.get(currentId)) {
            int newDist = currentCost + neighbor.cost;
            if (newDist < dist[neighbor.id]) {
                dist[neighbor.id] = newDist;
                pq.add(new Node(neighbor.id, newDist));
            }
        }
    }
}

4. その他のテクニック

4.1. MODを使った大数の取り扱い
競技プログラミングでは、しばしば大きな数を扱うためにモジュラ演算を使います。よく使われるMODは10^9 + 7です。

int MOD = 1000000007;

int modAdd(int a, int b) {
    return (a + b) % MOD;
}

int modMul(int a, int b) {
    return (int)((1L * a * b) % MOD);
}

4.2. 再帰の最適化
Javaの再帰はデフォルトではスタックサイズが制限されているため、深い再帰が必要な場合は、再帰の深さに注意が必要です。StackOverflowErrorを避けるために再帰の代わりにループで実装することもあります。

5. 競技プログラミングに役立つライブラリ
5.1. Apache Commons Math
競技プログラミングでよく使う数学的な処理（最大公約数、最小公倍数、素因数分解など）を便利にするライブラリです。

今回は競技プログラミングのことをまとめてみました。
毎日更新していますので、@y-t0910をフォローしていただけると嬉しいです。