AtCoder Regular Contest 039

A - A - B problem

3桁固定だと愚直に解ける。

main :: IO ()
main = getContents >>= print . solve . words

solve :: [String] -> Int
solve [ a@[ a0, a1, a2 ] , b@[ b0, b1, b2 ] ]
  = maximum [ read a' - read b' | (a', b') <- concat $ [ [ ([ k, a1, a2 ], b), (a, [ k, b1, b2 ]) ] | k <- ['1'..'9'] ] ++ 
                          [ [ ([ a0, k, a2 ], b), ([ a0, a1, k ], b), (a, [ b0, k, b2 ]), (a, [ b0, b1, k ]) ] | k <- ['0'..'9'] ] ]
solve _ = undefined

今回は3桁固定だからこんなのでいいけれど、一般に書き換え系はData.Arrayの(//)が便利です。

B - 高橋幼稚園

単に二項係数を取れば瞬殺である。これは簡単。

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

solve :: [Integer] -> Integer
solve [ n, k ] | n <= k = binomial n (k `mod` n) `mod` 1000000007
               | otherwise = binomial (n + k - 1) k `mod` 1000000007
solve _ = undefined

binomial :: Integral a => a -> a -> a
binomial n k | k <= 0 || n <= k || n <= 0 = 1
             | otherwise = product [k+1..n] `div` product [1..n-k]

C - 幼稚園児高橋君

最初に書いたのはこれ。Setに訪問済みを入れていく感じ。

import Data.List (foldl')
import qualified Data.Set as S
 
main :: IO ()
main = getLine >> getLine >>= putStrLn . (\(x, y) -> unwords [ show x, show y ]) . solve
 
solve :: String -> (Int, Int)
solve = snd . foldl' go (S.singleton (0, 0), (0, 0))
 
go :: (S.Set (Int, Int), (Int, Int)) -> Char -> (S.Set (Int, Int), (Int, Int))
go (s, (x, y)) c = f s (x + dx, y + dy)
  where (dx ,dy) | c == 'R' = (1, 0)
                 | c == 'U' = (0, 1)
                 | c == 'L' = (-1, 0)
                 | otherwise = (0, -1)
        f s' (x', y') | S.member (x', y') s' = f s'' (x' + dx, y' + dy)
                      | otherwise = (s'', (x', y'))
                      where s'' = S.insert (x', y') s

しかし、これだとTLEする。StringをByteStringにしたり、MapをHashMapにしたりしたけど無意味だった。どうやら、ある行に対する区間を記録していかなくてはいけないらしい。私には書けなかった。コンテスト中これをHaskellで通した人が一人いて、すごいと思った。うーん、頑張りたい。