AtCoder Beginner Contest 040

atcoder

A - 赤赤赤赤青

n個の中の特定の一つのブロックを隣り合うブロックの入れ替えによって両端のいずれかに移動する最小の回数。

main :: IO ()
main = getContents >>= print . (\[n, x] -> min (x - 1) (n - x)) . map read . words

B - □□□□□

n個のタイルをどれだけたくさん使ってできる限り正方形に並べられるか。指標は二辺の差と使い切れなかったタイルの数の和が最小のもの。

main :: IO ()
main = readLn >>= print . solve

solve :: Int -> Int
solve n = minimum [ abs (l - k) + n - k * l | k <- [1..round (sqrt (fromIntegral n))], let l = n `div` k ]

C - 柱柱柱柱柱

柱を端から端まで飛び移っていく。一本飛ばしでも飛べるのだが、柱を飛び移るときに高さが違うだけ疲れるので疲れを最小にしたい。

import Data.List (foldl')

main :: IO ()
main = print . solve . tail . map read . words =<< getContents

solve :: [Int] -> Int
solve (a0:as) = fst $ fst $ foldl' f ((0, a0), (0, maxBound)) as
  where f ((x, ax), (y, ay)) az = (min (x + abs (ax - az), az) ((y + abs (ay - az)), az), (x, ax))

Array使ってDPしてもいいけど、せいぜい最後の二本の情報を持っていればよいのでそこまでする必要はないかな。一本飛ばしまでしかできないからそうだけど、何本飛ばしでもできて、過去の全てを使って新しいところの値が決まるという問題ならDPしたほうがよさそう。

D - 道路の老朽化対策について

重み付き無向グラフ上で、ある重み以上の道しか通れない時にどれだけの数のノードに辿り着けるか。

import Control.Monad (replicateM)
import Data.Graph (buildG, reachable)

main :: IO ()
main = do
  [n, m] <- getInts
  abys <- replicateM m (toTriple <$> getInts)
  q <- readLn
  vws <- replicateM q (toTuple <$> getInts)
  mapM_ print $ solve n abys vws

getInts :: IO [Int]
getInts = map read . words <$> getLine

solve :: Int -> [(Int, Int, Int)] -> [(Int, Int)] -> [Int]
solve n abys vws = [ length $ reachable gr v | (v, w) <- vws, let gr = buildGraph w ]
  where buildGraph w = buildG (1, n) $ concat [[(a, b), (b, a)] | (a, b, y) <- abys, y > w]

toTuple :: [a] -> (a, a)
toTuple xs = (head xs, xs !! 1)

toTriple :: [a] -> (a, a, a)
toTriple xs = (head xs, xs !! 1, xs !! 2)

すみません、Largeは通らないです。50点は取れた。本当は、最初に各ノード間の最小の重みを計算しないといけなさそうだけど、元気がなかった…