ひらめの日常

日常のメモをつらつらと

Scalaで競技プログラミング: 標準入力周りで調べたこと

複数変数の初期化

例えば、1 2 3のように空白区切りで3つの標準入力を受け取るために、次のようなコードをよく書きます。

val sc = new Scanner(System.in)
val v, e, r = sc.nextInt()

これは左辺の変数の個数分、右辺の式が評価されているようです。(公式ドキュメントが見当たらないので、探しています...)

scala> val a, b, c = 1
val a: Int = 1
val b: Int = 1
val c: Int = 1

scala> val a, b, c = util.Random.nextInt()
val a: Int = 2127446030
val b: Int = 1199584050
val c: Int = 638157382

これは ScannernextInt() を使うことによって実現できるのですが、Scalascala.io.StdIn.readInt() ではできません。

Scanner (Java Platform SE 8)

Scala Standard Library 2.13.3 - scala.io.StdIn

なぜかというと、ScalareadInt() は「readLine() した結果に対して toInt を呼び出している」だけだからです。なので空白区切りの入力に対しては readLine().split(" ").map(_.toInt) のように文字列を分割する処理を入れなければいけません。readInt() の内部実装は以下の通りです。

/** Reads an int value from an entire line of the default input.
 *
 *  @return the Int that was read
 *  @throws java.io.EOFException if the end of the
 *  input stream has been reached.
 *  @throws java.lang.NumberFormatException if the value couldn't be converted to an Int
 */
def readInt(): Int = {
  val s = readLine()
  if (s == null)
    throw new java.io.EOFException("Console has reached end of input")
  else
    s.toInt
}

複数行の読み込み

この記事を参考にしました。

qiita.com

AOJなどでは、行数が与えられずに、「与えられた行数分処理しなさい」という問題があります。行数が与えられればその数だけループ回せば良いのですが、そうではないので困ってしまいますね。(例えばこの問題などです:Aizu Online Judge

その際はio.Source.stdin.getLines() を呼び出すことで、次の入力がある限りは読み込み続けてくれます。

Scala Standard Library 2.13.3 - scala.io.Source

for (l <- io.Source.stdin.getLines()) {
  val arr = l.split(" ").map(_.toInt)
  ...
}

Array.fill

サイズnの入力を受け取り、配列として初期化する際に、次のようなコードをよく書きます。

val a = Array.fill(n)(sc.nextInt())

これでn回の入力を受け取っているのですが、これは Array.fill の第二引数が名前渡し引数(call-by-name)になっているからです。そのおかげで、第二引数がn回呼び出されることになり、意図した挙動になります。

Scala Standard Library 2.12.4 - scala.Array

By-name Parameters | Tour of Scala | Scala Documentation

By-name parameters are evaluated every time they are used. They won’t be evaluated at all if they are unused. This is similar to replacing the by-name parameters with the passed expressions.

Array.fill の内部実装は以下の通りです。

  /** Returns an array that contains the results of some element computation a number
   *  of times.
   *
   *  Note that this means that `elem` is computed a total of n times:
   *  {{{
   * scala> Array.fill(3){ math.random }
   * res3: Array[Double] = Array(0.365461167592537, 1.550395944913685E-4, 0.7907242137333306)
   *  }}}
   *
   *  @param   n  the number of elements desired
   *  @param   elem the element computation
   *  @return an Array of size n, where each element contains the result of computing
   *  `elem`.
   */
  def fill[T: ClassTag](n: Int)(elem: => T): Array[T] = {
    if (n <= 0) {
      empty[T]
    } else {
      val array = new Array[T](n)
      var i = 0
      while (i < n) {
        array(i) = elem
        i += 1
      }
      array
    }
  }

コメントや例が書いてあり、丁寧だと感じました。

Note that this means that elem is computed a total of n times