結果

問題 No.3 ビットすごろく
ユーザー くわいくわい
提出日時 2015-11-05 20:31:28
言語 Scala(Beta)
(3.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,196 bytes
コンパイル時間 6,354 ms
コンパイル使用メモリ 224,696 KB
最終ジャッジ日時 2024-11-14 19:25:20
合計ジャッジ時間 6,814 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
-- [E040] Syntax Error: Main.scala:45:32 ---------------------------------------
45 |  def main(args: Array[String]) {
   |                                ^
   |                                '=' expected, but '{' found
1 error found

ソースコード

diff # 

import scala.collection.mutable
import scala.io.StdIn

object Problem003 {

  case class State(current: Int, steps: Int)

  object StateOrdering extends Ordering[State] {
    def compare(a: State, b: State) = a.steps compare b.steps
  }

  def bitCount(i: Int): Int = Integer.bitCount(i)

  def proc(goal: Int): Int = {
    def inField(i: Int): Boolean = 1 <= i && i <= goal

    val dp = Array.fill(goal + 1)(Int.MaxValue)

    val queue = new mutable.PriorityQueue[State]()(StateOrdering.reverse)
    queue += State(1, 0)

    while (queue.nonEmpty) {
      def add(currentPlace: Int, nextSteps: Int): Unit = {
        if (inField(currentPlace) && dp(currentPlace) > nextSteps) {
          queue += State(currentPlace, nextSteps)
          dp(currentPlace) = nextSteps
        }
      }

      val s = queue.dequeue()

      if (s.current == goal) return s.steps + 1

      val back = s.current - bitCount(s.current)
      val forward = s.current + bitCount(s.current)
      val nextSteps = s.steps + 1

      add(back, nextSteps)
      add(forward, nextSteps)
    }

    -1
  }

  def main(args: Array[String]) {
    val n = StdIn.readInt()

    val result = proc(n)
    println(result)
  }
}
0