Java競技プログラミングメモ

#はじめに

この記事の内容を書きなおして、
「Javaで競技プログラミングをするときの罠とテク」
「Javaで競技プログラミングをするときによく使う標準ライブラリ」
という2つの記事にしました。
全体的に見直しをしたのでこちらを見ることをオススメします。

---

今までJavaで競技プログラミングをしていて自分がつまづいたところや、知って役に立ったと思ったことを振り返ってまとめた。

#入力
##Scannerが遅い・メモリを食う
標準入力で入力が渡されるオンラインジャッジでは、標準ライブラリのScannerを使うと楽にパースができる。

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();

しかしScannerは遅いしメモリを食う。入力が大きい場合にTLEやMLEを起こしたり、よりよいオーダーで問題を解く必要が出てきたりする。
高速化する簡単な方法として、パースをInteger.parseInt()に任せるというのがある。

Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.next());

さらに高速化が必要な場合は、Scannerの代わりになる処理を自前で実装することになる。比較的実装が軽い方法としては、BufferedReader.readLineで行ごとに読み込み、String.splitかStringTokenizerで分割する方法がある。
実装は重いが、InputStreamで文字を少しずつ読み込み自前でパースするのが高速かつ省メモリ。

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		}else{
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
	public boolean hasNext() { skipUnprintable(); return hasNextByte();}
	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			}else if(b == -1 || !isPrintableChar(b)){
				return minus ? -n : n;
			}else{
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
}

ベンチマークを簡単に取ってみた

入力処理が終わったあとにRuntime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()でメモリ使用量を計算したので、GCが入るかどうかで(?)オーダーが変わったりするのでメモリ使用量は参考程度。
newの回数が多そうなreadLine+split系はメモリを多く食い、整数を自前でパースした場合はnewが起きずに非常に高速かつ省メモリという傾向はあった。

$10^9$未満の非負の整数$10^7$個を改行区切りで渡し、総和を求める。(入力はファイルから)

	実行時間(ms)	メモリ使用量(byte)
Scanner.nextLong()	10585	119885880
Long.parseLong(Scanner.next())	6649	59768536
BufferedReader.readLine() + String.split + parseLong	4350	621540456
BufferedReader.readLine() + StringTokenizer + parseLong	3996	803218752
InputStream.read(byte[] b) + 自前整数パース	495	3020104

$10^9$未満の非負の整数を$1$行に$3 \times 10^3$個をスペース区切りで、$3 \times 10^3$行分渡して総和を求める。(入力はファイルから)

	実行時間(ms)	メモリ使用量(byte)
Scanner.nextLong()	9513	190954272
Long.parseLong(Scanner.next())	5910	49428296
BufferedReader.readLine() + String.split + parseLong	1708	314296040
BufferedReader.readLine() + StringTokenizer + parseLong	1719	80907608
InputStream.read(byte[] b) + 自前整数パース	466	3020104

$N=10^5$で複数の数値が一行にある場合や、$N=10^6$になると入力を受け取る方法をScanner以外に変えたほうが良さそう。

##Scanner.nextLine()
nextやnextIntなどで行末に到達した後にnextLineを呼び出すと、次の行が読まれるのではなく、空文字列が帰ってくるので注意する。

#結果の整形と出力
##文字列結合
Javaで文字列の結合は+演算子を使うことでできる。+演算子による結合は毎回新たなStringのインスタンスが作成されるため、たくさんの文字列を結合したいときにはStringBuilderを使う。

次のようなプログラムは遅い。

int n = 100;
String s = "";
for(int i=0;i<n;i++) {
	s += "hoge";
}

代わりにStringBuilderを使う。

int n = 100;
StringBuilder sb = new StringBuilder();
for(int i=0;i<n;i++) {
	sb.append("hoge");
}
String s = sb.toString();

