LoginSignup
4
3

More than 1 year has passed since last update.

@ka2kama

AtCoderの過去問精選 10 問をScalaで解いてみる

Last updated at Posted at 2021-04-11

はじめに

けんちょんさんの有名記事、AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ に出てくる過去問精選10問を Scala で解いてみました｡

先に上記の記事を読んでいる方が対象のため､解法やアルゴリズムの解説などは省いています｡

ベースとなる解法は元記事に合わせつつ､要所要所でScalaのテイストと､あと筆者のこだわりを取り入れています｡
また説明用に多少冗長にしている部分もあります.

これからScalaでAtCoder (または競技プログラミング全般) を始めようと思っている方の参考になれば幸いです｡

第 1 問: ABC 086 A - Product (100 点)

解答例
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in) // ①
    val a, b = sc.nextInt() // ②
    val c = a * b
    val ans = if (c % 2 == 0) "Even" else "Odd" // ③
    println(ans)
  }
}

① 入力を受け取るのにJavaの Scanner クラスを使っています｡
AtCoderでは空白区切りの文字列などが頻出するので､ scala.io.StdIn.readInt などより Scanner の方が簡便に書けます｡

② Scalaでは複数の変数を一遍に初期化出来ます｡
このとき､右辺の sc.nextInt() は左辺に並べた変数の数だけ呼び出されます｡

今回の例でいうと､例えば 3 4 のような空白区切りの文字列に対し sc.nextInt() を2回呼び出すことで､変数 a には 3 が､変数 b には 4 が代入されます｡
少しハッキーな書き方ではありますが､AtCoderでは非常によく使いますので､覚えておいて損はありません｡

もちろん､下記のように2行に分けても構いません｡

val a = sc.nextInt()
val b = sc.nextInt()

③ Scalaの if は文ではなく式のため、値を返します｡
Java の三項演算子のようなものと思っていただければいいと思います (三項演算子よりは幾分高機能ですが)｡
ここでは解答として出力する文字列を変数 ans に代入しています｡

第 2 問: ABC 081 A - Placing Marbles (100 点)

解答例
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val s = sc.next() // ① 
    val ans = s.count { _ == '1' } // ②
    println(ans)
  }
}

① 入力値を文字列として受け取っています｡

② String ( 正確にはStringOps ) の count メソッドを使い､引数の条件に合致する文字の数を取得します｡
文字列を文字 ( Char ) のリストとして捉えれば理解しやすいのではないかと思われます｡

第 3 問: ABC 081 B - Shift Only (200 点)

解答例1
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt()
    val list = Seq.fill(n)(sc.nextInt()) // ①
 
    val ans = solve(list)
    println(ans)
  }
 
  def solve(list: Seq[Int]): Int = {
    val xs = Iterator
      .iterate(list) { _.map { _ / 2 } } // ②
      .takeWhile { _.forall { _ % 2 == 0 } } // ③

    xs.size // ④
  }
}
解答例2
  import scala.annotation.tailrec
 
  def solve(list: Seq[Int]): Int = {
    @tailrec // ⑤
    def loop(xs: Seq[Int], cnt: Int): Int =
      if (xs.forall { _ % 2 == 0 }) {
        val ys = xs.map { _ / 2 }
        loop(ys, cnt + 1) // ⑥
      } else cnt
 
    loop(list, 0)
  }
解答例3
  def solve(list: Seq[Int]): Int = {
    var xs = list
    var cnt = 0
    while (xs.forall { _ % 2 == 0 }) {
      xs = xs.map { _ / 2 }
      cnt += 1
    }

    cnt
  }

① 事前に個数が与えられている状態で､その後の入力値を､数値ごとにリストに詰める処理です｡
例えば入力が以下のようだったとします｡

3
8 12 40

この場合､上記のソースでいう変数 n が 3 となり､変数 list は List(8, 12, 40) となります｡1
また空白区切りだけでなく､以下のように改行区切りの場合も同様です｡

