#167936 (Haskell) No.129 お年玉(2)

提出ソース

結果

問題	No.129 お年玉(2)
ユーザー	aimy
提出日時	2017-04-22 11:31:08
言語	Haskell (9.8.2)
結果	AC
実行時間	86 ms / 5,000 ms
コード長	782 bytes
コンパイル時間	7,455 ms
コンパイル使用メモリ	169,344 KB
実行使用メモリ	94,208 KB
最終ジャッジ日時	2024-05-05 23:19:26
合計ジャッジ時間	10,283 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 9,984 KB
testcase_01	AC	86 ms 94,208 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	34 ms 36,224 KB
testcase_06	AC	49 ms 48,788 KB
testcase_07	AC	48 ms 41,724 KB
testcase_08	AC	50 ms 55,552 KB
testcase_09	AC	65 ms 66,904 KB
testcase_10	AC	53 ms 49,772 KB
testcase_11	AC	43 ms 43,668 KB
testcase_12	AC	62 ms 66,176 KB
testcase_13	AC	63 ms 68,608 KB
testcase_14	AC	50 ms 50,740 KB
testcase_15	AC	46 ms 45,568 KB
testcase_16	AC	45 ms 44,980 KB
testcase_17	AC	63 ms 66,304 KB
testcase_18	AC	50 ms 49,664 KB
testcase_19	AC	66 ms 66,812 KB
testcase_20	AC	52 ms 49,592 KB
testcase_21	AC	68 ms 68,024 KB
testcase_22	AC	47 ms 48,512 KB
testcase_23	AC	75 ms 81,280 KB
testcase_24	AC	69 ms 70,784 KB
testcase_25	AC	39 ms 36,480 KB
testcase_26	AC	49 ms 51,840 KB
testcase_27	AC	44 ms 46,720 KB
testcase_28	AC	72 ms 66,052 KB
testcase_29	AC	1 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	3 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	3 ms 5,504 KB
testcase_38	AC	9 ms 11,008 KB
testcase_39	AC	18 ms 22,400 KB
testcase_40	AC	44 ms 46,976 KB
testcase_41	AC	25 ms 23,324 KB
testcase_42	AC	13 ms 16,512 KB
testcase_43	AC	13 ms 16,384 KB
testcase_44	AC	85 ms 93,440 KB
testcase_45	AC	7 ms 9,856 KB
testcase_46	AC	20 ms 24,960 KB
testcase_47	AC	82 ms 90,752 KB
testcase_48	AC	54 ms 58,240 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:10:10: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Data.List, but defined in GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
   |
10 |   bits = tail (reverse (take w (unfoldr (return . swap . flip divMod 2) x)))
   |          ^^^^

Main.hs:14:6: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘head’
    (imported from Data.List, but defined in GHC.List):
    "This is a partial function, it throws an error on empty lists. Use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
   |
14 |    | head bs == 0 = query' left (tail bs)
   |      ^^^^

Main.hs:14:34: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Data.List, but defined in GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
   |
14 |    | head bs == 0 = query' left (tail bs)
   |                                  ^^^^

Main.hs:15:32: warning: [GHC-63394] [-Wx-partial]
    In the use of ‘tail’
    (imported from Data.List, but defined in GHC.List):
    "This is a partial function, it throws an error on empty lists. Replace it with drop 1, or use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."
   |
15 |    | otherwise = query' right (tail bs)
   |                                ^^^^
[2 of 2] Linking a.out

ソースコード

raw source code

import Data.Tuple
import Data.List

data Tree a = Node a (Tree a) (Tree a)
memoize f = memof where memof = f (query (blank memof))
blank f = blank' 1 where blank' k = Node (f k) (blank' (2*k)) (blank' (2*k+1))

query m x = query' m bits
 where
  bits = tail (reverse (take w (unfoldr (return . swap . flip divMod 2) x)))
  w = floor (logBase 2 (fromIntegral x)) + 1
  query' (Node v left right) bs
   | bs == [] = v
   | head bs == 0 = query' left (tail bs)
   | otherwise = query' right (tail bs)

q = 10^9

comb n r = div (fact n) (fact r * fact (n-r))
fact = memoize (\f x -> if x<=1 then 1 else x * f (x-1))

main = getContents >>= print . otoshidama . map read . words

otoshidama :: [Integer] -> Integer
otoshidama [n,m] = let r = mod n (1000*m) in mod (comb m (div r 1000)) q

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード