HaskellでABC460を解く

はじめに

今回はC問題まで解けました。D問題はBFSの実装しテストケースは通りましたがどうしてもWAとTLEが残ってしまい現時点でまだ解けていません。

A問題

問題文通りに演算し演算回数をカウントします。

A問題提出

main = do
  [n, m] <- readInts
  print $ solve n m 0

solve n m cnt
  | m == 0 = cnt
  | otherwise = solve n m' (succ cnt)
  where
    m' = n `mod` m

B問題

距離の2乗で比較することで整数で判定できます。ご判定してしまう状況を回避するのにだいぶタイムロスしてしまいました。

B問題提出

main = do
  t <- readLn :: IO Int
  replicateM_ t $ do
    [x1, y1, r1, x2, y2, r2] <- readInts
    let mxr = max r1 r2
    let mnr = min r1 r2
    -- 大きい円に小さい円が入り込んでいるか
    if dist2 (x1, y1) (x2, y2) < (mxr - mnr) ^ 2 -- 内部にある
      then
        putStrLn "No"
      else do
        if dist2 (x1, y1) (x2, y2) <= (r1 + r2) ^ 2
          then do
            -- 交わっている
            putStrLn "Yes"
          else do
            putStrLn "No"

dist2 (x1, y1) (x2, y2) =
  (x2 - x1) ^ 2 + (y2 - y1) ^ 2

C問題

AもBも大きい順にソートして取れるだけ取っていきます。考え方は素直でした。

C問題提出

main = do
  [_n, _m] <- readInts
  as <- sortBy (flip compare) <$> readInts
  bs <- sortBy (flip compare) <$> readInts
  print $ solve as bs 0

solve [] [] cnt = cnt
solve _as [] cnt = cnt
solve [] _bs cnt = cnt
solve aas@(a : as) bbs@(b : bs) cnt
  | b <= 2 * a = solve as bs (succ cnt)
  | otherwise = solve aas bs cnt

おわりに

D問題みたいなグラフ問題やり方まで考えられても実装時の不具合が解消できずなかなか上手く行きません。