Javaで競技プログラミングをするときによく使う標準ライブラリ

この記事は「[Java競技プログラミング](http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b)」の後半部分を元に書き直したものです。前半部分は「[Javaで競技プログラミングをするときの罠とテク](http://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4)」です。

Javaで競技プログラミングをするときによく使うクラスやメソッドをまとめました。
各クラスのより詳細な説明はドキュメントを参照してください。
https://docs.oracle.com/javase/jp/8/docs/api/index.html?overview-summary.html

計算時間について、**定数時間**は要素数と関係ない時間で終わることを表します。**対数時間**は要素数$n$に対して$O ({\rm log}(n))$の時間で終わることを表します。**線形時間**は要素数に比例した時間で終わることを表します。
線形時間より対数時間、対数時間より定数時間の方が良いです。定数時間か対数時間なら十分高速と言えます。

CollectionsやMapに対する操作の計算量については、[このページ(英語)](http://infotechgems.blogspot.jp/2011/11/java-collections-performance-time.html)が詳しいです。

#Collection(インターフェース)
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Collection.html

`List`や`Set`などに共通のインターフェースです。
以降に説明する`Collection`インターフェースを実装しているクラスではすべて`size`や`isEmpty`などのメソッドが使えます。

```java
Collection<Integer> c = new ArrayList<>();
c.size();   //要素数を返す
c.isEmpty();//空かどうかを返す。 (c.size() == 0) と同じ
for(int x:c) {
	//インデックスが不要な場合は、拡張for文を書ける。
}
```

##ArrayList
https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayList.html

可変長の配列が欲しい場合、`ArrayList`を使うのが間違いないです。
ランダムアクセス・要素の末尾への追加・末尾の要素の削除が定数時間でできます。[^1]

```java
ArrayList<Integer> al = new ArrayList<>();
al.add(1); //要素の末尾への追加
al.get(0); //ランダムアクセス
al.remove(al.size() - 1); //末尾の要素の削除
```

##ArrayDeque
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/ArrayDeque.html

双方向キューです。スタックが必要な場合もこれを使います。
先頭と末尾への要素の追加・先頭と末尾の要素の取り出しと削除が定数時間でできます。[^1]

```java:デックとして利用
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.offerFirst(1);//先頭への追加
deq.offerLast(2); //末尾への追加
deq.pollFirst();  //先頭の取得と削除
deq.pollLast();   //末尾の取得と削除
```

```java:キューとして利用
Queue<Integer> q = new ArrayDeque<>();
q.offer(1);//要素の追加
q.poll();  //要素の取得と削除
```

```java:スタックとして利用
ArrayDeque<Integer> stack = new ArrayDeque<>(); //Stackにはキャストできない
stack.offerFirst(1);//要素の追加
stack.pollFirst();  //要素の取得と削除
```

##PriorityQueue
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/PriorityQueue.html

優先度つきキューです。要素の追加と、最小の要素の取り出しと削除が対数時間でできます。
最小の要素が複数ある場合、`peek`や`poll`の対象になるのはそのうちの1つです。
要素の比較のために、要素のクラスに`Comparable`が正しく実装されているか、コンストラクタで`Comparator`を渡す必要があります。

```java:Comparableが実装されている場合
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);//要素の追加
pq.poll();  //最小の要素の取り出しと削除
```

```java:Comparableが実装されている場合・逆順
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(1);//要素の追加
pq.poll();  //最大の要素の取り出しと削除
```

```java:Comparatorを渡す場合
//Pointをx座標が小さい順に取り出すPriorityQueueを作成する
PriorityQueue<Point> pq = new PriorityQueue<>((p1,p2)->Integer.compare(p1.x,p2.x));
pq.offer(new Point(1,2));//要素の追加
pq.poll();               //最小の要素の取り出しと削除
```

##Set(インターフェース)
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/Set.html

`Set`は同じ要素が重複しないデータ構造です。`Set`に含まれている要素を追加しても`Set`は変更されません。
`Set`に含まれているオブジェクトに、`equals`に影響を及ぼすような変更をしてはいけません。
競技プログラミングでは`HashSet`と`TreeSet`をよく使います。

###HashSet
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/HashSet.html

`HashSet`はハッシュ関数を用いた`Set`の実装です。
要素の追加・検索・削除が定数時間でできます[^2]。特定の順序は保たれません。
`HashSet`にオブジェクトを入れるときは、`equals`と`hashCode`を規約に沿って実装する必要があります。

```java
HashSet<Integer> hs = new HashSet<>();
hs.add(1);      //要素の追加
hs.contains(1); //要素が含まれているか判定
hs.remove(1);   //特定の要素の削除
```

###TreeSet
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/TreeSet.html

`TreeSet`は平衡二分探索木を用いた`Set`の実装です。ソートされる`Set`と考えることができます。
要素の追加・検索・削除・次に大きい要素・次に小さい要素の取り出しなどが対数時間でできます。
`PriorityQueue`と同様、要素の比較のために、要素のクラスに`Comparable`が正しく実装されているか、コンストラクタで`Comparator`を渡す必要があります。

```java
TreeSet<Integer> ts = new TreeSet<>();
ts.add(1);      //要素の追加
ts.contains(1); //要素が含まれているか判定
ts.first();     //最も小さい要素を返す
ts.pollFirst(); //最も小さい要素を取得・削除する
ts.last();      //最も大きい要素を返す
ts.pollLast();  //最も大きい要素を取得・削除する
ts.ceiling(1);  //これ以上の要素のうち、最も小さい要素を返す
ts.higher(1);   //これより大きい要素のうち、最も小さい要素を返す
ts.floor(1);    //これ以下の要素のうち、最も大きい要素を返す
ts.lower(1);    //これより小さい要素のうち、最も大きい要素を返す
ts.remove(1);   //特定の要素の削除
```

#HashMap
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/HashMap.html

`Map`は、キーを値にマッピングするものです。一つのキーに対して一つの値が対応します。
エントリーの追加(put)・キーに対する値の取得(get)が定数時間でできます[^2]。
`HashMap`のキーに使うクラスは、`equals`と`hashCode`を規約に沿って実装する必要があります。

```java
HashMap<Integer, Integer> hm = new HashMap<>();
hm.put(1, 1);      //キーと値の組の追加
hm.containsKey(1); //キーがマップに含まれているか判定
hm.get(1);         //キーに対応する値を返す
hm.keySet();       //キーの一覧のSetを返す
hm.values();       //値の一覧のSetを返す
hm.entrySet();     //エントリーの一覧のSetを返す
```

#Arrays/Collections
http://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/Arrays.html
http://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/Collections.html

`Arrays`は配列に対するメソッドが、`Collections`には`Collection`に対するメソッドがたくさんあります。

配列のソートには`Arrays.sort`を使います。オブジェクトの配列をソートする場合、オブジェクトに`Comparable`が実装されているか、`Comparator`を引数に渡す必要があります。また、プリミティブの配列をソートする場合は、アルゴリズムが異なるため低速になる場合があります。
リストのソートには`Collections.sort`を使います。こちらも、オブジェクトに`Comparable`が実装されているか、`Comparator`を引数に渡す必要があります。

二分探索には`binarySearch`メソッドを使います。これも、オブジェクトに`Comparable`が実装されているか、`Comparator`を引数に渡す必要があります。また、配列やリストはあらかじめソートされている必要があります。
一致する値がある場合にはそのインデックスが帰ります。一致する値が複数ある場合そのうちのどのインデックスが帰ってくるかは分かりません。
一致する値が無かった場合、返り値`x`に対して`~x`は、キーより大きい値のうち最も小さいもののインデックスとなります。

```java
Integer[] array = {5,3,1,2,4};
List<Integer> list = Arrays.asList(array);

Arrays.sort(array);                                   //ソート
Arrays.sort(array, (x,y)->Integer.compare(y, x));     //コンパレータを渡してソート
Collections.sort(list);                               //ソート
Collections.sort(list, Collections.reverseOrder());   //逆順にソート
Collections.sort(list, (x,y)->Integer.compare(y, x)); //コンパレータを渡してソート
list.sort(Collections.reverseOrder());                //逆順にソート

Arrays.binarySearch(array, 3);     //二分探索
Collections.binarySearch(list, 3); //二分探索

Collections.reverse(list); //リストを逆順にする

Arrays.fill(array, 3); //配列を同じ値で埋める
Arrays.copyOf(array, array.length); //配列のコピーを返す
Arrays.copyOfRange(array, 0, 3);    //配列のコピーを返す

Arrays.toString(array);     //配列を文字列にして返す
Arrays.deepToString(array); //配列を文字列にして返す(多次元配列の中身も文字列化される)
list.toString();            //リストを文字列にして返す

Arrays.hashCode(array); //配列のハッシュを返す
list.hashCode();        //リストのハッシュを返す
```

#equals,hashCode,compareToの実装例
`Pair`クラスを作成し、`equals`と`hashCode`をオーバーライドします。さらに、`Comparable`インターフェースを実装します。

```java
class Pair implements Comparable<Pair> {
	int a,b;
	public Pair(int a,int b) {
		this.a = a;
		this.b = b;
	}
	
	//(a,b)が一致
	@Override
	public boolean equals(Object o) {
		if (o instanceof Pair) {
			Pair p = (Pair) o;
			return a == p.a && b == p.b;
		}
		return super.equals(o);
	}
	
	/* 
	 * x.equals(y) ならば hashCode(x) == hashCode(y)でなければならない。
	 * この実装では同じハッシュ値をもつペアを容易に見つけられるため、ハッシュとしては弱い。
	 */
	@Override
	public int hashCode() {
		return a ^ b;
	}

	//辞書順比較
	@Override
	public int compareTo(Pair o) {
		if (a != o.a) {
			return Integer.compare(a, o.a);
		}
		return Integer.compare(b, o.b);
	}
}
```

#Math
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/lang/Math.html

`Math`クラスは様々な計算のためのメソッドがあります。

```java:Mathのメソッドの一部
Math.abs(-1); //絶対値
Math.sin(Math.PI); //三角関数　Math.PIは円周率
Math.log(Math.E); //対数関数 Math.Eはネイピア数
Math.pow(10, 3); //累乗
Math.max(1, 2); //最大値
```

$\sqrt{x^2 + y^2}$を求める、`Math.hypot(double x,double y)`というメソッドがありますが、低速なため使わない方が良いです。オーバーフローの心配がなければ`Math.sqrt(x * x + y * y)`としましょう。

#Integer/Long
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/lang/Integer.html
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/lang/Long.html

`Integer`クラスと`Long`クラスにはそれぞれintとlongの処理に役立つさまざまなメソッドがあります。

```java
Integer.bitCount(x); //x2の補数バイナリ表現で1の数
Integer.numberOfLeadingZeros(x); //xの2の補数バイナリ表現で先頭に続く0の数
Integer.numberOfTrailingZeros(x); //xの2の補数バイナリ表現で末尾に連続する0の数
Integer.compare(x, y); //x < yならば負の数、x == yならば0、x > yならば正の数を返す
Integer.parseInt("10", 2); //文字列を基数を指定してパースする
Integer.toString(2,2); //数値を指定した基数で文字列に変換する
Integer.toBinaryString(2); //数値を2進数の文字列にする
Integer.toHexString(17); //数値を16進数の文字列にする
```

`bitCount`,`numberOfLeadingZeros`,`numberOfTrailingZeros`といったメソッドは2進数に関係する問題やbitDPで役に立つことがあります。
`compare(x, y)`は自分で`compareTo`を実装するときなどに役立ちます。
`parseInt`や`toString`は基数を指定することで10進数以外の処理ができます。
`toBinaryString`や`toHexString`は引数を符号なし整数として扱います。bitDPのデバッグなどに役立ちます。

#BigInteger
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/math/BigInteger.html

longで収まらないような大きな整数を扱えるクラスです。
このクラスはイミュータブルです。例えば、`a.add(b)`は`a+b`を表す新たな`BigInteger`を返します。`a`や`b`が変更されることはありません。

```java
BigInteger a = new BigInteger("5"); //5
BigInteger b = BigInteger.valueOf(13); //6
BigInteger c = BigInteger.TEN.pow(100); //10^100
a.add(b);        //a + b
a.subtract(b);   //a - b
a.multiply(b);   //a * b
a.divide(b);     //a / b
a.remainder(b);  //a % b
a.mod(b);        //a mod b
a.gcd(b);        //gcd(a,b)
a.abs();         //|a|
a.modInverse(b); //a^(-1) (mod b)
a.modPow(c, b);  //a^c (mod b)
c.nextProbablePrime(); //cより大きい最初の素数
a.longValue(); //longに変換
```

`nextProbablePrime`は適当な素数を用意したり、チャレンジケースを生成したりするのに便利です。

#BigDecimal
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/math/BigDecimal.html

任意精度の10進数を表すクラスです。`BigInteger`の整数部と、`int`のスケールからなり、$X \times 10^Y$を表します。
このクラスはイミュータブルです。
doubleより範囲や精度が優れた実数型と考えることもできます。ただし、`double`と比較すると`Infinity`や`NaN`に相当するものはありません。
`BigDecimal`では、丸めモードを指定しないと、正確な結果が表現できない場合に例外がスローされます。
例えば、`BigDecimal.ONE.divide(BigDecimal.valueOf(3))`という計算は、結果が$0.3333 \dots$となり、正確に表すことが不可能なため例外が発生します。

```java
BigDecimal a = new BigDecimal("2.5");
BigDecimal b = BigDecimal.valueOf(3);
System.out.println(a.divide(b,MathContext.DECIMAL128)); //34桁の精度で割り算をする
a.doubleValue(); //doubleに変換する
```

#Scanner
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/util/Scanner.html

改行やスペース区切りの入力をパースして数値や文字列を読み込むのに便利なクラスです。正規表現を使用しているため低速です。
より高速な入力のパース方法については[こちらの記事](http://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4)で説明しています。

入力が期待しているものと違う場合、`InputMismatchException`がスローされます。
入力を読み終わったら、`close()`を呼び出したほうが良いですが、数秒しか動かないプログラムで問題になるシーンは少ないと思います。

```java
Scanner sc = new Scanner(System.in); //標準入力から読み込むScannerを作成
sc.next(); //次の文字列を読み込む
sc.nextLine(); //次の行を読み込む
sc.nextInt(); //次のintを読み込む
sc.nextLong(); //次のlongを読み込む
sc.nextDouble(); //次のdoubleを読み込む
sc.nextBigInteger(); //次のBigIntegerを読み込む
sc.nextBigDecimal(); //次のBigDecimalを読み込む
sc.close(); //スキャナをクローズする(行儀が良い)
```


#String
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/lang/String.html

文字列を表現するイミュータブルなクラスです。

```java
String s = "3billiondevicesrunjava";
String t = "lion";
s.length(); //文字列の長さを返す
s.equals(t); //一致するか調べる
s.compareTo(t); //辞書順で比較する
s.charAt(0); //指定したインデックスの値を返す
s.substring(2,5); //部分文字列を返す
s.toCharArray(); //文字列を表すchar[]を返す
s.indexOf(t); //指定した文字列が最初に出現するインデックスを返す
s.lastIndexOf(t); //指定した文字列が最後に出現するインデックスを返す
s.startsWith(t); //文字列が指定された接頭詞で始まるか判定する
s.endsWith(t); //文字列が指定された接尾詞で終わるか判定する
s.contains(t); //指定した文字列を含むか調べる
s.matches("\\w+"); //指定した正規表現と一致するか判定する
s.toLowerCase(); //小文字に変換する
s.toUpperCase(); //大文字に変換する
s.replace('b','m'); //文字を置換する
s.replace("b","tri"); //文字列を置換する
s.replaceAll("[0-9]+","10"); //正規表現を用いて置換する
s.split("n"); //文字列を正規表現によって分割する
String.format("%04d", 123); //フォーマットした文字列を返す
String.valueOf(5); //Integer.toString(5) と同じ
```

#StringBuilder
https://docs.oracle.com/javase/jp/8/docs/api/index.html?java/lang/StringBuilder.html

可変な文字列です。主に文字列を高速に連結するのに使います。

```java
StringBuilder sb = new StringBuilder();
sb.append("hoge"); //hogeを末尾に追加
sb.append(3);      //3を末尾に追加
sb.toString();     //-> hoge3
```

#Pattern / Matcher
Pattern: https://docs.oracle.com/javase/jp/8/docs/api/java/util/regex/Pattern.html
Matcher: https://docs.oracle.com/javase/jp/8/docs/api/java/util/regex/Matcher.html

シンプルな正規表現の利用の場合、`String.matches(String,String)`や`String.replaceAll(String,String)`で十分なことがあります。
一方、`Pattern`と`Matcher`を使えばグループなどの機能を使えます。

```java
public static void main(String[] args) {
	Pattern p = Pattern.compile("<([0-9]+),([0-9]+)>");
	Matcher m = p.matcher("<12,345>");
	if (m.matches()) {
		System.out.println(m.group(1) + " " + m.group(2));
	}else{
		System.out.println("fail");
	}
}
```

```text:実行結果
12 345
```

[^1]: 厳密には、償却定数時間です。つまり、$n$回の操作が$O(n)$の時間で出来ます。
[^2]: ハッシュが衝突する場合は最悪で線形時間になります。