2010-05-08 [長年日記]
λ. Google Code Jam 2010 Qualification Round
問題はそんなに難しい問題ではなかったのだけど、思いの他苦戦してしまった。 次のラウンドには一応進めたけれど、感覚が鈍ってるなぁ……
A. Snapper Chain
3問のうち一番苦戦したのがこの問題。 最初に書いたのは以下のようなプログラムで、Smallは簡単に解けるのだけど、Largeの上限のデータとかを生成して食わせると、とても終了しない。
{-# LANGUAGE Rank2Types, ScopedTypeVariables #-}
import Data.Array.ST
import Control.Monad
import Control.Monad.ST
import Text.Printf
f :: forall st. Int -> Int -> ST st Bool
f n k = do
(power :: STUArray st Int Bool) <- newArray (1,n+1) False
(state :: STUArray st Int Bool) <- newArray (1,n) False
let updatePower = do
writeArray power 1 True
forM_ [2..n+1] $ \pos -> do
b1 <- readArray power (pos - 1)
b2 <- readArray state (pos - 1)
writeArray power pos (b1 && b2)
updateState = do
forM_ [1..n] $ \pos -> do
isPowered <- readArray power pos
when isPowered $ do
isON <- readArray state pos
writeArray state pos (not isON)
updatePower
forM_ [1..k] $ \_ -> updateState >> updatePower
readArray power (n+1)
main :: IO ()
main = do
t <- readLn
forM_ [(1::Int)..t] $ \i -> do
[n,k] <- liftM (map read . words) $ getLine
printf "Case #%d: %s\n" i (if runST (f n k) then "ON" else "OFF")
Largeサイズの入力を扱えるようにと数回プログラムを書き直したが、その途中でトレースを表示して、初めて二進数のインクリメントになっている事に気づいた。 問題文の文章にちょっと騙された。
import Control.Monad
import Text.Printf
import Data.Bits
f :: Int -> Int -> Bool
f n k = and [testBit k i | i<-[0..n-1]]
main :: IO ()
main = do
t <- readLn
forM_ [(1::Int)..t] $ \i -> do
[n,k] <- liftM (map read . words) $ getLine
printf "Case #%d: %s\n" i (if f n k then "ON" else "OFF")
B. Fair Warning
Bは個人的には3問の中で一番簡単で、特に工夫は必要なかった。
import Control.Monad
import Text.Printf
f :: [Integer] -> Integer
f ts = (t - ((ts !! 0) `mod` t)) `mod` t
where t = g ts
g :: [Integer] -> Integer
g ts = foldl1 gcd [ti - tj | ti <- ts, tj <- ts, ti > tj]
main :: IO ()
main = do
c <- readLn
forM_ [(1::Int)..c] $ \i -> do
(n:ts) <- liftM (map read . words) $ getLine
printf "Case #%d: %d\n" i (f ts)
【2010-05-27追記】 Google Code Jam 2010 Qualification Round — Scratch Leaf — MAYAH.JP によれば、上のソースのgは以下のようにすれば十分で、より少ない計算量で出来たらしい。そりゃそうだ。
g :: [Integer] -> Integer g ts = foldl1 gcd [ti - t0 | ti <- ts', ti /= t0] where (t0:ts') = sort ts
C. Theme Park
最初に書いたのはC.hs。 Smallは当然解けるのだけど、甘い見積もりでLargeをダウンロードしてしまったら、時間内に解けなくて撃墜。 ちょっと工夫して、テーブル化して高速なべき乗法を使うようにしたら解けた(C2.hs)。 Largeはちゃんと性能的にも解けると確信してからダウンロードしないと駄目だなぁ。勿体無いことをした。 これは実際に参加してみて初めて感じた点。
【追記】 誰かがこの問題についてTwitterで「鳩ノ巣原理の良い例題」と書いていて*1、そのときは意味が分からなかったけど、後でku-ma-meさんに説明していて、そういう方法もあったと気づいた。
*1 今探したら残念ながら見つからなかったけど
2010-05-14 [長年日記]
λ. 「真理の度合理論は適切か？ 〜ファジイ論理と真理理論〜」 by 矢田部俊介
ytbさんに一度直接お会いしてみたくて、講演を聞きに行った。
本発表では、ファジイ論理の『真理値』の解釈の問題を題材に、真理に関する意味論的な見方と、公理論的な見方が対立する例を紹介する。
ファジイ論理は、『真理値』として[0,1]の実数をとる意味論によって定義され、その真理概念は伝統的に「真理の度合理論」によって説明されてきた。しかし、その『真理値』が何を意味しているかを巡っては、Suzko とDummett による議論以来、論争が続いている。発表者は、この問題に関し、搦め手からアプローチする。すなわち、「真理の度合い」を、ファジイ論理（の一例であるLukasiewicz無限値述語論理）上の公理的真理理論の枠組みでによって定式化し、形式化された度合い理論が（枠組みの真理理論がω-矛盾であることにより）成立しないことを示す。この結果は、公理的真理理論における真理概念は度合理論では説明できないことを示すものであり、[0,1]を真理値ととらえる意味論的な見方に否定的な結果であるといえる。
2010-05-15 [長年日記]
2010-05-17 [長年日記]
λ. A,O,B,ABの比率が4:3:2:1として、任意に4人集めたときにその全員の血液型が異なる確率
A,O,B,ABの比率が4:3:2:1として、任意に4人集めたときにその全員の血液型が異なる確率
finalfusionさんの問題が面白そうだったので、素朴な確率モナドを使って、Haskellで簡単に解いてみた。
import Data.List (nub)
import qualified Data.Map as M
import Control.Monad
newtype Fractional w => P w a = P{ runP :: [(a, w)] }
instance Fractional w => Monad (P w) where
return a = P [(a, 1)]
m >>= f = P $ do
(a,p) <- runP m
(b,q) <- runP (f a)
return (b, p*q)
random :: Fractional w => [(a,Integer)] -> P w a
random xs = P [(a, fromInteger w / s) | (a,w) <- xs ]
where s = fromInteger $ sum (map snd xs)
data BloodType = A | O | B | AB deriving (Show, Eq)
bloodtype :: Fractional w => P w BloodType
bloodtype = random [(A,4),(O,3),(B,2),(AB,1)]
problem :: Fractional w => P w Bool
problem = do
xs <- replicateM 4 bloodtype
return $ length (nub xs) == 4
ans :: Double
ans = M.fromListWith (+) (runP problem) M.! True
ψ たけを [手計算ですぐ求まるような。]
ψ みはら [答えはいくつですか〜？]
ψ さかい [＞たけをさん 手段の方が目的だったので、深く考えてなかったんですが、確かに。 ＞みはらさん 落ち着いて考えれば、す..]
ψ みはら [いやー、もう仕事でいっぱいいっぱいでー＞＜ 答えが知りたかったんです。解いてないですが。 落ち着いたら考えますね〜]
ψ さかい [お仕事お疲れ様です。 楽しみを奪っちゃ悪いけど、一応答えだけ書いておくと 36 / 625 = 0.0576 のはず..]
ψ みはら [結構低いんですね！]
ψ さかい [さすがに全員違う確率ですからね。 でも、こういう確率の問題って、自分の直観があてにならなくて、好きです。]
2010-05-22 [長年日記]
λ. Google Code Jam 2010 Round 1A
Aでしょうもないバグで悩んで時間がなくなり、結局Aしか解けなかった orz せめて、あとBのsmallくらいは解きたかったなぁ。1B,1Cで再挑戦か……
A. Rotate
単に言われている通りに書けば良いだけなのだけど、すべての直線の列挙をもれなく列挙する部分にバグを入れてしまって、随分と時間を食ってしまった。A.hs
B. Make it Smooth
どうやって解いたら良いか、全く思いつかなかったんだけど、後でku-ma-meさんに話したら、あっさり方針をたててくれたので、それに従って解いてみた(B.hs)。 これは私には時間内に解ける気がしないなぁ。
最初、B-small-practice.in は解けたと思ったら、B-large-practice.in では incorrect になり、どこを間違ったんだろうと随分悩んでしまった。 何故か、i≧mだったら挿入を利用しても意味がないと思い込んでいたのが原因だったので、修正 (上のコードは修正済み)。
C. Number Game
後で解く。
λ. Real World Haskell読書会 2010-05
今月は12章バーコード認識の続きっぽい。先月は、CLTT読書会第一回と重なっていてそっちに行ってしまったので、RWH読書会は久しぶり。
λ. Google Code Jam 2010 Round 1B
Bで悩んでしまい、またもやAしか解けなかった orz 残すは1Cのみ……
A. File Fix-it
何も考えずに、STモナドで命令的に書いた。 A.hs
B. Picking Up Chicks
後で解く。
C. Your Rank is Pure
本番中は難しそうだなと思って手をつけていなかったけれど、後からPracticeで解いてみたら、案外簡単だった。C.hs
smallは普通にDPで解けて、largeは組み合わせの計算をメモ化したら、時間内に解けた。 けど、100003のモジュロというので安心して32bit整数で計算してたら、乗算で32bitの範囲を超えるケースがあるのを見落としていて、一回Incorrectになってしまった。
2010-05-23 [長年日記]
λ. Google Code Jam 2010 Round 1C
1CはなんとかC-large以外を解くことが出来た。
- Rank
- 189
- Score
- 76
- Penalty
- 1:59:35
1A,1Bでパス出来ずに諦めかけていたが、ラストチャンスの1Cでなんとかなった。危なかった……
それから、Code Jam 2010 Statistics · Language Details: Haskell によると、Round 1C に参加していた Haskeller の21人の中ではトップだったらしい。ちょっと嬉しい。
A. Rope Intranet
両側で大小関係が入れ替わっているような組の数を数えればよいだけ。
import Control.Monad
import Text.Printf
pairs :: [a] -> [(a,a)]
pairs [] = []
pairs (x:xs) = [(x,y) | y <- xs] ++ pairs xs
f :: [(Int,Int)] -> Int
f xs = length $ do
((a1,b1),(a2,b2)) <- pairs xs
guard $ signum (a1-a2) /= signum (b1-b2)
return ()
main :: IO ()
main = do
t <- readLn
forM_ [(1::Int)..t] $ \x -> do
n <- readLn
xs <- replicateM n $ liftM ((\[x,y] -> (x,y)) . map read . words) getLine
printf "Case #%d: %d\n" x (f xs)
B. Load Testing
元の区間を最終的に何個の領域で分割・被覆できるかを考えて、そのためには二分割を何段階繰り返せば良いかを考える。
ceiling (logBase 2 (logBase C (P/L))) みたいな値だとは思ったけど、念のため整数演算で計算。後から、naoya_tさんの記事で「対数空間で二分探索する感じ」と書いてあるのを見て、「なるほど。そうまとめられるのか」と思った。
import Control.Monad
import Text.Printf
f :: Integer -> Integer -> Integer -> Integer
f l p c = head [m | (m,x) <- zip [0..] (iterate (2*) 1), n <= x]
where n = head [n | (n,x) <- zip [0..] (iterate (c*) l), p <= x]
main :: IO ()
main = do
t <- readLn
forM_ [(1::Int)..t] $ \x -> do
[l,p,c] <- liftM (map read . words) getLine
printf "Case #%d: %d\n" x (f l p c)
C. Making Chess Boards
ナイーブに解いたらsmallは解けた。 largeの最大サイズの入力を適当に生成して食わせてみたら終わらなかったのだけど、最適化とかを考えているうちに残り時間がなくなったので、ダメ元でlargeのデータをダウンロードしてやっぱりダメだった。 後からnaoya_tさんの記事を読んで、そうやれば良かったのかと思った。
【2010-07-07 追記】 書き直して解けた。 C2.hs
