【Java】競技プログラミング最序盤で使用しているリファレンスまとめ

【はじめに】

本項での「競技プログラミング最序盤」は
・AtCoder Beginner Contest での A, B問題
・Paiza スキルチェック での B, C, D, E問題 を指します。

特にAtCoderの場合、初学者の方はまず 過去問精選10問 に触れて、その後 過去問サイト AtCoder Problems で問題を埋めていくのがオススメです。

本稿はJavaの膨大なリファレンスの中から 特に初学者の自分にとって役に立ったものを簡単なコメント付きで紹介するスタンスなので、正確性に欠ける表現が数多く有ります。
より正確に知りたい方はこちらの Oracleの公式リファレンスマニュアル を参照して下さい。

【標準入力 編】

一般的にJavaでの標準入力には Scannerクラス を使用する。
最初に import java.util.Scanner; を書き、mainメゾット内でインスタンス化してから使用すると手間が省ける。

import java.util.Scanner;

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

以下、インスタンス名はscで統一する。

・入力を文字列で受け取る

sc.nextLine();
空白文字も含めて改行までの文字列を 1行丸ごと 取得する。

sc.next()
改行及び空白文字までの文字列を取得し、空白を含まない。
入力文字列の空白と改行を無視して考えることができる。

String str1 = sc.nextLine();
String str2 = sc.next();

・入力を数値で受け取る

sc.nextInt();
sc.nextLong();
sc.nextDouble();

それぞれ int型 / long型 / double型の数値を取得することができる。
数値の性質上当たり前だが、.next()と同じように 入力を空白や改行で区切って受け取る。

int num1 = sc.nextInt();
long num2 = sc.nextLong();
double num3 = sc.nextDouble();

・入力を文字で受け取る

sc.next().charAt(0);

char型には入力を受け取る専用のメソッドが存在しないため、後述のcharAt()と組み合わせて使うと良い。

char ch = sc.next().charAt(0);

一般に入出力は 低速 であるため、極めて大量に繰り返すと TLE (Time Limit Exceeded / 指定された実行時間をオーバー) の一因になる。 (最序盤ではあまりTLEは出ないが...)
詳しくは後述の ・入出力の高速化 の項で紹介している。

【文字列編】

以下、文字列 str1 を Hello,World とする。

String str1 = "Hello,World";

・文字列に特定の文字列が含まれているか判定

str1.contains("検索する文字");

真偽をboolean型で返す。

System.out.println(str1.contains("W")); 
// Output: true

・文字列が一致しているか比較

str1.equals(比較する文字列);

真偽をboolean型で返す。
文字列はint型のように == を使うと正常に比較できない ので、.equals() を使う。
==を使えない理由 (javaでの同値性と同一性の違い)はこの記事を参考に。

String str2 = "I love Java";

if(str1.equals(str2)) {
    System.out.println("同じだよ");
} else {
    System.out.println("違うよ");
}
// Output: 違うよ

・文字列からn～m-1番目までの文字列を切り取る

str1.substring(n, m);

String型で返す。
こういう位置を数える系は、最初の文字を 0番目 とすることに注意。

System.out.println(str1.substring(0,4)); 
// Output: Hell

・文字列からn番目の1文字を切り取る

str1.charAt(n);

1文字だけ切り取るならこちらでもよい。char型で返す。

System.out.println(str1.charAt(4)); 
// Output: o (←Hell"o"のo)

・文字列をchar型配列に変換

char[] 配列名 = str1.toCharArray();

文字列を文字単位で区切り、char型配列に格納する事が出来る。

char[] array1 = str1.toCharArray();

for (int i = 0; i < array1.length; i++) {
	System.out.print(array1[i] + "_"); 
}
// Output: H_e_l_l_o_,_W_o_r_l_d_

・文字列中の特定の文字列の位置を検索

str1.indexOf("検索する文字");

位置をint型で返す。見つからなければ "-1"。
第二引数で検索開始位置を指定することもできる。

System.out.println(str1.indexOf("o")); 
// Output: 4 (Hello→"01234"となりoは4番目なので4が返される)

System.out.println(str1.indexOf("o", 5)); 
// Output: 7 (Hello,Wo→"01234567"となり7が返される)

