HaskellでABC422を解く

はじめに

C問題できそうでできずハマってしまい良くないパターンでした。D問題はギリギリ提出間に合わず。数分遅れでACできたが早々にC問題に見切りをつけられたら良かったと反省。

A問題

一旦１次元の添字(0-indexed)に直してインクリメントした後２次元の添字に戻す

ABC422A.hs

main = do
  s <- getLine
  let i = pred $ read @Int [head s]
  let j = pred $ read @Int [last s]

  let k = succ $ i * 8 + j

  let l = succ $ k `div` 8
  let m = succ $ k `mod` 8

  putStrLn $ show l ++ "-" ++ show m

提出

https://atcoder.jp/contests/abc422/submissions/69099445

B問題

Immutableな配列でBlackなセルにおいて4方向を調べ近所のBlackセルの個数が2または4あるかを調べる。

ABC422B.hs

main = do
  [h,w] <- readInts
  ss <- replicateM h getLine
  let grid = AU.listArray ((1,1),(h,w)) $ concat ss :: AU.UArray (Int,Int) Char
  let ans = solve grid (h,w) [(i,j) | i <- [1..h], j <- [1..w]]
  putStrLn $ bool "No" "Yes" ans

solve :: AU.UArray (Int,Int) Char -> (Int,Int) -> [(Int,Int)] -> Bool
solve _ _ [] = True
solve grid (h,w) ((i,j):ijs)
  | grid AU.! (i,j) == '.' = solve grid (h,w) ijs
  | blacks == 2 || blacks == 4 = solve grid (h,w) ijs
  | otherwise = False
  where
    neighbors = [(k,l) | (k,l) <- [(i+1,j),(i-1,j),(i,j+1),(i,j-1)], AU.inRange (AU.bounds grid) (k,l)]
    blacks = length $ filter (=='#') $ map (grid AU.!) neighbors

提出

https://atcoder.jp/contests/abc422/submissions/69108068

C問題

ドハマリしてしまった。解説読むとそうだよなと思うが解いてる最中はなんとも正解にたどり着けず。

ABC422C.hs

main = do
  n <- readLn :: IO Int
  replicateM_ n $ do
    [a,b,c] <- readInts
    let ans = minimum [a,c, (a+b+c)`div`3]
    print ans

提出(写経)

https://atcoder.jp/contests/abc422/submissions/69136638

提出（解説を参考に二分探索で解き直し）

https://atcoder.jp/contests/abc422/submissions/69150029

D問題

時間内提出には間に合わず。
やリ方はなるべく均等に配分していくという素直なもの。
TLEにならないか心配したが案外すっと解けました。

ABC422D.hs

main = do
  [n,k] <- readInts
  let x = 2^n
  -- 単純になるべく均等に２等分していけばよい
  print $ if k `mod` x == 0 then 0 else 1 -- アンバランスは1以下にできる
  -- なるべく余りを離して２分木のように配置していかないといけない
  let ans = last $ take (n+1) $ iterate f [k]
  putStrLn $ unwords $ map show ans

f [] = []
f (x:xs) = (x`div`2):(x-(x`div`2)) : f xs

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

https://atcoder.jp/contests/abc422/submissions/69136102

おわりに

C問題のような簡単そうでハマる問題やD問題のように一見ややこしそうで案外簡単な問題を上手く見極められるようになりたい。