AtCoder Beginner Contest 339 振り返り

前回のABC振り返りです。
※前回の記事はここ

今回の結果

A,C 2完でした。今回はB問題が難しかった。

各問題の振り返り

A - TLD

• 問題文
• 自分の回答
  '.'でsplitして最後の値を取ってくれば解けます。

main :: IO ()
main = do
  !s <- BC.getLine
  BC.putStrLn $ last $ BC.split '.' s

B - Langton's Takahashi

• 問題文
• 自分の回答(upsolved)
  問題文の通り愚直に解くだけなのですが、難しかった。
  こういう座標を移動して解く問題は慣れてない..
  自分はMArrayも使わず愚直に解いたのですが、意外と実行時間も20msくらいでした。
  直和型を使って上下左右方向のデータを持っておき、回転するたびに更新します。
  Arrayの境界を((1, 1), (h, w))としていたのですが、端からもう片方の端に移動する時に、素直にmodが使えず実装に時間がかかってしまいました。
  後で気づいたのですがArrayの境界を((0,0), (h-1, w-1))にしておけば素直にmodだけで計算できたので戦略ミスでした。

data Direction = U | D | L | R
type Grid = Array Position String
type Position = (Int, Int)
type Current = (Position, Direction)
main :: IO ()
main = do
  [h, w, n] <- readInputInts
  let !ans = simulate (h, w) n
  forM_ [1 .. h] (\i -> putStrLn $ concat [ans ! (i, j) | j <- [1 .. w]])
readInputInts :: IO [Int]
readInputInts = L.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
initGrid :: Position -> Grid
initGrid (h, w) = listArray @Array ((1, 1), (h, w)) $ repeat "."
updateGrid :: Grid -> Position -> Grid
updateGrid grid pos = grid // [(pos, updateColor color)]
  where
    updateColor c = if c == "." then "#" else "."
    color = grid ! pos
move :: Position -> Current -> String -> (Position, Direction)
move hw curr@(pos, dir) color = if color == "." then moveW hw curr else moveB hw curr
moveW :: Position -> Current -> (Position, Direction)
moveW (h, w) ((i, j), dir) =
  case dir of
    U -> (if j + 1 > w then (i, 1) else (i, j + 1), R)
    R -> (if i + 1 > h then (1, j) else (i + 1, j), D)
    D -> (if j - 1 < 1 then (i, w) else (i, j - 1), L)
    L -> (if i - 1 < 1 then (h, j) else (i - 1, j), U)
moveB :: Position -> Current -> (Position, Direction)
moveB (h, w) ((i, j), dir) =
  case dir of
    U -> (if j - 1 < 1 then (i, w) else (i, j - 1), L)
    L -> (if i + 1 > h then (1, j) else (i + 1, j), D)
    D -> (if j + 1 > w then (i, 1) else (i, j + 1), R)
    R -> (if i - 1 < 1 then (h, j) else (i - 1, j), U)
simulate :: Position -> Int -> Grid
simulate (h, w) n = go n ((1, 1), U) $ initGrid (h, w)
  where
    go 0 _ grid = grid
    go k curr grid =
      let grid' = updateGrid grid (fst curr)
          curr' = move (h, w) curr color
          color = grid ! fst curr
       in go (k - 1) curr' grid'

ちなみに、他の回答を見ると、座標更新するタイプの問題はMArrayを使うのが定石のようでした。
こちらの回答の見よう見まねで解いてみます。これだと2ms程度で実行できます。(提出先はここ)

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeApplications #-}
module Main where
import Control.Monad
import Data.Array.Base
import Data.Array.IO.Internals (IOUArray)
import qualified Data.ByteString.Char8 as BC
import qualified Data.Char as C
import Data.Ix ()
import qualified Data.List as L
import Data.List.Split
main :: IO ()
main = do
  [h, w, n] <- readInputInts
  !as <- newArray @IOUArray ((0, 0), (h - 1, w - 1)) '.'
  let f (pos@(x, y), (dx, dy)) _ = do
        !c <- readArray as pos
        if c == '.'
          then do
            writeArray as pos '#'
            let d'@(dx', dy') = (dy, -dx)
                pos' = (\(i, j) -> (i `mod` h, j `mod` w)) (x + dx', y + dy')
            return (pos', d')
          else do
            writeArray as pos '.'
            let d'@(dx', dy') = (-dy, dx)
                pos' = (\(i, j) -> (i `mod` h, j `mod` w)) (x + dx', y + dy')
            return (pos', d')
  foldM_ f ((0, 0), (-1, 0)) [1 .. n]
  !as'' <- freeze as :: IO (UArray (Int, Int) Char)
  mapM_ putStrLn $ chunksOf w (elems as'')
readInputInts :: IO [Int]
readInputInts = L.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine

ちなみに、Haskellのmodは

(x `div` y)*y + (x `mod` y) == x

を満たすように実装されています。(参考)
そのため、

(-1) `mod` 4

を実行すると

(x `mod` y) = x - ((x `div` y)*y)

となり、　

-1 `mod` 4 = -1 - ((-1) `div` 4) * 4
         = -1 - (-1 * 4) -- (-1) `div` 4 = -1 となる
         = 3     

となります。
このことから、i=0もしくはj=0からマイナス方向に移動するときも、modでもう片方の端に移動するように実装することが可能になります。

C - Perfect Bus

• 問題文
• 自分の回答
  こっちは簡単でした。全ての値が0以上でないといけないように初期値を決めるのがポイントになります。
• 累積和を取って一番小さい値をとり
  • 0より小さければ絶対値が初期値
  • 0以上であれば0が初期値
    で初期値を求めます。
    その後、初期値をバスに乗り降りする人のリストの先頭に加えて総和を取れば答えが得られます。
    ちなみに、B問題で焦ってたので何回かWAしてしまいました。

main :: IO ()
main = do
  _ <- readLn @Int
  !as <- readInputInts
  let !res = L.scanl1 (+) as
  let !minim = minimum res
  let !start = if minim < 0 then abs minim else 0
  print $ start + last res
readInputInts :: IO [Int]
readInputInts = L.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine

全体を振り返って

B問題のようなタイプの問題を解くのに慣れていなかったので非常に苦労しました。
ただ、今回の問題でMArrayの使い方がなんとなくわかったので収穫です。
Haskellも競プロも難しい。。