・文字列内の特定の文字(列)を全て置換

str1.replace("置換される文字列", "置換する文字列");

char型でもString型でも引数にできる。
第一引数を "" にすると、文字列に1文字ずつ任意の文字(列)を挟める。先頭と最後にも挟まれる事に注意。

System.out.println(str1.replace("l", "ZZ"));
// Output: HeZZZZo,WorZZd

・文字列内のアルファベットを全て大文字/小文字に変換

str1.toUpperCase(); →大文字
str1.toLowerCase(); →小文字

全角アルファベットにも対応。

System.out.println(str1.toUpperCase());
// Output: HELLO,WORLD

System.out.println(str1.toLowerCase());
// Output: hello,world

・文字列を特定の文字で分割して配列に格納

String[] 配列名 = str1.split("特定の文字");

区切るための文字は配列に含まれないことに注意。
""で分割すると一文字ずつに分けられる。

String[] array1 = str1.split(","); 

for(int i = 0; i < array1.length; i++) {
    System.out.print(array1[i] + "#"); 
}
// Output: Hello#World#

・配列の要素が順番まで全て一致しているか比較

Arrays.equals(配列1, 配列2);

import java.util.Arrays; を最初に書いて使う。
真偽をboolean型で返す。

int[] array1 = {1, 2, 3};
int[] array2 = {1, 2, 3};

if(Arrays.equals(array1, array2)) {
    System.out.println("同じだよ");
} else {
    System.out.println("違うよ");
}
// Output: 同じだよ

・多次元配列の要素が順番まで全て一致しているか比較

Arrays.deepEquals(配列1, 配列2);

import java.util.Arrays; を最初に書いて使う。
真偽をboolean型で返す。
多次元配列については後述の ・二次元配列 の項を参考に。

int[][] array1 = {{1,2}, {3,4}};
int[][] array2 = {{1,2}, {3,4}};

if(Arrays.deepEquals(array1, array2)) {
    System.out.println("同じだよ");
} else {
    System.out.println("違うよ");
}
// Output: 同じだよ

・配列を昇順ソート

Arrays.sort(配列);

import java.util.Arrays;を最初に書いて使う。
配列ならString型だけでなくint型、char型など幅広く使える。

例えば、複数の単語をString型配列にしてArrays.sort()すれば辞書順にできる。
また、文字列を toCharArray でchar型配列にして Arrays.sort() すれば、1つの文字列内の文字を辞書順に並び替えられる。

辞書順の並びは文字コードでの順番に準拠している。
0~9 → 記号 → A~Z → a~z → ひらがな → カタカナ → 漢字

// 単語を並び替えて辞書順に

String[] array1 = {"this", "is", "a", "sample"};
// 昇順ソート
Arrays.sort(array1);
// 出力
for(int i = 0; i < array1.length; i++) {
	System.out.print(array1[i] + ", ");
}
// Output: a, is, sample, this,

// 文字列そのものを並び替えて辞書順に

// String型をChar配列に変換
char[] array1 = str1.toCharArray();
// 昇順ソート
Arrays.sort(array1);
// 出力
for(int i = 0; i < array1.length; i++) {
	System.out.print(array1[i]);
}
// Output: ,HWdellloor

【注意】
Java11におけるArrays.sort() の計算量は O(N logN) である。
Arrays.sort()に限った話ではないが、ソートをfor文で何度も繰り返すようなプログラムを書くと競技プログラミングにおいてはTLEになりかねないので注意しよう。

【変換編】

・String型 → int型

Integer.parseInt(数値の文字列);

System.out.println(Integer.parseInt("123"));
// Output: 123 (←int型)

・int型 → String型

String.valueOf(数値);

他の方法として 数値.toString(); も使える。
ただし toString() は変換対象がnullだった場合NullPointerExceptionになるので注意しよう。

System.out.println(String.valueOf(123)); 
// Output: 123 (←String型)

・int型 ↔ double型

(double) int型数値 : int型 → double型
(int) double型数値 : double型 → int型

キャスト演算子による強制型変換。
int型の数値をdouble型にすると 数値.0 になり、double型の数値をint型にすると小数点以下が切り捨てられる。

System.out.println((double) 123);
// Output: 123.0

System.out.println((int) 123.456);
// Output: 123

