Scalaで競技プログラミングするためのTips
競プロ初心者作
気が向いたら更新していくつもり
入力
標準入力
標準ライブラリで提供されているものは遅いので自作したものを使います.
object Scanner { private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0 @inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126 @inline private def hasNextByte(): Boolean = if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else { true } @inline private def hasNext(): Boolean = { while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1 hasNextByte() } @inline private def readByte(): Byte = if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else { -1 } def next(): String = { if(!hasNext()) ??? val sb = new StringBuilder; var b = readByte() while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() } sb.toString } def nextInt(): Int = { val n = nextLong() if (n < Int.MinValue || Int.MaxValue < n) ??? n.toInt } def nextLong(): Long = { if(!hasNext()) ??? var minus = false; var b = readByte() if (b == '-') { minus = true; b = readByte() } def go (b: Byte, n: Long = 0): Long = if ('0' <= b && b <= '9') { go(readByte(), n * 10 + b - '0') } else if (minus) { -n } else { n } go(b) } def nextDouble(): Double = next.toDouble }
// - input - // 1 2 3 // --------- println(Scanner.nextInt()) // => 1
エラー処理はサボり気味.
初期化
少数
並べることでまとめて初期化できます.
// - input - // 1 2 3 // --------- val x, y, z = Scanner.nextInt() println(s"$x, $y, $z") // => 1, 2, 3
コレクション
fill
でまとめて初期化できます.
// - input - // 1 2 3 4 5 // --------- Array.fill(5)(Scanner.nextInt()) // [1, 2, 3, 4, 5]
多次元にも利用できます.
// - input - // 1 2 // 3 4 // 5 6 // --------- Array.fill(3, 2)(Scanner.nextInt()) // [[1, 2], [3, 4], [5, 6]]
しかしながら転置した形のコレクションが欲しいことが多いと思います. その場合は自作したものを使います.
object MyArray { def fillT[T : scala.reflect.ClassTag](dimX: Int, dimY: Int)(f: => T): Array[Array[T]] = { val arrs = Array.ofDim[T](dimX, dimY) for { y <- (0 until dimY) x <- (0 until dimX) } { arrs(x)(y) = f } arrs } }
// - input - // 1 2 // 3 4 // 5 6 // --------- MyArray.fillT(2, 3)(Scanner.nextInt()) // [[1, 3, 5], [2, 4, 6]]
出力
標準出力
出力の数が多い場合 (例えば O(n)
回出力するような場合) は println(Any)
は遅いので避けて, 代わりに java.io.PrintWriter(OutputStream)
を使います.
val pw = new java.io.PrintWriter(System.out) for (i <- 0 until 100000) pw.println(i) pw.flush()
フォーマット
Double
のフォーマットは遅いので自作したものを使います.
object MyFormat { def double(x: Double, precision: Int): String = { var num = x val sb = new StringBuilder if (num < 0) { sb.append("-") num = -num } num += Math.pow(10, -precision) / 2 sb.append(num.toLong) sb.append(".") num -= num.toLong (0 until precision).foreach(i => { num *= 10 sb.append(num.toInt) num -= num.toInt }) sb.toString } }
データ構造
適宜計算パターンに合わせて使い分ける必要があります. 殆どの場合Scala標準ライブラリが提供しているもので足りると思います (Segment Treeみたいな演算がDomain-Specificなものはないですが).
使用頻度が高そうなデータ構造
Array
Vector
(※ immutableのみ)List
(※ immutableのみ)ArrayBuffer
(※ mutableのみ)ListBuffer
(※ mutableのみ)HashSet
ListSet
TreeSet
BitSet
IntMap
・LongMap
HashMap
ListMap
TreeMap
MultiMap
(※ mutableのみ, トレイト)Stack
(※ immutableは代わりにList
を使う)Queue
PriorityQueue
(※ mutableのみ)
注意点
Seq
等のトレイトから初期化を行う際は, 内部的にそのデフォルト実装が利用される (例えばSeq
であればList
) ので, デフォルト実装の性能特性を意識する必要がある
Collections - 性能特性 - Scala Documentation- immutableなAPIはメモリを多く消費する傾向がある
ついでに前に作ったやつを貼っておく doc.co
アルゴリズム
ループ
単純なループに (0 until 10).foreach(...)
のような Range
を使うと不必要なオブジェクトが作られてしまうため若干ですが遅くなります. 時間にシビアな場合は while
で回すか以下のような関数を定義しておくと良いと思います.
@inline def rep(n: Int, f: => Unit): Unit = { var c = 0; while (c < n) { f; c += 1 } } @inline def rep(n: Int, f: Int => Unit): Unit = { var c = 0; while (c < n) { f(c); c += 1 } }
枝刈り
Scalaの構文には break
・continue
といったものがないため微妙に枝刈りのようなことがしづらいです. ライブラリレベルでは scala.util.control.Break
が提供されています.
val b = new scala.util.control.Breaks import b.{breakable,break} breakable { while (true) { ... if (...) break ... } }
書き方次第で「多重ループを任意段だけ抜ける」といったこともできます. continue
はないですが, ループの内側に breakable
を置くことで一応エミュレートできます.
val b0, b1 = new scala.util.control.Breaks b0.breakable { while (true) { ... if (...) b0.break b1.breakable { while (true) { if (...) b0.break else if (...) b1.break } } } }
val b = new scala.util.control.Breaks import b.{breakable,break} while (true) { breakable { ... if (...) break // break as continue ... } }
内部的には例外を投げていて精神衛生上よくない (ただし例外のコストはそこまで高くないらしい? (要検証))・ネストが深くなる・Breaks
インスタンスの管理が面倒, といった欠点が挙げられ, 代わりに再帰で書くという手もあります. SOFを避けるために末尾再帰化が必須という縛り付きですが. 他には takeWhile
等で頑張るという方法もあります. また, 1回breakしたらその時点で出力して終了するような場合は sys.exit
してしまうのも手です.
ソート
Scala標準ライブラリが提供している sorted
・sortWith
・sortBy
を使い分けます.
val list0 = List(1, 4, 3, 2) println(list0.sorted) // => [1, 2, 3, 4] println(list0.sortWith((a, b) => a > b)) // => [4, 3, 2, 1] val list1 = List(2 -> 4, 4 -> 2, 8 -> 2, 4 -> 1) println(list1.sorted) // => [(2,4), (4,1), (4,2), (8,2)] println(list1.sortBy(p => (p._2, p._1))) // => [(4,1), (4,2), (8,2), (2,4)]
二分探索
java.util.Arrays.binarySearch
を利用します.
val arr = Array(1, 2, 2, 3) val res0 = { val res = java.util.Arrays.binarySearch(arr, 0) if (res >= 0) res else ~res } println(res0) // => 0 val res2 = { val res = java.util.Arrays.binarySearch(arr, 2) if (res >= 0) res else ~res } println(res2) // => 1 val res4 = { val res = java.util.Arrays.binarySearch(arr, 4) if (res >= 0) res else ~res } println(res4) // => 3
その他コレクション操作
数が多いですが Scalaコレクションメソッドメモ(Hishidama's Scala collection method Memo) を使いこなせるようにしましょう. 大抵のことはできます. 基本的に正格評価されるということだけは頭の片隅においておきましょう.
その他
- クラス名に注意する必要があります.
object Main extends App
として定義しないといけないジャッジが多いようです.