HaskellでABC423を解く

はじめに

今回は案外Aに時間がかかってしまいました。C問題、D問題自力で間違いに気づいたので良しとしよう。D問題は同じ時刻に挿入することがあるな！と気づいたもののときには時間切れで insert を insertWithに書き換えただけで通りました。

A問題

多分こんなにややこしくなく解けるけど安全策でAC

ABC423A.hs

main = do
  [x,c] <- readInts
  let y = x * 1000 `div` (1000+c)
  let cands = [1000*(y`div`1000), 1000*((y+1000)`div`1000)]
--  print cands
  let ans = filter (\z -> z*(1000+c::Int)`div`1000 <= x) cands
  print $ head ans

提出

https://atcoder.jp/contests/abc423/submissions/69310968

B問題

扉が閉まっている間の部屋の数を数えるので両側の0を取り除いて
右端の1と左端の1の長さを数えればよい。
ただし途中に1が一つもない場合はコーナーケースとして処理しないといけない。

ABC423B.hs

main = do
  n <- readLn :: IO Int
  ls <- readInts
  let ls1 = dropWhile (==0) ls
  let ls2 = dropWhile (==0) $ reverse ls1
  let ans = length ls2
  if ans == 0 then
    print 0
  else
    print $ ans - 1

提出

https://atcoder.jp/contests/abc423/submissions/69315685

C問題

自分がいる位置を考慮できてなくてWAになっていた。自分がいる位置より外側の1だけを無視するようにすればよい。

ABC423C.hs

{-
 - 自分がいる位置を考慮しないといけない
 - 自分がいる位置の左右がずっと1だったとしても自分がいる位置までしか除去してはいけない
 -}

main :: IO ()
main = do
  [n,r] <- readInts
  ls <- readInts
  let xs = zip [1..] ls
  let ls1 = map snd $ dropWhile (\(i,l) -> i > r && l==1) $ reverse $ dropWhile (\(i,l) -> i <= r && l==1) xs
  let closes = length $ filter (==1) ls1
  print $ closes + length ls1

提出

https://atcoder.jp/contests/abc423/submissions/69331325

D問題

時間内提出には間違いに気づけず。考え方は合ってたが同じ時刻に複数のお客さんが追加されることを考慮できてなかった(WAのときはinsertWith を insert としていた)。

ABC423D.hs

main = do
  [n,k] <- readInts
  abcs <- replicateM n $ do
    [a,b,c] <- readInts
    return (a,b,c)
  putStr $ unlines $ map show $ solve k 0 IM.empty abcs

solve :: Int -> Int -> IM.IntMap Int -> [(Int,Int,Int)] -> [Int]
solve _ _ _ [] = []
solve k tBase im abc@((t0,dt,c):abcs)
  | c <= k = max tBase t0 : solve (k-c) (max tBase t0) (IM.insertWith (+) (max tBase t0+dt) (-c) im) abcs
  | otherwise = solve (k-c1) (max tBase t1) im1 abc
  where
    ((t1,c1),im1) = IM.deleteFindMin im

提出(提出10分オーバー)

https://atcoder.jp/contests/abc423/submissions/69350286

再提出

IntMapをHeapに変更。Heapの場合はIntMapのinsertのように上書きされて消えることもない。
https://atcoder.jp/contests/abc423/submissions/69358985

おわりに

C、D問題はすんなりACできず残念でした。自力で間違いには気づけたので良しとしよう。