・int型 ↔ char型 (見かけ上の数字の変換)

数値 - '0' : char型 → int型
(char)('0' + 数値) : int型 → char型

専用のメソッドは存在しないが、変換対象の数値が'0'〜'9'と分かっているので上記の方法が使える。

char ch = '1'; // 変換対象
int num = ch - '0';
System.out.println(num);
// Output: 1 (←int型)
		
int num2 = 2; // 変換対象
char ch2 = (char)('0' + num2);
System.out.println(ch2);
// Output: 2 (←char型)

・int型 ↔ char型 (文字コード番号への変換)

(char)int型 : その文字コード番目の文字
(int)char型 : その数字(文字)の文字コード番号

強制型変換することで 文字コード上の番号 に変換することができる。
見かけ上の数字を直接変換できるわけではないので注意。

どの文字がどの番号に来るかは文字コード表を参考に。

System.out.println((int) '5');
// Output: 53 (文字コード表で文字'5'は53番目である)

System.out.println((char) 50);
// Output: 2  (文字コード表で50番目の文字は'2'である)

・char型配列 → String型

String 変数名 = new String(char型配列);

char[] ch = {'a', 'b', 'c'};
String str2 = new String(ch); 
System.out.println(str2); 
// Output: abc

【Math. 編】

・数値の絶対値を求める

Math.abs(数値);

System.out.println(Math.abs(-100)); 
// Output: 100

・2つの数値の大小を比較

Math.max(数値, 数値); : 大きい方の数値を返す
Math.min(数値, 数値); : 小さい方の数値を返す

System.out.println(Math.max(10000, 1)); 
// Output: 10000

System.out.println(Math.min(10000, 1)); 
// Output: 1

・数値を累乗

Math.pow(n, m); : n^mを返す

戻り値はdouble型。

System.out.println(Math.pow(2, 10)); 
// Output: 1024.0

・円周率（π）

Math.PI;

戻り値はdouble型。
メソッドではなく定数なので()は不要。

System.out.println(Math.PI); 
// Output: 3.141592653589793

・三角関数

Math.sin(ラジアン);
Math.cos(ラジアン);
Math.tan(ラジアン);

引数のラジアンと戻り値はdouble型。
この他にも逆正弦、双曲線正弦など一通り用意されている。

少数は誤差が怖いので扱いには十分注意したい。
もし可能なら予め10^n倍して整数として演算を行い、最後に少数に戻すという方法も視野に入れよう。

System.out.println(Math.sin(Math.PI / 6)); //sin (π/6)
// Output: 0.49999999999999994

・弧度法 ↔ 度数法

Math.toRadians(角度);
Math.toDegrees(ラジアン);

引数の角度,ラジアン並びに戻り値はdouble型。

System.out.println(Math.toRadians(30));
// Output: 0.5235987755982988

System.out.println(Math.toDegrees(0.52));  
// Output: 29.79380534680281

・数値の平方根 , 立方根

Math.sqrt(数値); : 平方根
Math.cbrt(数値); : 立方根

戻り値はdouble型。

System.out.println(Math.sqrt(16)); 
// Output: 4.0

System.out.println(Math.cbrt(8));  
// Output: 2.0

・AND , OR , XOR , NOT演算

&, | , ^ , ~

ビット演算子。
意外とA問題でも出題されるので、この演算子の存在を知っておくだけでも役に立つ（とくにxor）。

// 0b〇〇 = 2進数表記

System.out.println(0b0110 & 0b1010);
// Output: 2 (←0b0010)
System.out.println(0b0110 | 0b1010);
// Output: 14 (←0b1110)
System.out.println(0b0110 ^ 0b1010);
// Output: 12 (←0b1100)
System.out.println(~0b0110);
// Output: -7 (←0b1001)

・2進数 , 8進数 , 16進数文字列に変換

Integer.toBinaryString(数値); : → 2進数
Integer.toOctalString(数値); : → 8進数
Integer.toHexString(数値); : → 16進数

存在を知っておくと便利なやつ。
int型ではなくString型であることに注意。

System.out.println(Integer.toBinaryString(10)); 
// Output: 1010

System.out.println(Integer.toOctalString(10)); 
// Output: 12

System.out.println(Integer.toHexString(10)); 
// Output: a

