結果

問題 No.3 ビットすごろく
ユーザー 3405691582
提出日時 2017-03-21 02:49:09
言語 Haskell
(8.0.2)
結果
AC  
実行時間 4216 ms
コード長 921 Byte
コンパイル時間 1583 ms
使用メモリ 5892 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 3 ms
1892 KB
2.txt AC 3 ms
1900 KB
3.txt AC 3 ms
1892 KB
4.txt AC 151 ms
4868 KB
5.txt AC 14 ms
4848 KB
6.txt AC 919 ms
4860 KB
7.txt AC 188 ms
4860 KB
8.txt AC 61 ms
4752 KB
9.txt AC 538 ms
4868 KB
10.txt AC 1646 ms
5880 KB
11.txt AC 2484 ms
5884 KB
12.txt AC 1321 ms
4864 KB
13.txt AC 849 ms
4856 KB
14.txt AC 108 ms
4840 KB
15.txt AC 2266 ms
5884 KB
16.txt AC 3933 ms
5892 KB
17.txt AC 3285 ms
5892 KB
18.txt AC 3777 ms
5884 KB
19.txt AC 124 ms
4808 KB
20.txt AC 4216 ms
5888 KB
challenge01.txt AC 2366 ms
5892 KB
challenge02.txt AC 3968 ms
5884 KB
challenge03.txt AC 3965 ms
5884 KB
system_test1.txt AC 3921 ms
5884 KB
system_test2.txt AC 3 ms
1884 KB
system_test3.txt AC 127 ms
4864 KB
system_test4.txt AC 3089 ms
5884 KB
system_test5.txt AC 1407 ms
5888 KB
system_test6.txt AC 3 ms
2204 KB
system_test7.txt AC 4 ms
2416 KB
system_test8.txt AC 1144 ms
4856 KB
テストケース一括ダウンロード

ソースコード

diff #
import Data.Array
type Board = Array Int Int
main = do
  n <- read <$> getLine :: IO Int
  putStrLn $ show $ calcMinDist n

updateBoard :: ([Int],Board) -> ([Int],Board)
updateBoard ([],b) = ([],b)
updateBoard (is,b) = 
  (is',(b//if b!i'<0 then [] else prev ++ next))
  where
    (_,n) = bounds b
    numOfOne = sum . map (`mod`2) . takeWhile (>0) . iterate (`div`2)
    pr = i' - numOfOne i'
    nx = i' + numOfOne i'
    prev = if pr<1 || (b!pr>0&&b!pr<b!i'+1) then [] else [(pr,b!i'+1)]
    next = if nx>n || (b!nx>0&&b!nx<b!i'+1) then [] else [(nx,b!i'+1)]
    (i',is') = findMinDistInd is
    findMinDistInd [i] = (i,[])
    findMinDistInd (i:is) =
      let (i',is') = findMinDistInd is in
        if b!i'<0 || (b!i>=0 && b!i<=b!i') then (i,i':is') else (i',i:is')

calcMinDist :: Int -> Int
calcMinDist n =
  snd (iterate updateBoard ([1..n],board)!!(n+1)) ! n
  where
    board = listArray (1,n) $ 1:repeat (-1)
0