yu/logs/*

技術メモ など

AtCoder ABC294 D 解法メモ KotlinでTLEせずに10^6くらいの出力をしたい(出力の高速化)

単純なprintだとTLEするケースに初めて遭遇したのでメモ

解いていた問題

atcoder.jp

解法メモ

  • 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以下に
  • もう少しだけ大き目に106をPrintWriter経由で
    • 229 ms
      • 実行時間制限に問題なさそうな時間で出力できていそう?

提出した回答

参考