・数値のlog[e] , log[10]

Math.log(数値); : log[e]数値
Math.log10(数値); : log[10]数値

戻り値はdouble型。

System.out.println(Math.log(10)); 
// Output: 2.302585092994046

System.out.println(Math.log10(100)); 
// Output: 2.0

・数値を切り上げ/切り捨て/少数第1位で四捨五入

Math.ceil(数値);
Math.floor(数値);
Math.round(数値);

戻り値はdouble型, 四捨五入のみlong型。
少数第1位以外で四捨五入したい場合は、予め数値を10^n倍してから四捨五入し、10^nで割ろう。

System.out.println(Math.ceil(1.99));  
// Output: 2.0

System.out.println(Math.floor(1.01));  
// Output: 1.0

System.out.println(Math.round(1.50)); 
// Output: 2

・1～10までのランダムな数値

(int)(Math.random() * 10) + 1

Math.randomは0.0以上1.0未満のランダムな値を返す。
それを10倍にして+1してint型に変換している。

競プロではデバッグで使う事が多い。

System.out.println((int)(Math.random() * 10) + 1);
// Output: 5 (←1~10までのランダムな数値)

・文字が数字か判定する

Character.isDigit('文字')

引数はchar型、戻り値はboolean型。
与えられた文字が数字(0～9)であればtrue、そうでなければfalseを返す。

if(Character.isDigit('a')) {
	System.out.println("数字だよ");
} else{
    System.out.println("数字じゃないよ");
}
// Output: 数字じゃないよ

【String.format 編】

String.format() メソッドを使うことで、数値や文字列を任意の形式に編集することができる。

String.format("書式文字列", 編集したい値);

書式文字列 は フォーマット指定子 % から始まり、任意の 書式 を書き、編集したい値の 型 で終わる。

型 について、整数(10進数)は d、整数(16進数)は x、整数(8進数)は o、浮動小数点数は f、文字列は s、文字は c、真偽値は b。

返り値はすべてString型になる。

また、System.out.printf();として出力することで、String型の変数に代入することなく直接文字列や数値などを指定した書式で画面に出力することができる。

・数値を先頭からn桁0埋め

String.format("%0(桁数)d", 数値);

例えば0埋め4桁なら "%04d" 。

System.out.printf("%04d", 7); 
// Output: 0007

・数値を先頭からn桁空白埋め

String.format("%(桁数)d", 数値);

例えば4桁なら "%4d" 。

System.out.printf("%4d", 7); 
// Output:   7 (←7の前に3つ空白がある)

・数値を下位桁から3桁ごとにカンマ区切り

String.format("%,d", 数値);

区切りの桁数を指定することはできない。

System.out.printf("%,d", 12345678); 
// Output: 12,345,678

・浮動小数点数の小数部の桁数を指定

String.format("%.(桁数)f", 数値)

例えば小数点以下3桁にするなら "%.3f" 。
いわゆる 丸め処理。
この場合は指定した桁数より1つ下の桁で四捨五入を行う。

System.out.printf("%.3f", 1.234567); 
// Output: 1.235

【特殊な書き方編】

・拡張for文 (for-each構文)

for(要素の型 要素の変数名 : 配列名) { }

指定した配列から要素を取り出し、変数に格納し、処理を実行する。
順に続けていき最後の要素を実行したら終了。

String array1[] = {"a", "b", "c"};

for (String s : array1) {
	System.out.print(s + ", ");
} 
// Output: a, b, c, 

・三項演算子を使った出力

System.out.print( ブール値を返す条件式 ? "trueでの表示文" : "falseでの表示文" );

三項演算子を用いることでif-else文を省略できる。

可読性が下がるので普通にif-elseを書いたほうがよいが、他人の解答を眺めるとA,B問題レベルの簡素なプログラムで見かける事が多いので 存在を知ってるとコードが読めてちょっと嬉しい。

System.out.println(1 == 2 ? "Yes" : "No"); 
// Output: No

【リスト編】

配列ではなくリストを使う場面

配列に要素の追加、削除、挿入、置き換え、検索などを行いたいときや、固定長ではなく 可変長 の配列を取り扱いたい時はリストが大いに役に立つ。

