始めに
今までC++で競技プログラミングをしてきたのですが、業務でScalaを書いていることもあり、ScalaでAtCoderを解いてみようと思います。大半が解いたことある問題かつ、目的はScalaに慣れることなので、解説は省いています。
勉強途中であることもあり、より良い書き方とかあれば是非是非コメントにアドバイスお願いします!
問題はこちら
解答
C++で解いたときはbit全探索をしたが、今回パッと思いつかなかったので、再帰関数で実装した。各種類の参考書を購入するかしないかで分岐するようにして、全ての場合を調べる。
本来なら Array
の要素を書き換えるような方法で入力を受け取りたくないが、Scalaっぽく受け取るとしたらどうなるのだろうか...?(そもそも Array
をScalaであまり使わない印象があるが...)
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 n, m, x = sc.nextInt() val aArr = new Array[Array[Int]](n) val cArr = new Array[Int](n) (0 until n).foreach { i => cArr(i) = sc.nextInt() aArr(i) = (0 until m).map(_ => sc.nextInt()).toArray } val default = 1e9.toInt def dfs(idx: Int, sum: Int, willBuy: Boolean, skills: Array[Int]): Int = { if (idx > n - 1) { if (!skills.exists(_ < x)) sum else default } else { if (willBuy) { val nxt = aArr(idx).zip(skills).map { case (a, skill) => a + skill } val nxtSum = sum + cArr(idx) dfs(idx + 1, nxtSum, willBuy = true, nxt) min dfs(idx + 1, nxtSum, willBuy = false, nxt) } else { dfs(idx + 1, sum, willBuy = true, skills) min dfs(idx + 1, sum, willBuy = false, skills) } } } val result = dfs(-1, 0, willBuy = false, new Array[Int](m)) val ans = if (result == default) -1 else result pw.println(ans) pw.flush() }