pekempeyのブログ

A 問題

-- Exec time: 2 ms
-- Memory usage: 508 KB
{-# LANGUAGE ScopedTypeVariables #-}
import Data.Bits
main = getLine >>= print . foldl1 xor . map (read :: String -> Int) . words


B 問題

あまり面白くない書き方。

-- Exec time: 6 ms
-- Memory usage: 1148 KB
import Control.Applicative
import Data.Char

main = do
[h, w] <- map read . words <$> getLine g <- replicateM h getLine mapM putStrLn . solve$ g

solve :: [String] -> [String]
solve g = [[f i j | j <- [0..w-1]] | i <- [0..h-1]]
where
h = length g
w = length . head $g inside :: Int -> Int -> Bool inside i j = 0 <= i && i < h && 0 <= j && j < w f :: Int -> Int -> Char f i j | g !! i !! j == '#' = '#' | otherwise = intToDigit . length . filter (\(ii, jj) -> g !! ii !! jj == '#')$ adj
where adj = [(ii, jj) | ii <- [i-1..i+1], jj <- [j-1..j+1], inside ii jj]


C 問題

DFS せずに行列でやった。

-- Exec time: 752 ms
-- Memory usage: 10508 KB
import Control.Applicative
import Data.List

main = do
[n, m] <- map read . words <$> getLine es <- map (map pred . map read) . map words <$> replicateM m getLine
print . length . filter (isBridge n es) $es isBridge :: Int -> [[Int]] -> [Int] -> Bool isBridge n es [u, v] = not . (!! v) . (!! u) . foldl1' mul . replicate n$ toMatrix n (delete [u, v] es)

toMatrix :: Int -> [[Int]] -> [[Bool]]
toMatrix n es = [[f i j | j <- [0..n-1]] | i <- [0..n-1]]
where
f :: Int -> Int -> Bool
f i j
| i == j    = True
| otherwise = [i, j] elem es || [j, i] elem es

mul :: [[Bool]] -> [[Bool]] -> [[Bool]]
mul a b = [[foldl1' (||) $zipWith (&&) x y | y <- transpose b] | x <- a]  D 問題 こういうのは書きやすいね。 -- Exec time: 815 ms -- Memory usage: 2428 KB import Control.Applicative import Control.Monad import Data.List main = do [n, k] <- map read . words <$> getLine
xy <- map (map read) . map words <$> replicateM n getLine print$ solve xy k

solve :: [[Int]] -> Int -> Int
solve xy k = minimum . map (\(x1, y1, x2, y2) -> (x2 - x1) * (y2 - y1)) . filter ((>= k) . count xy) $bs where [xs, ys] = transpose xy bs = [(x1, y1, x2, y2) | x1 <- xs, x2 <- xs, y1 <- ys, y2 <- ys, x1 < x2, y1 < y2] count :: [[Int]] -> (Int, Int, Int, Int) -> Int count xy (x1, y1, x2, y2) = length . filter (\[x, y] -> x1 <= x && x <= x2 && y1 <= y && y <= y2)$ xy