3
8
12
40

この手の入力は頻出なので､この書き方もほぼ定型です｡

あとはその後の構想に応じて List.fill や ArraySeq.fill ､ Iterator.fillなどのデータ構造を使い分けます｡

大まかに言うと､ head/tail を多用する場合は List.fill ､ 添字アクセスを多用する場合は ArraySeq.fill､ 逐次読み込みを一度だけ行えればいいのであれば Iterator.fill あたりが候補になります｡

とはいえ､実際はACになりさえすればどれを使っても構いません｡
迷ったら Seq.fill でいいと思います｡

② Iterator.iterateメソッドを使い､「要素を全て 2 で割る」という行為を無限に繰り返し､それぞれの時点のスナップショットのリスト (のようなもの) を生成しています｡2
イメージとしては､等差数列や等比数列が近いでしょうか｡
ただし Iterator は計算を遅延するので､実際にはすぐ下の takeWhile の継続条件を満たさなくなった時点で繰り返し処理が打ち切られます｡

③ takeWhile の継続条件である「リスト内の要素がすべて偶数であること」を判定するために forall メソッドを使っています｡

Scalaはコレクション操作のメソッドが充実しているので､どういうメソッドがあるかを知っておくと､思考とタイピングの手間が省けます｡

参考:
・ scala.collection.immutable.Seq
・ Scalaコレクションメソッド

④ 取得できたスナップショットの数がそのまま､「要素を全て 2 で割る」という行為を繰り返すことが出来た回数 (= 答え) になります｡

⑤ 解答例 2 では､ Iterator ではなく末尾再帰関数を使って問題を解いています｡
tailrec アノテーションはなくても動きますが､うっかり末尾再帰になっていないときにコンパイラが教えてくれるので､常につけておくことをオススメします｡

⑥ 要素を全て 2 で割り､カウントを 1 増やして次のループへ行きます｡
Scalaでは再帰は末尾再帰であればwhileループに変換されるので､何度再帰関数を呼び出してもスタックオーバーフローにはなりません｡

末尾再帰関数は､解答例 3 のようにwhileループで書くことも出来ます｡

これくらい単純なループであれば､whileの方が読みやすいかもしれません｡
ただScalaのwhileには break や continue が存在しないので､全てをwhileで記述するには少々書きにくい部分もあります｡3
末尾再帰の書き方も知っておいて損はないかと思われます｡

補足
元々業務などでScalaを使っていた人にとっては､解答例 3 のようなゴリゴリの手続き型の書き方はあまり Scala "らしくない" と思われるかもしれません｡
しかし､手続き型 "でも書ける" ことはScalaの強みの一つだと､筆者は考えています｡
AtCoderは大前提として「時間内にACを取れなければ無価値」なので､問題に応じた有益な書き方を使い分けるのが一番だと思います｡

第 4 問: ABC 087 B - Coins (200 点)

解答例
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val a, b, c, x = sc.nextInt()
 
    val ans = solve(a, b, c, x)
    println(ans)
  }

  def solve(a: Int, b: Int, c: Int, x: Int): Int = {
    val xs = for {
      aa <- 0 to a // ①
      bb <- 0 to b
      cc <- 0 to c
      total = 500 * aa + 100 * bb + 50 * cc
      if total == x
    } yield (aa, bb, cc) // ②

    xs.size // ③
  }
}

① Scalaの多重ループは､そのまま縦に並べることが出来ます｡

② 組み合わせを保持しリストを作っています｡
今回の問題の場合､組み合わせの詳細は必要ないので､ここは固定値でも構いません｡

③ 組み合わせの数を返します｡

第 5 問: ABC 083 B - Some Sums (200 点)

