始めに
今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。
勉強途中であることもあり、より良い書き方とかあれば是非是非コメントにアドバイスお願いします！
問題はこちら
解答
再帰関数でTLEにとっても悩まされた...末尾再帰で書ければもう少し早くなったのかもしれないが、どうやればいいかわからなかった。
さらに、再帰の中で PartialFunction を呼び出していると TLE になって、PartialFunction を回避するだけで1秒近く早くなる事象に遭遇した。確かに部分関数値を生成しているのでそのコストはかかるだろうけど、こんなにかかるのか？と疑問に思った。特にコップ本などに言及はなかったので、もう少し調べてみたい。
変更前：Submission #17676971 - AtCoder Typical Contest 001
変更後：Submission #17677294 - AtCoder Typical Contest 001
他には、初心者なのでArray型の初期化方法をこちらを見て知った。
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() }
