HaskellでABC436を解く

はじめに

ABC436に参加しました。
コンテスト中にオンラインジャッジにログインできなくなっていることに気がついて焦りつつの戦いになりました。

A問題

文字列を逆向きにして'o'を追加してn個分の文字を取り出して更に逆向きにするとOK。

main = do
  n <- readLn :: IO Int
  s <- getLine
  let t = reverse $ take n $ reverse s ++ repeat 'o'
  putStrLn t

A問題提出

B問題

問題の意図が分からず時間かかってしまいました。
最終的には理解は一旦置いておいて問題文のまま実装してACできました。

main = do
  n <- readLn :: IO Int
  let mp0 = M.fromList [((i,j),-1)| i <- [0..n-1], j <- [0..n-1]]
  let pos0 = (0,(n-1)`div`2)
  let mp = M.insert pos0 1 mp0 :: M.Map (Int,Int) Int
  let ans = step n (n*n-1) pos0 1 mp
  putStr $ unlines $ (map (unwords.(map show))) [[ans M.! (i,j) | j <- [0..n-1]]| i <- [0..n-1]]

step :: Int -> Int -> (Int,Int) -> Int -> M.Map (Int,Int) Int -> M.Map (Int,Int) Int
step n cnt (r,c) k mp
  | cnt == 0 = mp
  | mp M.! pos1 == -1 = step n (pred cnt) pos1 (succ k) (M.insert pos1 (succ k) mp)
  | otherwise = step n (pred cnt) pos2 (succ k) (M.insert pos2 (succ k) mp)
  where
    pos1 = ((r-1)`mod`n, (c+1)`mod`n)
    pos2 = ((r+1)`mod`n,c)

B問題提出

C問題

最初任意の大きさの正方形が足されると思いO(N)でどうやって重複を検出しようかと考えましたが結局4マスのチェックなので
コツコツチェックすれば良いということに気づいて配列でArrayを使って実装を開始。
実装終わったところでN=10e9なので配列での保持はサイズ的に無理となりSetで実装し直しました。
ギリギリTLEせずにACできてよかった。

main = do
  [n,m] <- readInts
  rcs <- replicateM m $ do
    [r,c] <- readInts
    return (r,c)

  print $ solve rcs

solve rcs0 = step 0 (S.empty) rcs0
  where
    step cnt _ [] = cnt
    step cnt m ((r,c):rcs)
      | any (flip S.member m) pos = step cnt m rcs
      | otherwise = step (succ cnt) m1 rcs
      where
        pos = [(r,c),(r+1,c),(r,c+1),(r+1,c+1)]
        m1 = S.union m (S.fromList pos)

C問題提出

おまけ

Online Judgeが使えなくてテスト時にコピペが必要でアセアセしました。対策は
以下のURLにまとめられていてコンテスト後に無事修正できました。

Online Judgeが使えなくなった時の対処

おわりに

D問題は通常のBFSにワープを組み込む方法をあれこれ試しましたが時間切れとなりました。残念。