解答例1
import scala.annotation.tailrec
 
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n, a, b = sc.nextInt()
 
    val ans = solve(n, a, b)
    println(ans)
  }
 
  def solve(n: Int, a: Int, b: Int): Int = {
    val xs = (1 to n).filter { i => // ①
      val s = findSumOfDigits(i)
      s >= a && s <= b
    }

    xs.sum
  }

  def findSumOfDigits(n: Int): Int = {
    val digits = n.toString.map { _.asDigit} // ②

    digits.sum
  }
}
解答例2
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n, a, b = sc.nextInt()
 
    val ans = solve(n, a, b)
    println(ans)
  }
 
  def solve(n: Int, a: Int, b: Int): Int = {
    var total = 0
    for (i <- 1 to n) {
      val s = findSumOfDigits(i)
      if (s >= a && s <= b) {
        total += i
      }
    }
 
    total
  }
 
  def findSumOfDigits(n: Int): Int = {
    var m = n
    var sum = 0
    while (m > 0) {
      sum += m % 10
      m /= 10
    }

    sum
  }
}

① filter メソッドで該当する数字のみ抽出したリストを作成し､合計を出しています｡

② 数値を一度文字列に変換した後､桁ごとの数の合計を出しています｡
Scalaにおいて String は Char のリストとして扱うことができるので､各桁の文字を Char#asDigit メソッドで Int に変換しています｡

解答例2は､ほとんど元記事と同じ記述にしてみました (解説は省きます)｡

第 6 問: ABC 088 B - Card Game for Two (200 点)

解答例1
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt()
    val cards = Seq.fill(n)(sc.nextInt())
 
    val ans = solve(cards)
    println(ans)
  }
 
  def solve(cards: Seq[Int]): Int = {
    val (alice, bob) = cards
      .view // ①
      .sorted(Ordering[Int].reverse) // ②
      .zipWithIndex // ③
      .foldLeft((0, 0)) { case ((alice, bob), (a, i)) => // ④
        if (i % 2 == 0)
          (alice + a, bob)
        else
          (alice, bob + a)
      }
 
    alice - bob
  }
}
解答例2
  // ⑤
  sealed trait Player
  case object Alice extends Player
  case object Bob extends Player

  def solve(cards: Seq[Int]): Int = {
    // ⑥
    val (alice, bob, _) = cards.view
      .sorted(Ordering[Int].reverse)
      .foldLeft((0, 0, Alice: Player)) { case ((alice, bob, player), a) =>
        player match {
          case Alice => (alice + a, bob, Bob)
          case Bob   => (alice, bob + a, Alice)
        }
      }

    alice - bob
  }

① 引数のリストにいくつかの処理を加えるので､無駄な中間生成物を作らないようViewに変換しています｡
Viewについては下記のドキュメントを参考にしてください｡
参考: Views

ただし､この問題程度のデータ量でViewを使うメリットはほぼありません｡4
単に筆者の趣味です｡

② 数値のリストを降順ソートしています｡
sorted メソッドは何も渡さなければ今回のケースだと昇順ソートになってしまうので､降順ソートになるよう Ordering[Int].reverse を指定しています｡
他にも「一度昇順ソートしてから逆順にする」､「昇順ソートしておいて後ろから取る」なども考えられますが､最初から降順ソートにしてしまうのが一番無駄もなくわかりやすいと思います｡

③ zipWithIndex メソッドを使い､元々のリストの要素を､要素と添字のタプルにしています｡
これは Scala でリストの添字を取得するための常套手段です｡

④ AliceとBobのそれぞれの初期点数を0点として､リストの先頭から交互に点数を加算しています｡
最終的にそれぞれの合計点がタプルとして取得できるので､変数宣言でもパターンマッチで別々の変数に代入し､差をとって終了です｡

⑤ 解答例 2 は添字を使わない解法にしてみました｡
プレイヤーを表す列挙を定め､タプルに「現在のプレイヤー」を追加し､要素ごとに交互に切り替えています｡
最初にカードを取るのはAliceなので､初期プレイヤーにはAliceを配置しています｡

⑥ 解答例 2 の書き方だと､最後に合計点と共に次のプレイヤーも取得しますが､その情報は不要なので変数のパターンマッチ時に _ を使い情報を捨てています｡

