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

#はじめに

この記事の内容を書きなおして、
「[Javaで競技プログラミングをするときの罠とテク](http://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4)」
「[Javaで競技プログラミングをするときによく使う標準ライブラリ](http://qiita.com/p_shiki37/items/3902f4e3adc3aeb382f1)」
という2つの記事にしました。
全体的に見直しをしたのでこちらを見ることをオススメします。

****

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

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

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

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

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

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

```java
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`を使う。

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

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

代わりに`StringBuilder`を使う。

```java
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`に出力を一度固める方法はメモリを多く使うという指摘がありました)

```java
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に対して引数に整数型を渡すと実行時エラーになる。

```java
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);
	}
}
```

```text:出力
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`も使える。

```java
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);
	}
}
```

```text:出力
7.69230769230769230769230769230769230769E-12
0.00000000000769230769
0.00000000000769230769230769230769230769230769230769
3.141592653589793E10
31415926535.8979300000
```

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

```java
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)
スタックを拡張したい場合、スタックサイズを指定してスレッドを作る。

```java
//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?](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160) のサイズを大きくしたような問題など)
構文解析の問題だと再帰を書きたくなるが、[Shipura](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2570)がサイズが大きくて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系の問題に多い)

```java
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`を用いる。

```java
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を実行することができる。

```java
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`などを使う。

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

}
```

```text:出力
-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が取られる。
このような動作を期待していなければ場合分けする必要がある。

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

```text:出力
1073741824
-2147483648
1
2
```

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

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

```text:出力
2
8589934592
8589934592
```


###longからdoubleへの変換
longからdoubleへのキャストは暗黙的に行えるが、longはdoubleの仮数部に収まらないので誤差が発生する。
CODE FESTIVALの[あさプロ](http://code-festival-2014-morning-hard.contest.atcoder.jp/tasks/code_festival_morning_med_c)でこれをやらかした。

###BigDecimalのオーバーフロー
`BigDecimal`の指数部はint型なので指数がオーバーフローすると例外が発生する。これも[あさプロの同じ問題](http://code-festival-2014-morning-hard.contest.atcoder.jp/tasks/code_festival_morning_med_c)でやらかした。

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

```java
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)`も使える。
自前のオブジェクトでこれらの比較をしたい場合には、自分でメソッドをオーバーライドする必要がある。

```java
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); //辞書順で小さい方を出力
	}
}
```

```text:出力
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に対応していればラムダ式も書ける。

```java
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](http://fornwall.net/eclipsecoder/)というプラグインがあり、かなり使える。
Eclipseの便利コマンドの参考:http://d.hatena.ne.jp/nanikaka/20121224/1356280771