• 7
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

ScalaでAOJ

この記事は Competitive Programming (その2) Advent Calendar 2015 の10日目の記事です。

私はScalaも競技プログラミングも初心者なので、厳密ではない言い回しや間違いがあるかもしれません。何かあればご指摘ください。

概要

AOJにScalaを含む3つの関数型言語が追加されたので、Scalaに入門しつつ問題を解いた時のことを書いた。

advent1.png

読む

15分でざっくり分かるScala入門
Scalaに入門してみた その最後
Scalaで競技プログラミング(入出力編)
競技プログラミングにおけるScalaの標準入力を楽にする

解く

Hello World

object Main {
  def main(args: Array[String]): Unit = {
    println("Hello World")
  }
}

10001: X Cubic

import scala.io.StdIn._

object Main{
  def main(args: Array[String]): Unit = {
      val x = readInt
      println(x*x*x)
  }
}

Reversing Numbers

split( ) 与えられた文字たちを区切り文字として分割してくれる。
map( ) リストの各要素に関数を適用する

例えば、

1 2 3 4 5

みたいな文字列をreadLineで読むと"1 2 3 4 5"という文字列になる。
よって、

readLine.split(" ")

とすると

Array("1","2","3","4","5")

という結果になる。この各要素に、map関数でtoIntを適用すると

readLine.split(" ").map(_.toInt)

というコードが出来上がる。後はこれをreverseしてmkStringしてsubmit。

import scala.io.StdIn.readLine

object Main {
  def main(args: Array[String]): Unit = {
    readLine
    println(readLine.split(" ").map(_.toInt).reverse.mkString(" "))
  }
}

Binary Search

import scala.io.StdIn._
import scala.annotation.tailrec

object Main {
  @tailrec
  def binarySearch(f: Int => Int, l: Int, r: Int): Int = {
    if(r-l<=1)f(l)
    else if(f((l+r)/2) < 1)binarySearch(f,(l+r)/2,r)
    else binarySearch(f,l,(l+r)/2)
  }

  def main(args: Array[String]): Unit = {
    val n = readInt
    val list = readLine.split(" ").map(_.toInt)

    val f = (ar: Seq[Int], a: Int) => (x: Int) => ar(x)-a

    val q = readInt
    val qlist = readLine.split(" ").map(_.toInt)
    val res = for(e <- qlist)yield binarySearch(f(list,e),0,n)
    println(res.count(_ == 0))
  }
}

binarySearch関数をInt => Int型の関数を引数でもらう実装にしておく。
main関数で
f(ソート済みリスト、探す)(二分探索時の添字):次どっちか(-1,0,1)
みたいな関数を作って、binarySearch関数に渡す時には添字渡すだけの形にしておくと良いのかなあと思った。

Range Minimum Query

Monoidトレイトを作っておいて、セグ木の中ではMonoidトレイトに定義されたopとzeroを使って実装しておくとrange minimum queryやrange sum queryにも、セグ木作る時にMonoid作って渡すだけになるので良いのかなあと思った。

object Main {
  trait Monoid[A]{
    def op(a1: A, a2: A): A
    def zero: A
  }

  class SegmentTree[A](val numOfNode: Int, val M: Monoid[A]){

    sealed trait Tree{ val value: A }
    case object Leaf extends Tree{ val value: A = M.zero }
    case class Node(value: A, left: Tree, right: Tree) extends Tree
    object Node {
        def apply(value: A) = new Node(value, Leaf, Leaf)
        def apply(l: Tree, r: Tree) = new Node(M.op(l.value,r.value),l,r)
    }

    private[this] val empty: Node = Node(M.zero,Leaf,Leaf)
    private[this] var root: Tree = empty

    private def updateRec(id: Int, x:A, l: Int = 0, r: Int = numOfNode, t: Tree = root): Tree = {
        def branch(now: Node): Node = {
            val m = (l + r)>>1
            if(r-l<=1)Node(x)
            else if(id < m)Node(updateRec(id,x,l,m, now.left), now.right)
            else Node(now.left,updateRec(id,x,m,r,now.right))
        }
        t match {
            case now: Node => branch(now)
            case _ => branch(empty)
        }
    }

    def update(id: Int, x: A): Unit = {
        root = updateRec(id, x)
    }

    def query(a: Int, b: Int, l: Int = 0, r: Int = numOfNode, t: Tree = root): A = {
      val m = (l + r)/2
      t match {
        case now: Node =>
          if(b<=l || r<=a)M.zero
          else if(a<=l && r<=b)now.value
          else M.op(query(a,b,l,m,now.left),query(a,b,m,r,now.right))
        case _ => M.zero
      }
    }
  }

  def main(args: Array[String]): Unit = {
    val line = scala.io.StdIn.readLine.split(" ").map(_.toInt)
    val n = line(0)
    val q = line(1)
    val m = new Monoid[Int]{
        def op(a1: Int, a2: Int): Int = a1 min a2
        def zero: Int = Int.MaxValue
    }

    val segtree = new SegmentTree[Int](n,m)

    for(i <- 1 to q){
        val input = scala.io.StdIn.readLine.split(" ").map(_.toInt)
        val x = input(1)
        val y = input(2)
        if(input(0)==0)segtree.update(x,y)
        else println(segtree.query(x,y+1))
    }
  }
}

まとめ

Scalaを使ってAOJの問題を解いてみようと思った理由は2つあって、
1.普段と違う言語を使うのが面白そうだった
2.より汎用的(?)な競技プログラミング用ライブラリを作れそうに思えた

参考資料にもあげたけど標準入力もそうだし、「競技プログラミングにおいて」どんな実装が良いのか、「こういうアルゴリズムの時はこうする」みたいなイメージがまだ掴めていない。