読者です 読者をやめる 読者になる 読者になる

LoL/LJL好きのエンジニアのブログ

技術的な話やら、最近はLoLやLJLの話など。

ABC #024 C - 民族大移動 をScalaの再帰で解いてみた

はじめに

B問題を再帰で解こうとしたらREで無理でした。(参考: http://abc024.contest.atcoder.jp/submissions/415693)では、Cなら行けるのではなかろうか、だって再帰の深さ1000程度だし。105 と比べたらだいぶ小さいし。

というわけで書きました。

ソースコード

if式の部分がちょっと汚いですが許してください

import java.util.Scanner
 
object Main {
  val sc = new Scanner(System.in)
 
  def main(args: Array[String]): Unit = {
    val n, d, k = sc.nextInt()
    val list = for(i <- 1 to d) yield (sc.nextInt(), sc.nextInt())
    
    for(i <- 1 to k)
      println(solve(sc.nextInt(), sc.nextInt(), list.toList))
  }
  
  def solve(s: Int, t: Int, list: List[(Int, Int)]): Int = list match {
    case Nil => return 0
    case (l, r) :: cdr => {
      if(l <= s && s <= r){
        // 範囲に入っている場合
        if(l <= t && t <= r){
          // もうゴールしてもいいよね
          1
        }else if(t < s){
          // 左まで行く
          1 + solve(l, t, cdr)
        }else{
          // 右まで行く
          1 + solve(r, t, cdr)
        }
      }else{
        // 範囲に入っていない場合
        1 + solve(s, t, cdr)
      }
    }
  }
}

結果

http://abc024.contest.atcoder.jp/submissions/415480

50ちょいあるテストケースのうち10くらいでRE、それ以外はAC。*1

f:id:yoshiki_utakata:20150524160550p:plain

何故だ… Scalaはforより再帰のほうが良いと思ったのに。仕方ないのでコンテストの時はよほど小さい問題でなければ var を使うしかないですかね…。 だったらもはやScala使わない方がいいのではないだろうか。

Pythonでは再帰のlimitを解放する方法があったけど、Scalaはないのかしら… もしかしたらジャッジサーバー側の設定だったりする?

*1:画面に写っていないところでも1箇所だけREが出ています