第 7 問: ABC 085 B - Kagami Mochi (200 点)

解答例1
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt()
    val xs = Seq.fill(n)(sc.nextInt())

    println(xs.distinct.size) // ①
  }
}
解答例2
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt()
    val set = Iterator.fill(n)(sc.nextInt()).toSet // ②

    println(set.size)
  }
}

① この問題では異なる数の個数を求めたいので､ 読み込み後に distinct メソッドでリスト内の重複を省き､size を取得しています｡

② 解答例 2 では､読み込み後に scala.collection.immutable.Set に変換しています｡
Set に変換することで重複はなくなるので､その size を取ればそれが答えになります｡
重複を省くためだけに Set を使うことの是非はありますが､競プロでは使えるものは何でも使えばいいと思います｡

なおここで Iterator.fill としているのは､すぐ Set に変換する予定なので無駄に Seq などの中間生成物を作らないようにしたかったからです｡
また直接 Set.fill としなかったのは､fillという名前に対して動きが少しトリッキー ( fill の第一引数の数と実際の個数が違う可能性がある) に感じたためです｡
どちらも筆者の趣味です｡

第 8 問: ABC 085 C - Otoshidama (300 点)

解答例1
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n, y = sc.nextInt()
 
    val (a, b, c) = solve(n, y)
    println(s"$a $b $c") // ①
  }
 
  def solve(n: Int, y: Int): (Int, Int, Int) = {
    val p = for {
      a <- (0 to n).view // ②
      b <- (0 to n - a).view
      c = n - a - b
      total = 10000 * a + 5000 * b + 1000 * c
      if total == y
    } yield (a, b, c)
 
    p.headOption.getOrElse((-1, -1, -1))
  }
}
解答例2
  import scala.annotation.tailrec

  def solve(n: Int, y: Int): (Int, Int, Int) = {
    @tailrec
    def loop(a: Int): Option[(Int, Int, Int)] =
      if (a > n) None
      else {
        @tailrec
        def loop2(b: Int): Option[(Int, Int)] =
          if (b > n - a) None
          else {
            val c = n - a - b
            val total = 10000 * a + 5000 * b + 1000 * c
            if (total == y) Some((b, c))
            else loop2(b + 1)
          }
 
        loop2(0) match {
          case Some((b, c)) => Some((a, b, c))
          case None         => loop(a + 1)
        }
      }
 
    loop(0).getOrElse((-1, -1, -1))
  }

① 文字列に変数を埋め込むのに文字列補間を使っています｡
参考: 文字列の補間

② ループを回す際に､第 6 問でも使った View に変換しています｡

ここでは二重ループを使っていますが､この問題の性質上､正解となる組み合わせはたった一つ見つかれば充分です｡
しかしここで View に変換しておかないと､例え一番最初に試した組み合わせが正解でも､そのまま全ての試行が終わるまでループが続いてしまいます｡

View に変換しておくと計算が遅延され､後で必要になった分しか処理されません｡
この場合でいうと headOption に必要な分だけ処理されるので､正解の組み合わせが一つでも見つかればそこで処理が打ち切られます｡

例によって､この問題ではViewに変換せずとも(全ての試行を試しても) ACになりますし､実行時間にもほぼ影響がありません｡いつもの趣味です｡

解答例 2 では､解答例 1 とほぼ似たようなことを末尾再帰のみで書いてみました｡
実行時間こそ解答例 1 より若干速かったものの､見ての通りかなりごちゃごちゃしてしまっています｡
参考程度に留めておいていただければと思います｡

第 9 問: ABC 049 C - Daydream (300 点)

解答例
import scala.annotation.tailrec

object Main {

  val words = Seq("dream", "dreamer", "erase", "eraser")

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val s = sc.nextLine()