##出力
標準出力に文字列を書き出すには、主にSystem.out.printlnを使うが、出力が大きい場合はTLEの原因になる。
解決策としては、PrintWriterを用いて自動フラッシュをしないようにする。
(StringBufferに出力を一度固める方法はメモリを多く使うという指摘がありました)

PrintWriter out = new PrintWriter(System.out);
int n = 100;
for(int i=0;i<n;i++) {
	out.println("hoge");
}
out.flush();

##小数点以下の桁数を指定する
DecimalFormatかSystem.out.printfを使う。doubleもBigDecimalも同じようにフォーマットできる。
System.out.printfを使う場合、フォーマットのfに対して引数に整数型を渡すと実行時エラーになる。

public class Main {
	public static void main(String[] args) {
		DecimalFormat df = new DecimalFormat("0.00000");
		System.out.println(df.format(Math.PI*10));
		System.out.printf("%.5f\n",Math.PI*10);

		BigDecimal x = BigDecimal.ONE.divide(new BigDecimal("13"), 40, RoundingMode.HALF_EVEN);
		DecimalFormat df2 = new DecimalFormat("0.000000000000000000000000000000");
		System.out.println(df2.format(x));
		System.out.printf("%.30f\n",x);
	}
}

出力

31.41593
31.41593
0.076923076923076923076923076923
0.076923076923076923076923076923

###doubleの高速なフォーマット
uwiさんのコメントを参考に追記しました。
doubleを大量に出力する必要がある場合、printfは遅い。
printfよりもDecimalFormatの方がやや速く、自前でフォーマットを行えばさらに高速化できる。

ベンチマーク
ファイルにPrintWriterを用いてMath.random() * Math.pow(10, Math.random() * 7)で生成したdoubleを$10^7$行出力してみた。
dtosはuwiさんのコメントのソースコードの関数を使用したもの。

	実行時間/行数(ns)
printf	1683
DecimalFormat	907
dtos	325

printfとdtosは$10^6$行出力したとすると1360ms分差がつくという結果になった。入力と同様、行数が$10^5$を超えるあたりから気にしたほうがよさそう。

##指数を使わない表記で出力
doubleやBigDecimalを使う場合に値が大きくなりすぎるか小さくなりすぎると、1.0E16のような表記にされてしまう場合がある。
小数点以下の桁数を指定するか、BigDecimalの場合はtoPlainStringも使える。

public class Main {
	public static void main(String[] args) {
        BigDecimal x = BigDecimal.ONE.divide(new BigDecimal("13"), 40, RoundingMode.HALF_EVEN);
        x = x.scaleByPowerOfTen(-10);
        System.out.println(x);
        System.out.printf("%.20f\n",x);
        System.out.println(x.toPlainString());

        double y = Math.PI * Math.pow(10, 10);
        System.out.println(y);
        System.out.printf("%.10f\n",y);
	}
}

出力

7.69230769230769230769230769230769230769E-12
0.00000000000769230769
0.00000000000769230769230769230769230769230769230769
3.141592653589793E10
31415926535.8979300000

#スタックオーバーフロー
よくある環境では、再帰の深さが数万くらいになるとスタックオーバーフローで落ちる。
C++に比べるとスタックオーバーフローしやすいので注意が必要。

public class Main {
	public static void main(String[] args) {
		System.out.println(recursive(30000)); //(自分の環境では)スタックオーバーフロー
	}
	static int recursive(int n) {
		if (n == 0) {
			return n;
		}else{
			return recursive(n-1) + 1;
		}
	}
}

##スタックの拡張
スレッドのデフォルトのスタックサイズはJVMのオプションによって決まり、これを設定していない場合は環境ごとのデフォルト値が用いられる。(320KB~1024KB)
スタックを拡張したい場合、スタックサイズを指定してスレッドを作る。

//Runnableを実装する
public class Main implements Runnable {
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start(); //16MBスタックを確保して実行
    }
    public void run() {
        //ここに処理を書く
    }
}

