たすのーと - ABC419振り返り

AtCoder Beginner Contest 419に参加したので振り返り。

ABCDの4完だったけど、いずれも簡単で多くの人に解かれていたので、パフォーマンスは大きくならず。

A - AtCoder Language

場合分けするだけでOK。

main :: IO ()
main = do
    ss <- getLine

    putStrLn $ case ss of
        "red" -> "SSS"
        "blue" -> "FFF"
        "green" -> "MMM"
        _ -> "Unknown"

B - Get Min

やることは明快だけど、色々躓いてしまった。。。

最初 Data.IntSet で管理すればよい¹かなと思ったけど、同じ整数が書かれたボールが複数存在しうるので、多重集合 IntBag で管理する（ IntBag は自作ライブラリとして用意している）。

これでOKかと思いきや、クエリ \(2\) は取り出したボールを除去する必要があることに気づかず、サンプルが通らなくてちょっと焦ってしまった。

main :: IO ()
main = do
    q <- val ucInt
    qs <- listN q ucInt

    let f :: IntBag  -> [Int] -> IO IntBag
        f is query = case query of
            [1,x] -> return $ insertIB x is
            [2] -> do
                let r = fst $ fromJust $ lookupMinIB is
                print r
                return $ deleteIB r is
            _ -> notComeHere

    void $ foldlM f emptyIB qs

これでめでたしめでたし、 IntBag 用意しておいてよかった・・・なのだけど、想定解はpriority queueだった。思いつかなかったのはちょっと悔しい。

C - King's Summit

各辺がグリッドに沿った、すべての人を含む長方形のうち最小のものを考える。

全員が集まるマスの座標を \((R,C)\) とすると、直感的には長方形の中心（付近）が時刻最小となるマスになりそうである。

ここで、各人の移動先は \(8\) 近傍であることから、 \((R_i,C_i)\) から \((R,C)\) に移動するのにかかる時間は \(\max \ (|R_i - R|, |C_i - C|)\) である（ \(4\) 近傍なら \(|R_i - R| + |C_i - C|\) である）。

したがって、求めるものは

\[\begin{equation} \max_{i=1\dots N} ( \max \ (|R_i - R|, |C_i - C|) ) \end{equation} \]

と書ける。

最大値を取る候補となるマスは、長方形の辺上に存在するマスなので、 \(R_i\) の最大値を \(R_{max}\) 、最小値を \(R_{min}\) 、 \(C_i\) の最大値を \(C_{max}\) 、最小値を \(C_{min}\) とすれば、求めるものは

\[\begin{equation} \max \ (|R_{max} - R|, |R_{min} - R|, |C_{max} - C|, |C_{min} - C|) \end{equation} \]

の \((R,C)\) についての最小値である。

\((R,C)\) として長方形内部の以下の点を取ると、最小値となる。これはほとんど長方形の中心だが、長方形の辺の長さが偶数の場合、長方形の中心はマスとマスの間にあることを考慮する。

\[\begin{equation} (R,C) = \biggl( \biggl\lceil \frac{R_{max} - R_{min}}{2} \biggr\rceil, \biggl\lceil \frac{C_{max} - C_{min}}{2} \biggr\rceil \biggr ) \end{equation} \]

main :: IO ()
main = do
    n <- val ucInt
    rcs <- int2list n

    let (rMax,rMin) = pair (maximum, minimum) $ map fst rcs
        (cMax,cMin) = pair (maximum, minimum) $ map snd rcs

    print $ max ((rMax - rMin + 1) `div` 2) ((cMax - cMin + 1) `div` 2)

D - Substr Swap

各位置ごとに、何回入れ替えが発生したかを高速に計算できれば良い（ \(x\) 番目の文字について、偶数回入れ替えなら \(S\) 、奇数回入れ替えなら \(T\) のものが選ばれる）。

いもす法を実装すれば良いということはすぐにわかったけど、肝心のいもす法の実装がごちゃついてしまった。うまい実装が思いつかず、結局 MArray を使って手続き的に実装した。

main :: IO ()
main = do
    (n,m) <- int2
    ss <- vector @VU.Vector n ucChar
    ts <- vector @VU.Vector n ucChar
    lrs <- int2list m

    let cum = runSTUArray do

           cumi <- newUArray (1,n+1) (0 :: Int)

           for_ lrs \(l,r) -> do
               modifyArray cumi l (1+)
               modifyArray cumi (r+1) (subtract 1)

           result <- newUArray (1,n) (0 :: Int)
           readArray cumi 1 >>= writeArray result 1

           for_ [2..n] \i -> do
               p <- readArray result (i-1)
               c <- readArray cumi i
               writeArray result i (p+c)

           return result


    for_ [1..n] \i -> do
        putStr $ if odd (cum ! i) then [ts VU.! (i-1)] else [ss VU.! (i-1)]

    putStrLn ""

コンテスト中は思いつかなかったが、 accumArray でさくっと実装できる²。

main :: IO ()
main = do
    (n,m) <- int2
    ss <- vector @VU.Vector n ucChar
    ts <- vector @VU.Vector n ucChar
    lrs <- int2list m

    let cum = listArray @UArray (1,n+1) $ L.scanl1 (+) $ elems $ accumArray @UArray @Int (+) 0 (1,n+1) $ concat [[(l,1),(r+1,-1)] | (l,r) <- lrs]

    putStrLn $ flip map [1..n] \i -> if odd (cum ! i) then ts VU.! (i-1) else ss VU.! (i-1)

感想など

AからDまではかなり簡単。早解きできていればよかったが、ちょいちょいつまづきがあって結局1時間かかってしまった。 Eも考えてみたが全く歯が立たず。解説を読むとDPと書いてあるが、どうやったら思いつくのか・・・ちゃんと考え方を理解してupsolveしよう。

ちなみに、現ジャッジ環境の containers ライブラリが古く、 IntSet には lookupMin が実装されていない（現環境の containers のバージョンは ^>=0.6.7 、 lookupMin が入ってるバージョンは 0.8 ）。↩︎
https://x.com/naoya_ito/status/1956722535401455830
コレ見たとき「あーたしかに！」となった（ zipWith3 の使い方も）。↩︎