概要
http://codeforces.com/contest/450/problem/A
をScalaで解いてみた。
競プロのリハビリ兼Scalaが競プロでどう使えるのかの検証その1です。
問題
n人の子供が並んでいる（1..nの番号付き）。
それぞれ、少なくともa[i]個のキャンディを受け取るまで帰らない。
Jzzhuさんは先頭の子からm個ずつキャンディを与える。
m個もらった子iは、もらった数の合計がa[i]を上回れば列から消え、まだなら列の最後に並ぶ。
最後に列に残った子は何番？
1 \leq n \leq 100
アルゴリズム
子供の列をListで表し、実装するだけ。
nが小さいので何しても大丈夫。
良心的なA問題。
Scala的には
列の最後に追加、というList的に不吉な文言が。
念のため、末尾に追加演算子（:+）を使わずreverseしてみた。
両方コドフォサーバーで試したところ、実行速度に差はほぼなし。
100程度なら何やっても大丈夫そう。
詳しい検証は速度が厳しい問題が出てからにしよう…。
こういうケース、うまく書けば再帰使わないで行けるんかな…？
末尾に増える時点でmapじゃ書けなさそうだし、あんまりいい方法が浮かばない。
なお、テストをしやすいように、solve関数にまとめた。
解答
import scala.annotation.tailrec
object Main extends App {
val sc = new java.util.Scanner(System.in)
val n,m = sc.nextInt
val input = List.fill(n)(sc.nextInt)
def solve( m: Int, input: List[Int] ): Int = {
@tailrec
def dist(children: List[(Int, Int)] ): Int = {
children match {
case List(x) => // size == 1
x._2 + 1
case x :: xs =>
val diff = x._1 - m
if (diff <= 0)
dist(xs)
else
dist( ( (diff, x._2) :: xs.reverse ).reverse )
}
}
dist( input.zipWithIndex )
}
println( solve( m, input ) )
}
自分で書いたテストケース
import org.scalatest._
class Test extends FlatSpec with Matchers {
it should "test 1" in {
val input = List(1, 3, 1, 4, 2)
Main.solve(2, input) should be (4)
}
it should "test 2" in {
val input = List(1, 1, 2, 2, 3, 3)
Main.solve(4, input) should be (6)
}
it should "test 3" in {
val input = List(6, 1, 5, 4, 2, 3, 1)
Main.solve(3, input) should be (4)
}
}
結果
Time: 249 ms
Memory: 100 KB
Scala見たことない人へのちょっとした解説
List[Int]
IntのList。いわゆる単方向リスト。
特定の要素に行くには先頭から辿らないと行けないので、末尾に追加とかは厄介。
その代わり、先頭に追加、とか先頭を順に取り出し、とかは速い。List[(Int,Int)]
Intを2つ持つタプルのList。タプルを書くのは簡単。便利。@tailrec
末尾再帰をしてね、ってお願いするアノテーション。
末尾再帰な関数は、whileに展開されてスタックを食いつぶさなくなる、らしい。
心休まるアノテーション。match - case
C言語のそれと比べてはいけないレベルで強力。
数字、文字列のみならず、型やリストでもマッチでき、ガード条件も付けられる。;
省略可能。1行に処理を並べたい時は必要。return
省略可能。ブロックの最後に書いたのがreturn値になる。便利。
ブロックを使って変数を複雑な初期化とかすると綺麗&&便利。
val t = {
val u = a+b
u*v
}
- reverse 要素の順番をひっくり返した配列を返す。 「reverse」→「先頭に要素追加」→「reverse」であら不思議、末尾に要素が追加できちゃう。 Listの末尾に追加するコストを気にしなければ、 List() :+ elem で末尾に追加できる演算子が用意されている。