No Such Blog or Diary
AMラジオって
- 2005-11-18 (Fri)
- 一般
受信できるデバイスが身の回りに皆無だなぁと初めて認識した.コンポやらラジカセがあれば受信できそうなものだがMP3プレーヤとスピーカで置換されてるし,MP3プレーヤもノイズとかの問題かFMしか受信できないし.明日の夜は需要があるので非常時にも役に立つと信じてラジオを購入.意外と高し.100円ショップとか行けば安く手に入ったのだろうか...?
- Comments: 0
- TrackBack (Close): -
ICPC by Haskell
ながながとICPC2005 Regional, Tokyo の問題Fを Haskell で.O(n^2) の DP で, 基本的に foldl の2重ネストと.Cで書いた場合と比べて for 文の代わりに foldl になっているだけの違いしかない...
-- Problem F in ACM/ICPC 2005 ASIA Regional Tokyo -- 2005/11/04 O(n^2) DP import Control.Monad import Debug.Trace import List main = getProblems >>= mapM_ (putStrLn.show.solve) getProblems = do [n] <- getNums if n==0 then return [] else do xs <- getNums b <- liftM (head.map read.words) getLine :: IO(Double) [sr,sv,se,sf] <- liftM words getLine liftM ((xs, b, read sr, read sv::Double, read se::Double, read sf::Double):) getProblems where getNums = liftM (map read.words) getLine :: IO([Int]) solve :: ([Int], Double, Int, Double, Double, Double) -> Double solve (ys,b,r,v,e,f) = sl ys [(0.0,0)] where -- xs:rest of checkpoints, cs:best cost for already passed checkpoints sl [] cs = fst $ head cs sl (x:xs) cs = sl xs (best x cs:cs) -- (best cost, current cost, current point) best x cs = (\(bc,c,p) -> (min bc (c + cost (x-p) x),x)) $ foldl op (100000000, 0, x) cs where op (cbc, c, p) (bc, pos) = let c' = c + cost (x-p) (x-pos) in (min cbc (c'+b+bc), c', pos) cost p q = ct p 0.0 where ct p c = if p == q then c else ct (p+1) (c+step p) step p = if p < r then 1.0 / (v-f*fromIntegral(r-p)) else 1.0 / (v-e*fromIntegral(p-r))
- Comments: 0
- TrackBack (Close): -
ICPC by Haskell
なぜか D を飛ばしてICPC2005 Regional, Tokyo の問題Eを Haskell で.全生成して条件で filter して max とるという非常に美しい形に...
-- Problem E in ACM/ICPC 2005 ASIA Regional Tokyo -- 2005/11/04 Brute Force (42 * 2^5) import Control.Monad import Debug.Trace import List main = getProblems >>= mapM_ (putStrLn.(\r -> if r < 0 then "-1" else show r).solve) getProblems = do n <- liftM (head.map read.words) getLine replicateM n getProblem getProblem = do r <- getNum s <- liftM (head.map read.words) getLine ws <- replicateM s getNum return (r, ws) where getNum = liftM (head.map read.words) getLine :: IO(Double) solve :: (Double, [Double])->Double solve (r, ws) = foldl max (-1.0).filter (<r).map(\(lw, rw)->lw+rw).concat.map genWidth.concat.map genTree.perm $ ws data BTree a = Node a (BTree a) (BTree a) | Leaf a genTree ] = [Leaf genTree xs = [ Node (weight t + weight u) t u | i <- [1..length xs-1], t<-genTree (take i xs), u<-genTree (drop i xs)] weight (Leaf x) = x weight (Node x _ _) = x genWidth (Leaf x) = [(0.0,0.0)] genWidth (Node _ l r) = let ls = genWidth l rs = genWidth r lw = weight l rw = weight r la = lw/(lw + rw) ra = 1-la in [x | (ll,lr)<-ls, (rl,rr)<-rs, x<-gen ll lr rl rr la ra] gen ll lr rl rr la ra = dupFlip (max (la + ll) (rl-ra), max (ra + rr) (lr-la)) dupFlip (x,y) = [(x,y), (y,x)] perm [] = [] perm ] = [[] perm (x:xs) = [ take i y ++ (x:drop i y) | y <- perm xs, i <- [1..length xs]]
- Comments: 0
- TrackBack (Close): -
ICPC by Haskell
引き続きICPC2005 Regional, Tokyo の問題Cを Haskell で.サイコロの全パタン生成が一番面倒かも.全盛生後の比較の高速化のために色名を数字に置き換える部分は少々手抜きかも.
-- Problem C in ACM/ICPC 2005 ASIA Regional Tokyo -- 2005/11/04 Brute Force (24^3) import Control.Monad import Debug.Trace import List main = getProblems >>= mapM_ (putStrLn.show.solve) getProblems = do [n] <- getNums if n==0 then return [] else do xs <- replicateM n getEntry liftM (xs:) getProblems where getEntry = liftM words getLine getNums = liftM (map read.words) getLine solve::[[String]]->Int solve [d] = 0 solve ds = let tab = zip (nub.sort.concat $ ds) [1..] rep x = case (lookup x tab) of Just i -> i ds' = map (map rep) ds in foldl1 min.map cost.map (head ds':).prod.map genAll.tail $ ds' cost = sum . map cost'. trans cost' xs = length xs - longest (sort xs) longest (h:ts) = foldl1 max.map snd $ scanl (\(x, c) y -> if y == x then (x, c+1) else (y, 1)) (h,1) ts trans s] = map (\x -> [) xs trans (xs:xss) = zipWith (:) xs $ trans xss prod s] = map (\x->[) xs prod (xs:xss) = concat.map (\x -> map (x:) (prod xss)) $ xs -- generate all dice equivalent to the die by rotation genAll = concat . map rots2 . rots1 -- rotations around an axis (the front surface is fixed) rots2 [x1,x2,x3,x4,x5,x6] = [[x1,x2,x3,x4,x5,x6], [x1,x3,x5,x2,x4,x6], [x1,x5,x4,x3,x2,x6], [x1,x4,x2,x5,x3,x6]] -- rotations to move each surface to the front rots1 [x1,x2,x3,x4,x5,x6] = [[x1,x2,x3,x4,x5,x6], [x2,x6,x3,x4,x1,x5], [x3,x2,x6,x1,x5,x4], [x4,x2,x1,x6,x5,x3], [x5,x1,x3,x4,x6,x2], [x6,x5,x3,x4,x2,x1]]
- Comments: 0
- TrackBack (Close): -
forall A
Haskell で forall A. A -> A 系の型を作ってみる.まずもっとも単純に.
let x = x
t を型変数として x :: t で,undef 以外の何者でもない気がする.
んで,次.
let f x = x
これで f :: t->t . id 関数なような.
続いて
let y f = f (y f)
これで y :: (t->t)->t . fixpoint 関数とうか Y コンビネータなような.
ついでに,
let g y z = if True then y else z
とすると g :: t->t->t になる.意味のある関数ではないが... さて,これ以降はどうなるのだろうか?
ついでなので,forall a,b,... . a -> b -> ... も作ろうとすると
let f x y = f x y
とかで引数の数を増やせばいくらでもいける.意味はないけど.意味のあるものってどれくらいあるんだろう? undef, id, fixpoint 以外に意味のあるのがあるか?
- Comments: 0
- TrackBack (Close): -