競技プログラミング in Scala
素人なのであてにはならないと思いますが。
[Scala]競技プログラミング in Scala
Scalaで競技プログラミングを行う際に気をつけることの列挙。
なぜScalaなのか?
プログラム全体の構造
Scalaプログラムの実行方法には二通りある。
注意すべきは、どちらの方法をとるかで書くべきプログラムが変わることである。scalaコマンドで直接実行する場合、トップレベルに書かれた式が実行される。scalacコマンドでコンパイルする場合、トップレベルには定義しかかけない。つまり、クラスを作らなければならない。コードは次のようになる。
object A extends Application{ ... hoge hoge }
直接実行する場合、クラスを定義しただけでは実行されないので、これとは逆にクラスを定義してはいけない。
書くべきコードはコンパイルする場合のほうが多い。また、実行させるのに必要なコマンドも長くなる(さらに悪いことに、コンパイルした場合、ラムダ式に応じて匿名の.classファイルが大量に生成される傾向にある)。あえてコンパイルする理由があるとすれば実行速度だろう。しかし、私の見たところによると、コンパイルして実行速度が速くなるということはなかった。直接実行する場合も内部的にはきっちりコンパイルして実行しているようだ(たぶんそうなので、直接実行する場合にもscalacする場合と同じぐらい起動に時間がかかる)。このことを鑑みるに、競技プログラミングであえてscalacを行う理由はない。プログラムはトップレベルに書き、scalaコマンドで実行するのが良い。
入出力
典型的な競技プログラミングの課題は標準入力からテストセットを入力し、結果を標準出力に書き出す必要がある。Scalaで入力をするにはいくつかの方法がある。
一つ目の方法は旧来の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
などがある。たくさんあるが、
-
- 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がある。
なぜか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になって、要素がつぶれてしまうことがあるので注意。