[Scala]競技プログラミング in Scala

Scala競技プログラミングを行う際に気をつけることの列挙。

なぜScalaなのか?

  • 速い
  • 静的型付
  • 字面がC++よりましなのでC++よりは速く書けるであろうという期待
  • 同じ理由でJavaよりは速く書けるであろうという期待
  • OCamlよりも基本的なライブラリが充実しているので速く書けるであろうという期待
  • Haskelは配列を弄繰り回すような場合にコードが冗長になる傾向があるのでそういう場合に比較して速く書けるであろうという期待

プログラム全体の構造

Scalaプログラムの実行方法には二通りある。

  • scalaコマンドによる直接実行
  • scalac(fsc)コマンドで.classファイルを生成 → scalaコマンドで.classファイルを指定して実行

注意すべきは、どちらの方法をとるかで書くべきプログラムが変わることである。scalaコマンドで直接実行する場合、トップレベルに書かれた式が実行される。scalacコマンドでコンパイルする場合、トップレベルには定義しかかけない。つまり、クラスを作らなければならない。コードは次のようになる。

object A extends Application{
  ... hoge hoge
}

直接実行する場合、クラスを定義しただけでは実行されないので、これとは逆にクラスを定義してはいけない。

書くべきコードはコンパイルする場合のほうが多い。また、実行させるのに必要なコマンドも長くなる(さらに悪いことに、コンパイルした場合、ラムダ式に応じて匿名の.classファイルが大量に生成される傾向にある)。あえてコンパイルする理由があるとすれば実行速度だろう。しかし、私の見たところによると、コンパイルして実行速度が速くなるということはなかった。直接実行する場合も内部的にはきっちりコンパイルして実行しているようだ(たぶんそうなので、直接実行する場合にもscalacする場合と同じぐらい起動に時間がかかる)。このことを鑑みるに、競技プログラミングであえてscalacを行う理由はない。プログラムはトップレベルに書き、scalaコマンドで実行するのが良い。

入出力

典型的な競技プログラミングの課題は標準入力からテストセットを入力し、結果を標準出力に書き出す必要がある。Scalaで入力をするにはいくつかの方法がある。

  • java.io.以下のBufferedReaderなどを使う
  • scala.io.Sourceを使う
  • java.util.Scannerを使う

一つ目の方法は旧来のJavaで一般的な方法だが、冗長に過ぎる。scala.io.Sourceはインターフェースが使いにくい。Java1.5以上であればScannerを使うのがよろしい。

出力はSystem.outを使う方法と、scalaの標準ライブラリを使う方法がある。前者は、単にSystem.out.とタイプするのが面倒なこと(これはimportすればよいのだが)に加え、JavaのクラスであるObjectを引数をとる関数にはscalaの暗黙の型変換がうまく働かないという問題がある。

System.out.printf("%d\n", 123) // NG
System.out.printf("%d\n", int2Integer(123)) // OK

この理由から、scala組み込みのを使うべきである。

printf("%d\n", 123) // OK

なお、scalaのprint/printlnには任意個の引き数が渡せて、その場合にはタプルの出力と同じになるので、デバッグに便利である。

データ構造

  • 配列

newでの生成は初期値が指定できない上に要素の型を指定しなくてはならず大変使いにくい。コンパニオンオブジェクトのfromFunctionが便利。

val aa = Array(1, 2, 3) // リテラル
val bb = Array.fromFunction(i=>...)(n) // 添え字で初期化できる
val cc = Array.fromFunction(_=> -1)(n) // 初期値が決まっているなら
val dd = Array.make(n, -1) // これでもいい
val ee = Array.fromFunction((i, j)=>...)(n, m) // 多次元配列も
val ff = Array.make(n, Array.make(m, -1)) // これはだめ
  • リスト

普通のリスト。

  • Map

の二つのtraitがある。前者は順序を保障しない。後者は保障する。実装しているクラスは次のとおり

    • scala.collection.immutable.HashMap extends Map
    • scala.collection.immutable.ListMap extends Map
    • scala.collection.immutable.TreeMap extends SortedMap
    • scala.collection.immutable.TreeHashMap extends Map
    • scala.collection.immutable.UnbalancedTreeMap extends Map
    • scala.collection.immutable.IntMap extends Map
    • scala.collection.immutable.LongMap extends Map
    • scala.collection.mutable.HashMap extends Map
    • scala.collection.mutable.LinkedHashMap extends Map
    • scala.collection.mutable.OpenHashMap extends Map