##再帰呼び出しの除去
スタックの拡張が出来ない場合やメモリ制限が厳しい場合、再帰を使わない解法を考える。全探索をする必要があり、深さ優先探索でも幅優先探索でもどちらでも良い場合は、Queueを使って簡単に再帰なしで書ける幅優先探索を使う。(How many Islands? のサイズを大きくしたような問題など)
構文解析の問題だと再帰を書きたくなるが、Shipuraがサイズが大きくてJavaだと再帰が書けずつらくなった。ArrayDequeをスタックとして利用して、再帰呼び出しではなく繰り返しで書くようにする。

#MLEの回避

データをなんとか小さくする

• int[1000000][2]よりint[2][1000000]の方が消費メモリが少ない。(後者の方が配列の数が少ない)
• dpテーブルでint[][]をbyte[][]に直したらMLEを回避できたことがあった。
• $0 \leq x,y < 100 (x,yは整数)$を$z = 100x + y$のように一つのintにまとめるテク。
• 配列の一部のインデックスしか意味のある値を持たない場合(疎な時)は、HashMapを用いるとメモリを節約できることがある。

配列などを使いまわす

入力に複数のテストケースが含まれている場合など、配列を何度も生成したくなる場合がある。(AOJのICPC系の問題に多い)

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if (n == 0) break;
			int[] a = new int[n];
			for(int i=0;i<n;i++) {
				a[i] = sc.nextInt();
			}
			//メインの処理
		}
	}
}

配列をいちいちnewで確保するのはメモリの消費量を増やすので、予め確保しておく。処理時間も短くなる。
初期化したい場合はArrays.fillを用いる。

public class Main {
	public static final int MAX_N = 10000;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] a = new int[MAX_N];
		while(true) {
			int n = sc.nextInt();
			if (n == 0) break;
			for(int i=0;i<n;i++) {
				a[i] = sc.nextInt();
			}
			//メインの処理
		}
	}
}

ArrayListなどのCollectionの実装クラスの場合はclear()が使える。

##ガベージコレクタ(GC)を実行する
テストケースが複数ある場合に配列などを使いまわすのが面倒な場合は、GCを実行してメモリを解放してもらう。
System.gcを呼び出すことで、GCを実行することができる。

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			int[] a = new int[n];
			if (n == 0) break;
			for(int i=0;i<n;i++) {
				a[i] = sc.nextInt();
			}
			//メインの処理
			System.gc(); //1テストケースごとにメモリを解放
		}
	}
}

#色々な罠
##計算
Javaに限らない話を多く含む。
###負の数の割り算
結果が負になる整数の割り算をした場合、切り捨てられる方向は絶対値が小さくなる方である。
切り捨ても含めた計算式を考えてコードに落としこむときに間違えやすい。
doubleのintへのキャストでも同じように切り捨てが行われる。必要に応じてMath.floorなどを使う。

public class Main {
	public static void main(String[] args) {
		for(int i=-4;i<=4;i++) {
			System.out.println(i + " / 3 = " + (i/3));
		}
	}

}

出力

-4 / 3 = -1
-3 / 3 = -1
-2 / 3 = 0
-1 / 3 = 0
0 / 3 = 0
1 / 3 = 0
2 / 3 = 0
3 / 3 = 1
4 / 3 = 1

###ビットシフトの罠
ビットシフトのシフトする量は左辺がintだとmod32、longだとmod64が取られる。
このような動作を期待していなければ場合分けする必要がある。

public class Main {
	public static void main(String[] args) {
		for(int i=30;i<=33;i++) {
			System.out.println(1<<i);
		}
	}
}

出力

1073741824
-2147483648
1
2

また、左辺がintで右辺がlongの時、結果はintになるので注意。(他の二項演算子と異なる)

public class Main {
	public static void main(String[] args) {
		System.out.println(1  << 33L);
		System.out.println(1L << 33 );
		System.out.println(1L << 33L);
	}
}

