結果

問題 No.3 ビットすごろく
ユーザー tanson
提出日時 2025-08-12 02:14:21
言語 Standard ML
(MLton 20210117)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 2,231 bytes
コンパイル時間 3,847 ms
コンパイル使用メモリ 687,864 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-12 02:14:30
合計ジャッジ時間 6,342 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

signature QUEUE =
sig
    type 'a t
    exception QueueEmpty
    val empty : 'a t
    val push : 'a -> 'a t -> 'a t
    val peek : 'a t -> 'a
    val drop : 'a t -> 'a t

    val isEmpty : 'a t -> bool
end


structure Queue : QUEUE =
struct
datatype 'a t = Queue of ('a list * 'a list)
exception QueueEmpty

val empty = Queue([], [])

fun normalForm (Queue ([], back)) = (Queue (List.rev back, []))
  | normalForm queue = queue;

fun push x (Queue (front, back)) = normalForm (Queue (front, x::back))

fun peek (Queue (h::_, _)) = h
  | peek (Queue ([], _)) = raise QueueEmpty

fun drop (Queue (h::t, back)) = normalForm (Queue (t, back))
  | drop (Queue ([], _)) = raise QueueEmpty

fun isEmpty (Queue ([], [])) = true
  | isEmpty _ = false

end


fun readInt () =
    valOf (TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn)


fun intString n =
    if 0 <= n
    then Int.toString n
    else "-" ^ Int.toString (abs n)


fun intToNumOfBit n =
    foldl (fn (c, acc) => if c = #"1" then acc + 1 else acc)
          0  
          (explode (Int.fmt StringCvt.BIN n))


fun findAns target used queue =
    let
        val (depth, location) = Queue.peek queue
    in
        if location = target then depth
        else
            (
              let
                  val numOfBit = intToNumOfBit location
                  val p = location + numOfBit
                  val m = location - numOfBit
                  val queue0 = Queue.drop queue
                  val queue1 = if p <= target andalso Array.sub (used, p) = false then Queue.push (depth + 1, p) queue0 before Array.update (used, p, true)
                               else queue0
                  val queue2 = if 1 <= m andalso Array.sub (used, m) = false then Queue.push (depth + 1, m) queue1 before Array.update (used, m, true)
                               else queue1
              in
                  findAns target used queue2
              end
            )
    end


val () =
    let
        val n = readInt ()
        val used = Array.array (n + 1, false)
        val queue = Queue.empty

        val ans = (findAns n used (Queue.push (1, 1) queue)
                   handle QueueEmpty => ~1)
    in
        print ((intString ans) ^ "\n")
    end
0