この記事は「Java競技プログラミング」の後半部分を元に書き直したものです。前半部分は「Javaで競技プログラミングをするときの罠とテク」です。
Javaで競技プログラミングをするときによく使うクラスやメソッドをまとめました。
各クラスのより詳細な説明はドキュメントを参照してください。
https://docs.oracle.com/javase/jp/8/docs/api/index.html?overview-summary.html
計算時間について、定数時間は要素数と関係ない時間で終わることを表します。対数時間は要素数$n$に対して$O ({\rm log}(n))$の時間で終わることを表します。線形時間は要素数に比例した時間で終わることを表します。
線形時間より対数時間、対数時間より定数時間の方が良いです。定数時間か対数時間なら十分高速と言えます。
CollectionsやMapに対する操作の計算量については、このページ(英語)が詳しいです。
Collection(インターフェース)
ListやSetなどに共通のインターフェースです。
以降に説明するCollectionインターフェースを実装しているクラスではすべてsizeやisEmptyなどのメソッドが使えます。
Collection<Integer> c = new ArrayList<>();
c.size(); //要素数を返す
c.isEmpty();//空かどうかを返す。 (c.size() == 0) と同じ
for(int x:c) {
//インデックスが不要な場合は、拡張for文を書ける。
}
ArrayList
可変長の配列が欲しい場合、ArrayListを使うのが間違いないです。
ランダムアクセス・要素の末尾への追加・末尾の要素の削除が定数時間でできます。1
ArrayList<Integer> al = new ArrayList<>();
al.add(1); //要素の末尾への追加
al.get(0); //ランダムアクセス
al.remove(al.size() - 1); //末尾の要素の削除
ArrayDeque
双方向キューです。スタックが必要な場合もこれを使います。
先頭と末尾への要素の追加・先頭と末尾の要素の取り出しと削除が定数時間でできます。1
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.offerFirst(1);//先頭への追加
deq.offerLast(2); //末尾への追加
deq.pollFirst(); //先頭の取得と削除
deq.pollLast(); //末尾の取得と削除
Queue<Integer> q = new ArrayDeque<>();
q.offer(1);//要素の追加
q.poll(); //要素の取得と削除
ArrayDeque<Integer> stack = new ArrayDeque<>(); //Stackにはキャストできない
stack.offerFirst(1);//要素の追加
stack.pollFirst(); //要素の取得と削除
PriorityQueue
優先度つきキューです。要素の追加と、最小の要素の取り出しと削除が対数時間でできます。
最小の要素が複数ある場合、peekやpollの対象になるのはそのうちの1つです。
要素の比較のために、要素のクラスにComparableが正しく実装されているか、コンストラクタでComparatorを渡す必要があります。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);//要素の追加
pq.poll(); //最小の要素の取り出しと削除
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(1);//要素の追加
pq.poll(); //最大の要素の取り出しと削除
//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(インターフェース)
Setは同じ要素が重複しないデータ構造です。Setに含まれている要素を追加してもSetは変更されません。
Setに含まれているオブジェクトに、equalsに影響を及ぼすような変更をしてはいけません。
競技プログラミングではHashSetとTreeSetをよく使います。
HashSet
HashSetはハッシュ関数を用いたSetの実装です。
要素の追加・検索・削除が定数時間でできます2。特定の順序は保たれません。
HashSetにオブジェクトを入れるときは、equalsとhashCodeを規約に沿って実装する必要があります。
HashSet<Integer> hs = new HashSet<>();
hs.add(1); //要素の追加
hs.contains(1); //要素が含まれているか判定
hs.remove(1); //特定の要素の削除
TreeSet
TreeSetは平衡二分探索木を用いたSetの実装です。ソートされるSetと考えることができます。
要素の追加・検索・削除・次に大きい要素・次に小さい要素の取り出しなどが対数時間でできます。
PriorityQueueと同様、要素の比較のために、要素のクラスにComparableが正しく実装されているか、コンストラクタでComparatorを渡す必要があります。
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
Mapは、キーを値にマッピングするものです。一つのキーに対して一つの値が対応します。
エントリーの追加(put)・キーに対する値の取得(get)が定数時間でできます2。
HashMapのキーに使うクラスは、equalsとhashCodeを規約に沿って実装する必要があります。
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は、キーより大きい値のうち最も小さいもののインデックスとなります。
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インターフェースを実装します。
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
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の処理に役立つさまざまなメソッドがあります。
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
longで収まらないような大きな整数を扱えるクラスです。
このクラスはイミュータブルです。例えば、a.add(b)はa+bを表す新たなBigIntegerを返します。aやbが変更されることはありません。
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
任意精度の10進数を表すクラスです。BigIntegerの整数部と、intのスケールからなり、$X \times 10^Y$を表します。
このクラスはイミュータブルです。
doubleより範囲や精度が優れた実数型と考えることもできます。ただし、doubleと比較するとInfinityやNaNに相当するものはありません。
BigDecimalでは、丸めモードを指定しないと、正確な結果が表現できない場合に例外がスローされます。
例えば、BigDecimal.ONE.divide(BigDecimal.valueOf(3))という計算は、結果が$0.3333 \dots$となり、正確に表すことが不可能なため例外が発生します。
BigDecimal a = new BigDecimal("2.5");
BigDecimal b = BigDecimal.valueOf(3);
System.out.println(a.divide(b,MathContext.DECIMAL128)); //34桁の精度で割り算をする
a.doubleValue(); //doubleに変換する
Scanner
改行やスペース区切りの入力をパースして数値や文字列を読み込むのに便利なクラスです。正規表現を使用しているため低速です。
より高速な入力のパース方法についてはこちらの記事で説明しています。
入力が期待しているものと違う場合、InputMismatchExceptionがスローされます。
入力を読み終わったら、close()を呼び出したほうが良いですが、数秒しか動かないプログラムで問題になるシーンは少ないと思います。
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
文字列を表現するイミュータブルなクラスです。
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
可変な文字列です。主に文字列を高速に連結するのに使います。
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を使えばグループなどの機能を使えます。
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");
}
}
12 345