HaskellでABC456を解く

はじめに

今回はCまで解けました。DはDPでしたが解説読むとやっていることはわかりますがなかなか思いつけないです。

A問題

カードを3枚選ぶので合計は3から18までの数字にはなり得ます。

A問題提出

main = do
  x <- readLn :: IO Int
  putStrLn $ bool "No" "Yes" $ x >= 3 && x <= 18

B問題

すべての組み合わせを作って [4,5,6]と一致するものをカウントしてすべての組み合わせの数との比率を計算します。

B問題提出

main = do
  as <- readInts
  bs <- readInts
  cs <- readInts
  let counts = length $ filter (\[a,b,c] -> [a,b,c]==[4,5,6] ) $ map sort [[a,b,c] | a <- as, b <- bs, c <- cs]
  printf "%.16f\n" $ ((fromIntegral counts) / fromIntegral (6*6*6)::Double)

C問題

解説では組み合わせ数を使ってスマートに解かれてましたが尺取り法で解きました。最初と最後の追加と削除があるのでSequenceを使用しました。

C問題提出

shakutori p op invOp identity as = go as as 0 identity
  where
    go lls@(l:ls) [] len res = len : go ls [] (len-1) (invOp res l)
    go lls@(l:ls) rrs@(r:rs) len res
      | p l r res = go lls rs (len + 1) (op res r) -- 条件を満たす場合lを固定したままrを進める
      | len == 0 = 0 : go ls rs 0 identity -- 長さが0になったら長さは0のままlもrも進める
      | otherwise =  len : go ls rrs (len-1) (invOp res l) -- 条件を満たさない場合、これまでの長さを出力し、長さを1つへらし、invOpをやって次のステップへ
    go _ _ _ _ = []

main = do
  s <- getLine

  let ans = solve s
  print $ modSum 0 ans

solve s = do
  let identity = Seq.empty
  -- Queue (1 :<| seq) (seq :|> 1) (1 <| seq) (seq |> 1)
  let can _l r res = case Seq.viewr res of
                      Seq.EmptyR -> True
                      _res Seq.:> a -> a /= r
  let push res r = res Seq.|> r
  let pop res _l = case Seq.viewl res of
                    Seq.EmptyL -> error "error"
                    _a Seq.:< res1 -> res1

  let lens = shakutori can push pop identity s
  lens

modSum sm [] = sm
modSum sm (x:xs) = modSum sm1 xs
  where
    sm1 = (sm+x) `mod` 998244353

D問題

いつもDPはなかなか解き方思いつかないです。
今回は、連続した個数ではないので尺取り法ではないし、
組み合わせで求めるのも違うし、DPかなくらいは思いましたが
具体的なやり方思いつけずでした。

D問題提出

main = do
  s <- getLine
  print $ solve s


solve = dp (0,0,0)
  where
    dp (a,b,c) [] = modPlus [a,b,c]
    dp (a,b,c) (x:xs)
      | x == 'a'  = dp (modPlus [a,b,c,1], b, c) xs
      | x == 'b'  = dp (a, modPlus [a,b,c,1], c) xs
      | otherwise = dp (a, b, modPlus [a,b,c,1]) xs

modPlus = foldl' (\acc x -> (acc+x)`mod` 998244353) 0

おわりに

GWはDPの精進に使おう。
総評