Haskell: ABC075

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 Control.Monad
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 Control.Monad
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