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

提出ソース

結果

問題	No.129 お年玉(2)
ユーザー	aimy
提出日時	2017-04-22 11:31:08
言語	Haskell (9.10.1)
結果	AC
実行時間	94 ms / 5,000 ms
コード長	782 bytes
コンパイル時間	5,954 ms
コンパイル使用メモリ	169,600 KB
実行使用メモリ	94,080 KB
最終ジャッジ日時	2024-11-28 00:49:06
合計ジャッジ時間	9,446 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 9,600 KB
testcase_01	AC	94 ms 94,080 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	37 ms 36,096 KB
testcase_06	AC	55 ms 48,536 KB
testcase_07	AC	55 ms 41,604 KB
testcase_08	AC	55 ms 55,552 KB
testcase_09	AC	67 ms 66,904 KB
testcase_10	AC	58 ms 49,520 KB
testcase_11	AC	50 ms 43,536 KB
testcase_12	AC	67 ms 66,304 KB
testcase_13	AC	68 ms 68,864 KB
testcase_14	AC	55 ms 50,724 KB
testcase_15	AC	52 ms 45,312 KB
testcase_16	AC	51 ms 44,596 KB
testcase_17	AC	69 ms 65,920 KB
testcase_18	AC	55 ms 49,536 KB
testcase_19	AC	71 ms 66,812 KB
testcase_20	AC	58 ms 49,592 KB
testcase_21	AC	76 ms 68,144 KB
testcase_22	AC	52 ms 48,512 KB
testcase_23	AC	81 ms 81,536 KB
testcase_24	AC	71 ms 70,912 KB
testcase_25	AC	46 ms 36,224 KB
testcase_26	AC	53 ms 51,968 KB
testcase_27	AC	49 ms 46,976 KB
testcase_28	AC	77 ms 65,924 KB
testcase_29	AC	1 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	3 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	3 ms 5,248 KB
testcase_36	AC	3 ms 5,248 KB
testcase_37	AC	3 ms 5,504 KB
testcase_38	AC	11 ms 10,880 KB
testcase_39	AC	21 ms 22,400 KB
testcase_40	AC	47 ms 46,848 KB
testcase_41	AC	29 ms 23,192 KB
testcase_42	AC	15 ms 16,256 KB
testcase_43	AC	15 ms 16,640 KB
testcase_44	AC	93 ms 93,440 KB
testcase_45	AC	9 ms 9,856 KB
testcase_46	AC	23 ms 24,960 KB
testcase_47	AC	91 ms 90,880 KB
testcase_48	AC	58 ms 57,984 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

結果

テストケース

コンパイルメッセージ

ソースコード