単純なprintだとTLEするケースに初めて遭遇したのでメモ
解いていた問題
解法メモ
- setとかを使って上手いこと状態を管理
- 私はバケットで解いてました
- (考察的な部分は解説参照ということで)
- そこまで遅い実装じゃない気がするのにTLEとなるケースがある
- 出力に時間が掛かっている・・・?
- 時間がかかっていたので、そこを考慮した実装にする
- 都度printせずに最後にまとめて出力する形にする
実装メモ
- ↓のような感じでPrintWriterを使用することで出力を高速化することができる
import java.io.PrintWriter fun main() { val pw = PrintWriter(System.out) for (i in 0 .. 1000000) { pw.println("1") } pw.flush() }
測定メモ
それぞれAtCoderのコードテストで確認
この問題で想定される、5 * 105を単純にprintした場合
- 1852 ms
- 5 * 105をPrintWriter経由でprintした場合
- 171 ms
- 1/10以下に
- 171 ms
- もう少しだけ大き目に106をPrintWriter経由で
- 229 ms
- 実行時間制限に問題なさそうな時間で出力できていそう?
- 229 ms