Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
145
Help us understand the problem. What is going on with this article?
@p_shiki37

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

More than 3 years have passed since last update.

この記事は「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(インターフェース)

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

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

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

Comparableが実装されている場合
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(1);//要素の追加
pq.poll();  //最小の要素の取り出しと削除
Comparableが実装されている場合・逆順
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(1);//要素の追加
pq.poll();  //最大の要素の取り出しと削除
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(インターフェース)

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

HashSet

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

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のキーに使うクラスは、equalshashCodeを規約に沿って実装する必要があります。

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クラスを作成し、equalshashCodeをオーバーライドします。さらに、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のメソッドの一部
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を実装するときなどに役立ちます。
parseInttoStringは基数を指定することで10進数以外の処理ができます。
toBinaryStringtoHexStringは引数を符号なし整数として扱います。bitDPのデバッグなどに役立ちます。

BigInteger

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

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と比較するとInfinityNaNに相当するものはありません。
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)で十分なことがあります。
一方、PatternMatcherを使えばグループなどの機能を使えます。

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

  1. 厳密には、償却定数時間です。つまり、$n$回の操作が$O(n)$の時間で出来ます。 

  2. ハッシュが衝突する場合は最悪で線形時間になります。 

145
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
145
Help us understand the problem. What is going on with this article?