競技プログラミングをjavaでよく使うものなどをアウトプットもかねて記事にしてみました。
- 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は、画面にメッセージや結果を表示するための命令です。
- 効率的なデータ構造
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(); // 最小値を取り出す
- アルゴリズムとその実装
競技プログラミングでは、アルゴリズムの効率性が求められます。以下は、よく使われるアルゴリズムとその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.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.1. Apache Commons Math
競技プログラミングでよく使う数学的な処理（最大公約数、最小公倍数、素因数分解など）を便利にするライブラリです。
今回は競技プログラミングのことをまとめてみました。