Experiments of Haskell programming, especially AtCoder.
See A good reference in Japanse
See, totemo kawaii.
String = [Char] is too slow.
See the discussion in Data.Text vs Data.ByteString.Char8
Instead of using
main = do
as <- map read . words <$> getLine
...
we must use Data.ByteString.Char8:
import qualified Data.ByteString.Char8 as C
import Data.Maybe ( fromJust )
readInt :: IO Int
readInt = fst . fromJust . C.readInt <$> C.getLine
readInts :: IO [Int]
readInts = map (fst . fromJust . C.readInt) . C.words <$> C.getLine
main = do
as <- readInts
...
http://fumieval.hatenablog.com/entry/2015/12/10/200630
TBA
Category Theory for Programmers: The Preface
See, again A good reference in Japanse
Mod, or rem.
For non-negative integers, use rem. (see https://twitter.com/mod_poppo/status/1092144670526791680)
As a common technique, e.g., if we want to calculate the round up the mean of a,b :: Int,
(a+b+1) `div` 2that is, we do not need to write like
kiriage a b
| even (a+b) = (a+b) `div` 2
| otherwise = (a+b+1) `div` 2 Brute-force search.
For loop
abc102_b Data.ByteString.Char8
abc113_b Data.ByteString.Char8
We have the following O(n) (not O(2*n)) maxMin,
maxMin :: [Int] -> (Int, Int)
maxMin = (,) <$> maximum <*> minimumabc072_b It is interesting but the raw recursion is faster and cheaper.
abc053_b Data.ByteString.Char8
Dynamic Programming (DP) algorithm
How is Dynamic programming different from Brute force
Integers (decimal numbers) and for loop.
agc025_a Vector performs well. Indeed, the interface is easy and clear.
Sorts, Greedy
abc042_b Data.ByteString.Char8
agc027_a Data.ByteString.Char8
agc012_a Data.ByteString.Char8
abc085_b Data.ByteString.Char8
abc071_b Data.ByteString.Char8
abc061_b Data.ByteString.Char8
abc091_b Data.ByteString.Char8
arc086_a Data.ByteString.Char8
Note: my implementation uses only List as the data structure. The execution time is so far beyond ok line, but some additional factor may be earned.
By the way, why this link is not self-consistent? I mean, the title after constests in its url differs from the last arc086_a.
Double, or triple folded for-loops (still eager search)
Initial attempt was using list comprehension to filter a correct combination. It basically the same as double-for-loops as in https://qiita.com/drken/items/fd4e5e3630d0f5859067#第-8-問--abc-085-c---otoshidama-300-点
Second attempt is much faster; first construct the ideal combination to pay Y-yen, maximumizing 10000-bills, then exchanging into smaller bill to reach the given N-bills.
abc088_c Data.ByteString.Char8
We do not need to find a solution, but to say the existance. Probably, it's a good time to study data structures.
arc096_a Data.ByteString.Char8
Simple comparison.
abc057_c Data.ByteString.Char8
Prime factors. It requires factor 2 in execution time and memory usage.
arc083_a Data.ByteString.Char8
Need better implementation, say factor 3. Filter has to be done only once.