出力

2
8589934592
8589934592

###longからdoubleへの変換
longからdoubleへのキャストは暗黙的に行えるが、longはdoubleの仮数部に収まらないので誤差が発生する。
CODE FESTIVALのあさプロでこれをやらかした。

###BigDecimalのオーバーフロー
BigDecimalの指数部はint型なので指数がオーバーフローすると例外が発生する。これもあさプロの同じ問題でやらかした。

##比較
プリミティブ型以外に対して==演算子による比較をすると参照の比較になるので、

public class Main {
	public static void main(String[] args) {
		String a = new String("abc");
		String b = new String("abc");
		System.out.println(a == b);
	}
}

はfalseになる。

StringやBigIntegerの比較にはequals(Object o)を用いる。
大小関係がある場合にはcompareTo(Object o)も使える。
自前のオブジェクトでこれらの比較をしたい場合には、自分でメソッドをオーバーライドする必要がある。

public class Main {
	public static void main(String[] args) {
		String a = new String("hoge");
		String b = new String("hoge");
		String c = new String("poyo");
		System.out.println(a.equals(b));
		System.out.println(b.equals(c));
		System.out.println(b.compareTo(c) < 0 ? b : c); //辞書順で小さい方を出力
	}
}

出力

true
false
hoge

##ソート
プリミティブ型(小文字で始まる型)の配列のソートをArrays.sort()ですると、最悪計算量が$O(n^2)$になる。
これはプリミティブ型の配列をソートする際のアルゴリズムがクイックソート(の改良版)であるためであって、ほとんどの場合は問題にならない。
ただし、作問側が意地悪な場合や、参加者がテストケースを作れるTopcoderやCodeforcesでは狙われる可能性がある。
対策としては、ソート前にシャッフルするか、ラッパ型の配列でソートする方法がある。
Java6とJava7,8ではクイックソートのアルゴリズムが異なるので、攻撃方法も違うらしい。
参考:http://codeforces.com/blog/entry/4827 , http://codeforces.com/blog/entry/7108

#競技でよく使う標準ライブラリ
詳しい情報はクラス名でググると日本語化されたJava6のドキュメントが出てくる。
##データ構造
検索や削除は必要か、重複は許されるか、順序は保たれる必要があるか、などから問題に応じて適切なデータ構造を使わないとWAやTLEになる。
標準ライブラリには使えるデータ構造がたくさんある。
参考(Collectionsに対する操作の計算量)：http://infotechgems.blogspot.jp/2011/11/java-collections-performance-time.html
###配列操作
Arraysに配列操作の様々なメソッドがある。
Arrays.sort()は配列の要素を昇順にソートする。オブジェクトのソートをする場合は匿名関数を使うと楽。ジャッジがJava8に対応していればラムダ式も書ける。

public class Main {
	public static void main(String[] args) {
		Pair[] a = {new Pair(0,5),new Pair(1,10),new Pair(2,3)};
		Arrays.sort(a, new Comparator<Pair>() {
			public int compare(Pair o1, Pair o2) {
				return Integer.compare(o1.b, o2.b); //Java7以降
			}
		});
	}
	static class Pair {
		int a,b;
		public Pair(int a,int b) {
			this.a = a;
			this.b = b;
		}
	}
}

Arrays.binarySearchはソート済の配列に対して二分探索をする。C++でいうlower_boundやupper_boundはない。一致する値が見つからなかった場合の返り値は負の値になる。同じ値が複数ある場合は結果の保証がないので使い勝手は良くない。

他によく用いるのはある要素で配列を埋めるArrays.fill、配列のディープコピーをするArrays.copyOf、デバッグに便利なArrays.toString、Arrays.deepToStringがある。配列の中身に対応したハッシュが必要な場合にArrays.hashcodeを使うこともあるかもしれない。

