ひらめの日常

日常のメモをつらつらと

Scalaで競技プログラミング: ATC001-A 深さ優先探索

始めに

今までC++競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。
勉強途中であることもあり、より良い書き方とかあれば是非是非コメントにアドバイスお願いします!

問題はこちら

atcoder.jp

解答

再帰関数でTLEにとっても悩まされた...末尾再帰で書ければもう少し早くなったのかもしれないが、どうやればいいかわからなかった。

さらに、再帰の中で PartialFunction を呼び出していると TLE になって、PartialFunction を回避するだけで1秒近く早くなる事象に遭遇した。確かに部分関数値を生成しているのでそのコストはかかるだろうけど、こんなにかかるのか?と疑問に思った。特にコップ本などに言及はなかったので、もう少し調べてみたい。
変更前:Submission #17676971 - AtCoder Typical Contest 001
変更後:Submission #17677294 - AtCoder Typical Contest 001

他には、初心者なのでArray型の初期化方法をこちらを見て知った。

qiita.com

val a = Array.fill(n)(sc.nextInt) // n要素標準入力で受け取る
val a = Array.ofDim[Int](3, 3) // 3*3の二次元配列

最終的な解答はこちら。

import java.io.PrintWriter
import java.util.Scanner

object Main extends App {
  val pw = new PrintWriter(System.out)
  val sc = new Scanner(System.in)

  val h, w = sc.nextInt()
  val c = Array.fill(h)(sc.next())
  val seen = Array.ofDim[Boolean](h, w)
  val s = for {
    i <- 0 until h
    j <- 0 until w
    if c(i)(j) == 's'
  } yield (i, j)
  
  val dis = Array(1, 0, -1, 0)
  val djs = Array(0, 1, 0, -1)

  def dfs(i: Int, j: Int): Boolean = {
    var ret = false
    (0 until 4).foreach { idx =>
      val ni = i + dis(idx)
      val nj = j + djs(idx)
      if (0 <= ni && ni <= h - 1 && 0 <= nj && nj <= w - 1 && !seen(ni)(nj)) {
        seen(ni)(nj) = true
        if (c(ni)(nj) == '.') ret = ret || dfs(ni, nj)
        else if (c(ni)(nj) == 'g') ret = true
      }
    }
    ret
  }

  val (si, sj) = s.head
  seen(si)(sj) = true
  val ans = if (dfs(si, sj)) "Yes" else "No"
  pw.println(ans)
  pw.flush()
}

Submission #17677400 - AtCoder Typical Contest 001