HaskellでABC463を解く

はじめに

今週はC問題まで解けました。D問題の解法全く全く思いつかないのでE問題に行き
用意していたダイクストラ法のテンプレートを使って提出までしましたがTLEでした。
スーパーノードという方法は前に見たことあったんですがコンテスト中は思いつかずでした。

A問題

Haskellでは分数型が使える利点を活かして分数のまま比較します。

A問題提出

main = do
  [x,y] <- readInts
  let ratio = x % y :: Ratio Int
  putStrLn $ bool "No" "Yes" $ ratio == 16 % 9

B問題

縦横を並び替えて'o'が含まれるかを調べます。

B問題提出

main = do
  [sn,sx] <- readToken
  let n = read sn :: Int
  ss <- replicateM n getLine
  let tt = transpose ss
  let idx = ord (head sx) - ord 'A'
  putStrLn $ bool "No" "Yes" $ 'o' `elem` (tt !! idx)

C問題

ハマりかけましたが無事解けました。
Queryは先読みしておいて前から処理することで逐次的に判断ができます。

C問題提出

main = do
  n <- readLn :: IO Int
  lhs <- replicateM n $ do
    [h,l] <- readInts
    return (l,h)
  let m = IM.fromListWith max lhs -- 同じ時刻の場合は大きい方をキープ
  -- 後ろから処理して大きいのが出たらそちらをとる
  let tbl = solve $ sortBy (flip compare) $ IM.assocs m
  let lhs' = sort $ solve tbl
--  print lhs'
  q <- readLn :: IO Int
  ts <- readInts
  let ts' = sort $ zip ts [1..]
--  print lhs'
--  print ts'
  let ans = sortBy (compare `on` snd) $ solve2 lhs' ts'
  putStr $ unlines $ map show $ map fst ans

solve tbl = step 0 tbl
  where
    step _mn [] = []
    step mn (lhi@(l,h):lhs)
      | h > mn = lhi : step h lhs
      | otherwise = step mn lhs

solve2 _lhs0 [] = []
solve2 [] _tis0 = [] -- error
solve2 lhs0@((l,h):lhs) tis0@((t,i):tis)
  | t < l = (h,i) : solve2 lhs0 tis
  | otherwise = solve2 lhs tis0

おわりに

まかり間違ってE問題が解けそう！と思いましたがTLEするやり方してしまってました。残念。