競プロ初心者作

気が向いたら更新していくつもり

入力

標準入力

標準ライブラリで提供されているものは遅いので自作したものを使います.

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 として定義しないといけないジャッジが多いようです.

自作した部分をまとめたやつ

github.com

水底

ScalaとかC#とかk8sとか

Scalaで競技プログラミングするためのTips

入力