###ArrayList
可変長の配列が必要になったらこれでいい。ランダムアクセスと要素の追加が定数時間でできる。C++のvectorに対応する。vectorのpush_backがaddと同じ。アクセスはC++と違い配列っぽくはできず、いちいちal.get(i)のように書かなければならない。要素の削除や小さいインデックスへの挿入はサイズに比例した時間がかかるので、あまりすることはない。(解法か使うべきデータ構造が間違っている)
ソートはCollections.sort()でできる。

###ArrayDeque
双方向キュー。`Stack'は非推奨クラスなので、スタックが必要な場合もこれを用いる。先頭と末尾への要素の追加と取り出しが定数時間でできる。

###PriorityQueue
優先度つきキュー。要素の追加と、最小の要素の取り出しが$O ({\rm log}(n))$でできる。C++のPriorityQueueと違い、小さい要素から出てくるので、C++のコードを読むときは注意がいる。大きい要素から取り出す優先度つきキューを作りたいときは、PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());のようにする。
PriorityQueueの内部的な構造は二分木ではあるものの二分探索木ではないので、containsやremoveはサイズに比例した時間がかかる。

###HashSet
Setは重複した要素が含まれないデータ構造。HashSetは理想的には要素の追加、検索、削除が定数時間でできるが、順序は保たれない。
HashSetにオブジェクトを入れるときは、equalsとhashCodeを規約に沿って定義しないと、思った動作をしてくれない。

###TreeSet
TreeSetは順序付けされたSet。要素の追加、検索、削除、次に大きい/小さい要素の取り出し、などが$O ({\rm log}(n))$でできる。定数倍はやや重い。

###HashMap
Mapはキーと値の組からなるEntryの集まり。put(K key, V value)でエントリーを追加し、'get(Object key)'でキーに対応する値を取得する。キーが含まれているかはcontainsKey(Object key)で判定する。すべてのエントリーが必要な場合は'EntrySet()'を使う。
HashSetと同様、キーはequalsとhashCodeが正しく実装されている必要がある。

##計算
###Integer,Long
整数に関するすこし複雑な演算をするメソッドがある。
バイナリ表現での1の数を数えるInteger.bitCount(int i)や、バイナリ表現での最下位の1に続く0の数を数えるInteger.numberOfTrailingZeros(int i)が2進数絡みの問題で役に立つことがある。

###BigInteger
longで収まらないような大きな整数を扱う場合に用いる。また、競技プログラミングに多いmodを取らせる問題を解くときに便利な関数がいくつもある。
modInverse(BigInteger m)は${\rm mod} ; m$での逆元を求める。modPow(BigInteger exponent, BigInteger m)は累乗のmodを求めてくれる。
nextProbablePrime()はそのBigIntegerよりも大きい素数を(ほぼ確実に)返す。チャレンジケースを作ったり適当な素数を用意するのに便利。(Wolfram alphaでnext/previous prime of 10^18 のように聞くという手もある。)

###BigDecimal
doubleより範囲の広い・精度のよい実数型が必要な時に使える。BigDecimalはプリミティブ型のdoubleと違い例外がうるさいので少し注意がいる。またInfinityやNaNも存在しない。
丸めは基本的にされず、正確な演算結果が得られる。正確でなくて良い場合は、適当に丸めを行って桁数を減らし、計算量を抑えられる。
割り算は、ゼロ除算で例外になるほかに、丸めを指定しないと割り切れない時に例外が投げられる。

各演算のメソッドのドキュメントには書かれていなかったが、指数部がintの範囲を超えるとオーバーフロー/アンダーフローとして例外が発生する。powなどで値が非常に大きく/小さくなる場合は適度に切り捨てるなど特別な処理が必要になる。

#エディタ
Javaの定番エディタであるEclipseがオススメ。TopCoderに参加するならEclipseCoderというプラグインがあり、かなり使える。
Eclipseの便利コマンドの参考:http://d.hatena.ne.jp/nanikaka/20121224/1356280771