import java.util.List; 及び import java.util.ArrayList; を一番上に書き、
「リストの生成」→「リストに要素を追加」→「検索などの処理」という手順を踏む。

(import java.util.*;でまとめてimportすれば楽だが、どのクラスが必要なのか知っておくとより良い)

以下、リスト名は list1 で統一する。

・リストの生成

List<データ型> 変数名 = new ArrayList<>();

データ型はラッパークラスなので、基本的には先頭を大文字にすればよい。
但しint型はIntegerになることと、char型はCharacterになることに注意。

List<Integer> list1 = new ArrayList<>();

・要素を追加

list1.add(要素);

要素について、例えば文字列なら.add("こんにちは"); 、数値なら.add(123); となる。

list1.add(挿入位置, 要素);

上のように追加する位置を指定することもできる（挿入）。
挿入位置は、リストの先頭を0として要素の隙間を最初から数えたものだ。

int[] array1 = {1, 2, 3, 2, 1};

// リストに配列の要素を追加
for(int i : array1) {
	list1.add(i);
}
System.out.println(list1);
// Output: [1, 2, 3, 2, 1]

// 要素を挿入
list1.add(1, 5);
System.out.println(list1);
// Output: [1, 5, 2, 3, 2, 1]

・要素の位置を検索

list1.indexOf(要素);

先頭を0番目として要素を順番に検索し、最初に見つかった要素のインデックス番号を返す。
見つからなければ -1。

また、list1.lastIndexOf(要素); で逆から検索した番号(＝リストの終わりに近い要素のインデックス番号)も返せる。

// list1 = [1, 5, 2, 3, 2, 1]

System.out.println(list1.indexOf(1));
// Output: 0 (←0番目に1がある)
System.out.println(list1.lastIndexOf(1));
// Output: 5 (←5番目に1がある)

・位置から要素を取得

list1.get(インデックス番号);

そのインデックス番号にある要素を返す。

// list1 = [1, 5, 2, 3, 2, 1]
System.out.println(list1.get(4));
// Output: 2 (←4番目の要素は2)

・リストの要素数を取得

list1.size();

リスト全体の要素数を返す。

// list1 = [1, 5, 2, 3, 2, 1]
System.out.println(list1.size());
// Output: 6 

・要素を置き換え

list1.set(インデックス番号, 置き換え後の要素);

指定した位置の要素を置き換える。

// list1 = [1, 5, 2, 3, 2, 1]
list1.set(0, 8);
System.out.println(list1);
// Output: [8, 5, 2, 3, 2, 1]

・要素を削除

list1.remove(インデックス番号);

削除した要素よりも後ろの要素はそのまま前に詰められる。

// list1 = [8, 5, 2, 3, 2, 1]
list1.remove(0);
System.out.println(list1);
// Output: [5, 2, 3, 2, 1]

・要素の順番を反転

Collections.reverse(リスト名);

リスト内の要素の順番を反転させる。
ソースコードの先頭に import java.util.Collections; を書いてから使用する。

// list1 = [5, 2, 3, 2, 1]
Collections.reverse(list1);
System.out.println(list1);
// Output: [1, 2, 3, 2, 5]

・要素を全て削除

list1.clear();

リスト内の全ての要素を削除する。

// list1 = [1, 2, 3, 2, 5]
list1.clear();
System.out.println(list1);
// Output: []

【その他】

・HashSet , TreeSet

要素の重複を許さない集合 を取り扱う HashSetクラス によって簡単に重複が探せる。

最初に import java.util.HashSet; を書き、インスタンス化してから使用する。
例えば以下のように、「拡張for文で配列を参照していき一番最初に重複した要素を出力する」ということも可能になる。

int[] array1 = {1, 2, 3, 1, 2};

// HashSetインスタンスを作成
HashSet<Integer> hs = new HashSet<>();

for(int n : array1) {
    // nを集合に追加できない場合(＝重複が生まれた場合)は知らせる
    if(!hs.add(n)) { 
        System.out.println("重複してるよ");
        break;
    }
}
// Output: 重複してるよ

また、HashSetの拡張クラスである TreeSetクラス は、要素を追加すると自動で昇順ソートされた状態になる。
要素の重複を許さない点はHashSetクラスと同じ。
最初に import java.util.TreeSet; を書き、インスタンス化してから使用する。

