ゆるふわブログ

プログラミング,大学の勉強,日常生活で感じたことをゆるふわに書いていけたらなと思います.技術的に拙いところがあっても温かい目で見守っていただければ幸いです.

AtCoder Beginner Contest 105 (by Haskell)

はい。

A AtCoder Crackers

問題よく読んでなかったですが 0 か 1 しかない感。

import Control.Applicative ((<$>))

fi = fromIntegral

main :: IO ()
main = do
  [n,k] <- map read . words <$> getLine :: IO [Int]
  print $ if min (ceiling (fi n/fi k)*k-n) (n-(n`div`k)*k) > 0
    then 1
    else 0

B Cakes and Donuts

ループ回して探索すれば良いと思います。

main :: IO ()
main = do
  n <- readLn :: IO Int
  putStrLn $ if null $ filter (\i -> i*4 <= n && (n-i*4)`mod`7 == 0) [0..n]
    then "No"
    else "Yes"

C Base -2 Number

なんかよく考えたら 2 進数もどきなのでどうとでもなった気がするが、頭が死んでいたので愚直にやった。divMod と quotRem 的な罠にはまった() anamorphism です。

import Data.List
import Data.Char

div' :: Int -> Int -> Int
div' a b
  | a`mod`b == 0 = a`div`b
  | otherwise    = a`div`b+1
  
mod' :: Int -> Int -> Int
mod' a b
  | a`mod`b==0 = 0
  | otherwise  = a`mod`b-b

f :: Int -> Maybe (Char, Int)
f i
  | i == 0    = Nothing
  | i == 1    = Just ('1',0)
  | otherwise = Just (chr (ord '0'+(i`mod'`(-2))), i`div'`(-2))

main :: IO ()
main = do
  n <- readLn :: IO Int
  let cs = unfoldr f n

  putStrLn $ if null cs
    then "0"
    else foldl' (\ans c -> c : ans)  "" cs

D Candy Distribution

一瞬アレっとなりました。C++ で AC してから Haskell で書き直した…
まあ累積和を取るところ、mod M で考えるところまではパッと出てくると思います。
制約をみると O(N^2) で探索させる気はないので、線形オーダーでどうにかできればうれしい。
区間 [i,j) の和が S[j]-S[i] で表せることを思えば、S[i] を mod M の値で分類し、頻度を数えれば良いことがわかります。(S[i] と S[j] の mod M が同じ時その差は M の倍数。mod M が同じものから異なる 2 つを選ぶ場合の数)
mod M が 0 の場合は自身だけを選ぶ場合も含まれることに注意。

import Control.Applicative ((<$>))
import Data.List

main :: IO ()
main = do
  [n,m] <- map read . words <$> getLine :: IO [Integer]
  as <- map read . words <$> getLine :: IO [Integer]
  let
    ss = map (`mod` m) $ scanl1 (+) as
    cs = map (\i -> (head i,genericLength i)) $ group $ sort ss

  print $ sum $ map (\(i,c) -> c*(c-1)`div`2 + (if i == 0 then c else 0)) cs

なんとなく行列を思い浮かべて、対角成分と上三角成分のようなイメージが湧いた()
直交行列の群 O(n) が Cayley 変換により n(n-1)/2 次元の Lie 群とみなせることを思い出して終了しました((((