ひらめの日常

プログラミングと読書と

Scalaで競技プログラミング ABC167-C Skill Up

始めに

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

問題はこちら

atcoder.jp

解答

C++で解いたときはbit全探索をしたが、今回パッと思いつかなかったので、再帰関数で実装した。各種類の参考書を購入するかしないかで分岐するようにして、全ての場合を調べる。

本来なら Array の要素を書き換えるような方法で入力を受け取りたくないが、Scalaっぽく受け取るとしたらどうなるのだろうか...?(そもそも ArrayScalaであまり使わない印象があるが...)

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()
}

Submission #17661602 - AtCoder Beginner Contest 167