int[] array1 = {5, 1, 2, 4, 3};

// TreeSetインスタンスを作成
TreeSet<Integer> ts = new TreeSet<>();

// 要素を追加
for(int n : array1) {
	ts.add(n);
}
// TreeSetを出力
for(int n : ts) {
	System.out.print(n);
}
// Output: 12345

・二次元配列

javaでは配列の要素の中に別の配列を格納することが出来る。つまり、普通の配列の要素の並びが直線的であるのに対し、二次元配列では平面的に要素を格納することができる。
基礎的な書き方は普通の配列と同じで、インデックスの[ ]が一つ増える。

競プロ序盤においては、表形式で入力を受け取りたい 時や、 後述の DP(動的計画法) でのテーブルとしてもよく使用する。

// 宣言
int[][] nums = new int[行の要素数][列の要素数];

// 代入
// 例：2行目3列目の箱 (「配列の先頭から2番目の要素」の中の「先頭から3番目」) に代入
nums[1][2] = 5;

・例外を投げる

IllegalArgumentExceptionインスタンスを投げることで、不正な引数をメソッドに渡していることをJVMに報告する。
デバッグ時に使う。

if(n < 0) {
	throw new IllegalArgumentException("nは0以上の値を指定して下さい。指定値=" + n);
}

・入出力の高速化

例えば出力について、StringBuilderクラス を利用して文字列の結合を行い、複数行の出力を1回で行うという方法がある。
インスタンス名.append()メソッドの引数で結合したい文字列を指定していく。
改行は"\n"、半角スペースは"\s"。

StringBuilder sb = new StringBuilder("");

sb.append("あいうえお\n");
sb.append("かき\sくけこ");

System.out.println(sb);
// Output: あいうえお
// Output: かき くけこ

また、 Scannerクラス や System.out.println が遅すぎる上にメモリ消費量も多いため、競プロ上級者は大抵FastScannerクラスなどの自作ライブラリを使用している。

Scannerクラスの代替として有名な FastScanner については@p_shiki37さんが以下の記事で書いて下さっている。
初学者にはやや難解だが、Javaで実行時間を短縮するためのテクニックが入出力に限らず網羅されており、C問題以降でTLEを防ぐために非常に有用な記事だ。

FastScannerに限らず 二分探索など汎用性の高いプログラムはメソッド化してテンプレートに追加しておけば時短になる上にプログラム全体の見通しも良くなる。

・DP/貪欲法/二分探索/bit全探索/Union-Find etc...

AtCoderでは計算量が Ο(10^8) を越えると TLE になることが多い。
そのため、計算量を意識しなければいけない事が多くなるC問題以降は アルゴリズム を知っていないとまるで歯が立たなくなり、
これは競プロ初心者にとっての大きな壁になっている。

頻出アルゴリズムを体系的に学べる良質なコンテンツ を紹介する。いずれも無料だ。

・アルゴ式
・競プロ典型90門
・アルゴリズムロジック
・AOJ (AIZU ONLINE JUDGE)

特に頻出の DP(動的計画法) については DPまとめコンテスト という有り難い問題集がある。
問題の解説は こちら。

・公式解答が理解できなかったら？

pythonやC++など言語は違なるものの、有志による以下の解説ページが参考になるかもしれない。

・youtubeでの公式解説配信 ←特にオススメ！
・かつっぱさんのABC解説動画
・けんちょんさんの競プロ精進記録
・hamayanhamayanさんのブログ
・佐野さんの「ものすごく丁寧でわかりやすいABC解説一覧」
・競技プログラミングをするフレンズさんのX(twitter)

この他にも、同じ言語でACしている人の解答を検索して参考にしたり、 X(Twitter)のAtCoder公式コミュニティ で質問するのも手だ。
また、開催から数週間遅れての公開になるが、コンテストのテストケースは こちらのページ で全て公開されている。過去問を解いていて数ケースだけエラーが出てしまう場合に役立つだろう。

【最後に】

読んでくださって有難うございました。
これからJavaで競技プログラミングを始める方にとって本稿が少しでもお役に立てれば幸いです。
もし誤字脱字や技術的なご指摘がございましたらお気軽にコメントください。