などがある。たくさんあるが、

    • immutable.ListMapと、immutable.UnbalancedTreeMapは存在価値が不明
    • immutable.TreeHashMapはHashMapでいい
    • mutable.LinkedHashMapとOpenHashMapはmutable.HashMapでいい

おおよそ次のような基準で選ぶと良い。

    • 順序付ならimmutable.TreeMap一択
    • キーが整数かつ非負で順序つきならimmutable.IntMap or LongMap
      • これらはunsignedに順序が付くようなので、非負の数しか入れないならSortedMapとして使える
      • HashMapよりは遅いがTreeMapよりはだいぶ速い
    • パフォーマンスが気になるならmutable.HashMap
    • それ以外ならimmutable.HashMap
      • (実際のところimmutable.HashMapは十分速い)

なお、scala.collection.immutable.Mapとmutable.Mapコンパニオンオブジェクトはそれぞれimmutable.HashMapとmutable.HashMapを生成する。

  • Set

mapと同様に順序付きとそうでないものの二つのtraitがある。

    • scala.collection.immutable.HashSet extends Set
    • scala.collection.immutable.ListSet extends Set
    • scala.collection.immutable.TreeSet extends SortedSet
    • scala.collection.mutable.HashSet extends Set
    • scala.collection.mutable.LinkedHashSet extends Set

なぜかmapよりもバリエーションが少ない。IntMap相当のものがないことを除けば、選定基準はMapと同じでいいだろう。

  • MultiMap

基本的にMap[A, Set[B] ]で扱う。便利のためにそのようなTraitがscala.collection.mutable.MultiMapに用意されている(なぜかmutableだけ)。

val x = new HashMap[Int, Set[Int] ] with MultiMap[Int, Int] // こうすると
x.add(1, 2)
x.add(1, 3)
x.entryExists(1, (_ = 2))
x.remove(1, 2) // こういうメソッドが使える

当然ながらimmutableにはくっつけられない。

キーも値も重複するものを許すものは用意されていない。

  • MultiSet

特に用意されているものはない。Map[A, Int] などで出現回数を数えるぐらいだろうか。

  • PriorityQueue

scala.collection.mutableにある。比較関数は変えられない。

小技

  • パラメータを複数個読み込む必要がある場合。
val sc = new java.util.Scanner(System.in)
val a, b, c = sc.nextInt() // a, b, c の順に整数が三つ読み込まれる
  • 整数の配列を読み込む場合
val arr = Array.fromFunction(_=>sc.readInt())(n) // arr(0) .. arr(n-1) に順に整数が読み込まれる
val mat = Array.fromFunction((_,_)=>sc.readInt())(n, m) // arr(0)(0) .. arr(0)(m-1) .. arr(n-1)(m-1) に順に整数が読み込まれる
  • 文字列を空白区切りで分割
val words = sc.nextLine() split " +"
  • ジェネレータは一回しか評価されない
for (caseno <- 1 to sc.nextInt()){
  ...
  printf("Case #%d: ...", caseno, ...)
}
  • パーザコンビネータが標準でついてるので、使えるようにしておくべし

気をつけること

型推論が弱いので、要所要所で型を書いてやる必要がある。書く必要がある場所の判定にはScala型推論アルゴリズムを熟知している必要があるので、Programming in Scalaには、コンパイラに怒られたらその都度注釈を入れよ、の様に書いてあった。しかし、いちいちそれでは時間をロスするので、注釈が必ず必要な簡単な場所は覚えておく。

    • 関数の引き数
    • 明示的にreturnしている関数の返り値の型
    • 再帰呼び出ししている関数の返り値の型
  • for式の型

for式でyieldすると、最初のジェネレータと同じ型のコレクションが返る。ListならList、ArrayならArrayであるが、SetだとSetになって、要素がつぶれてしまうことがあるので注意。