    val ans = solve(s)
    println(ans)
  }

  def solve(s: String): String = {
    val rwords = words.map { _.reverse }

    @tailrec
    def check(reversed: String): Boolean =
      if (reversed.isEmpty) true
      else
        rwords.find(reversed.startsWith) match { // ①
          case Some(rword) =>
            val rest = reversed.drop(rword.length) // ②
            check(rest)
          case None => false
        }

    if (check(s.reverse)) "YES" else "NO"
  }
}

① 逆順にした対象単語のリストの中から､reversedに前方一致しているものを見つけています｡

② 前方一致している単語があれば､元の文字列からその単語の文字数分の文字を削り､次のループに渡します｡
文字列が空になるか､前方一致する文字列が見つからなくなるまで続けます｡

第 10 問: ABC 086 C - Traveling (300 点)

解答例
case class Plan(t: Int, x: Int, y: Int) // ①

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt()
    val plans = List.fill(n) {
      val t, x, y = sc.nextInt()
      Plan(t, x, y) // ②
    }

    val ans: String = solve(plans)
    println(ans)
  }

  def solve(plans: List[Plan]): String = {
    import scala.math.abs

    val start = Plan(0, 0, 0) // ③
    val can = (start :: plans).zip(plans) // ④
      .forall { case (current, next) => // ⑤
        val dt = next.t - current.t
        val dist = abs(next.x - current.x) + abs(next.y - current.y)
        dt >= dist && dist % 2 == dt % 2
      }

    if (can) "Yes" else "No"
  }
}

① 入力行の情報を保持するための case class を定義しています｡
タプルでもいいのですが､後の処理を考えると case class の方が取り回しやすいのでそうしています｡

② 入力行から読み取った数値を ① の case class に詰めています｡
これにより Plan クラスのリストが出来上がります｡
問題の制約上必ず t の昇順になっているので､特にソートなどは行いません｡

③ スタート時の時刻および地点を表すインスタンスです｡

④ 元記事では添字を使い､今の要素 (t[i]) と次の要素 (t[i + 1]) を比べていました｡
ここでは､スタート地点( start ) を含むリストと含まないリストを zip し､ (今のPlan, 次のPlan) というタプルのリストにしています｡

:: は List クラスのメソッドで､リストの先頭に要素を追加します｡
List 以外でも同じことは出来ますが､ List であれば先頭への追加は定数時間で行われます｡
これをしたかったので 行読み込み時に List.fill で List として読み込んでいます｡
もし元記事と同じく添字アクセスで解く場合､List だと遅い5 ので､ Vector や ArraySeq のような IndexedSeq 系列のクラスを使いましょう｡

⑤ タプルにしたので､そのまま第 3 問でも使用した forall メソッドで､それぞれの要素ごとに判定ができます｡
全ての時間・点で次の場所へ到達できれば true ､ そうでなければ false です｡

補足: AtCoderの入出力について

以上､ 過去問精選10問を Scala で解いてみました｡

注意点として､Scalaの標準入力・標準出力は遅いということが挙げられます｡
特に C 問題以降かつ､入出力データが大量にあるタイプの問題だと､最悪 TLE (Time Limit Exceeded｡ 指定された上限実行時間超過｡ 誤答扱い) になります｡
下記の記事が非常に参考になりましたので､必要に応じて入出力の方法を工夫してみてください｡

Scalaで競技プログラミングするためのTips


最後までお読み頂きありがとうございました｡ 質問や不備についてはコメント欄か[Twitter](https://twitter.com/ka2_kamaboko)までお願いします。

  1. Seq.fill と書いた場合､実体としては List になります｡ ↩

  2. イテレータとリストの違いは ドキュメント を参考にしてください｡ ↩

  3. 厳密には breakable というものがありますが､ C や Java の break とは若干毛色が異なるためここでは割愛します｡ ↩

  4. むしろデータ量によってはオーバーヘッドで無駄が出るまであります｡ ↩

  5. List のランダムアクセスの計算量は O(n) です｡ ↩

4
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
3