HaskellでABC433を解く

はじめに

ABC433に参加しました。

A問題

(Y+a)*Z = X+a という式を展開し a = に直したときに分母が正かつ整数になっていればOK。分母はZ>=2の条件から必ず正なので気にしなくて良い。

main = do
  [x,y,z] <- readInts
  let a = (x - y*z)`mod`(z-1)
  if a == 0 && x - y*z >= 0 then
    putStrLn "Yes"
  else
    putStrLn "No"

A問題提出

B問題

Nが小さいので全探索で求める。自分の左側で自分より大きいものがあり一番最後に出てきたものが解になる。

main = do
  n <- readLn :: IO Int
  as <- readInts
  let bs = zip as [1..]
  let cs = solve [filter (\(x,j) -> j < i && x > a) bs | (a,i) <- bs]
  putStr $ unlines $ map show cs

solve [] = []
solve (a:as)
  | null a = -1 : solve as
  | otherwise = snd (last a) : solve as

B問題提出

C問題

ランレングス圧縮しておいて隣との関係で数を数えていけばよい。

main = do
  s <- getLine
  let ans = solve $ map (\g -> (head g, length g )) $ group s
  print ans

solve ((c1,l1):(c2,l2):cs)
  | x + 1 == y = min l1 l2 + solve ((c2,l2):cs)
  | otherwise = solve ((c2,l2):cs)
  where
    x = read @Int [c1]
    y = read @Int [c2]
solve _ = 0

C問題提出

おわりに

D問題は過去に似たような問題があってグループでまとめて処理すれば良さそうというところまで気づいたのですが実装うまく行かずでした。