Java 高速化テクニック

Java で競プロをするにあたって、プログラムの実行時間をより高速にするために一般的に使用されているテクニックをまとめてみました。

入出力の高速化

Java には Scanner や System.out がある。

こいつらは言語標準的な顔をしているが、遅い。

Scanner を高速化する

手っ取り早い方法として、

code:java

int n = sc.nextInt();

を

code:java

int n = Integer.parseInt(sc.next());

に置き換える、というものがある。これだけでも普通にやるよりある程度高速にはなる。

だが、これでもかなり遅いので、上位勢の方々は大抵FastScannerというものを自作して毎度貼り付けている。

ジャッジ内にFastScanner.classが出来る気がするが、問題ないっぽい。

出力を高速化する

C++などの例に漏れず、Java も出力の度に頻繁に flush がかかってしまう。

自前で PrintWriter を宣言してそれを出力に使うのが高速でよい。

code:java

PrintWriter out = new PrintWriter(System.out);

これをしているユーザはあまり見かけないが、$ 3 \times 10^5行の出力で$ 1000ms改善したことがあるのでやらない手はないだろう。

ただし

code:java

out.flush();

としてから終了する必要がある(多分)ので注意されたい。