競技プログラミング(Java)をまとめてみた

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

# 1. Scannerでの入力処理

**基本的な使用方法**
```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();
        System.out.println(a + b);
    }
}
```

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

それぞれの部分を説明します
```Java
import java.util.Scanner;
```

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

これがプログラム全体の「枠組み」です。Javaでは、すべてのプログラムはクラスという枠の中で書かれます。Mainという名前は、このプログラムの名前です。
```Java
public static void main(String[] args) { ... }
```

ここがプログラムのメイン部分です。プログラムが実行されると、この部分の中に書かれた命令が順番に実行されます。
```Java
Scanner sc = new Scanner(System.in);
```

ここでは、Scannerというツールを使って、キーボードから入力を受け付ける準備をしています。
```Java
int a = sc.nextInt();
```

ユーザーが入力した最初の数字を受け取り、その数字をaという名前の箱（変数）に入れます。
```Java
int b = sc.nextInt();
```

同じように、2つ目の数字をユーザーから受け取って、それをbという名前の箱に入れます。
```Java
System.out.println(a + b);
```

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


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

**リスト (ArrayList)**

用途: 順序付きの可変サイズのリスト。
特徴: O(1)で末尾に要素を追加。ランダムアクセスもO(1)でできる。
```java
ArrayList<Integer> list = new ArrayList<>();
list.add(1); // 末尾に追加
int x = list.get(0); // ランダムアクセス
```


**セット (HashSet)**

用途: 一意な要素の集合。
特徴: 挿入・削除・検索はO(1)。
```java
HashSet<Integer> set = new HashSet<>();
set.add(1); // 要素を追加
set.contains(1); // 要素が存在するかチェック
```

**マップ (HashMap)**

用途: キーと値のペアを保持するハッシュマップ。
特徴: 挿入・削除・検索はO(1)。
```java
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1); // キーに対応する値を設定
int value = map.get("apple"); // キーから値を取得
```

**キュー (PriorityQueue)**

用途: 優先度付きのキュー（最小値・最大値の管理）。
特徴: 挿入O(log n)、取り出しO(log n)。
```java
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3); // 要素を追加
pq.add(1); // 最小値を優先
int min = pq.poll(); // 最小値を取り出す
```

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

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

int[] arr = {5, 3, 8, 1};
Arrays.sort(arr); // 昇順ソート
```
逆順にソートする場合は、

Collections.reverseOrder()を使います。
```java
Arrays.sort(arr, Collections.reverseOrder());
```

**3.2. 二分探索**
Arrays.binarySearch()を使うことで、ソートされた配列に対する二分探索が可能です。
```java
int[] arr = {1, 3, 5, 7};
int index = Arrays.binarySearch(arr, 5); // 要素5の位置を返す
```

**3.3. 深さ優先探索 (DFS) と幅優先探索 (BFS)**
DFS (深さ優先探索): 再帰を使ったグラフの探索。
```java
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 (幅優先探索): キューを使ったグラフの探索。**
```java
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. 最短経路アルゴリズム (ダイクストラ法)**
重み付きグラフの最短経路を求めるダイクストラ法の基本実装。

```java
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です。
```java
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をフォローしていただけると嬉しいです。**