たすのーと - ABC406振り返り

パナソニックグループプログラミングコンテスト2025（AtCoder Beginner Contest 406）に参加したので振り返り。

A - Not Acceptable

まず時間で比較し、同じなら分で比較。最初、締切時刻ぴったりに提出したときはどうするんだろうと思ったけど、制約上そうはならないね。

main :: IO ()
main = do
    (a,b,c,d) <- val ((,,,) <$> ucInt <*> ucInt <*> ucInt <*> ucInt)

    printYn $ c < a || c == a && d < b

B - Product Calculator

順番に掛け算していって、結果が \(10^K\) 以上（ \(K+1\) 桁以上）になったら \(1\) で置換する、というのを繰り返せば良い。オーバーフロー対策は、雑に Integer を使って実装。最初、 \(1\) が表示されたらその後はずっと \(1\) のままだと勘違いしてた。。。

main :: IO ()
main = do
    (n,k) <- int2
    as <- list1 ucInt

    let result = L.foldl1' f $ map fromIntegral as
            where f :: Integer -> Integer -> Integer
                  f x y = let r = x * y
                          in if r >= 10^k then 1 else r

    print result

当初、 \(A_{i-1} < A_i > A_{i+1}\) 、 \(A_{i-1} > A_i < A_{i+1}\) なる \(A_i\) 、つまり変化の山・谷となる箇所を求めればいいかなーと思ったけど、単純にそれだけ求めても、同じ変化の山・谷を含む数列は複数存在しうるためうまく行かない（入力例1が通らない）。変化の山・谷を含む範囲をしゃくとり法で求めるのかなと思ったけど、実装に自信がなかったので、一旦飛ばしてD問題へ。

再度Cにもどってきて、入力例の増減をいくつか紙に書いて眺めてみると、整数列の変化の山・谷の位置ではなく、増加列→減少列→増加列となっている区間を見れば良いことがわかる。このような区間において条件を満たす整数列の数は、左増加列の要素数を \(a\) 、右増加列の要素数を \(b\) として \(a\times b\) となる。

実装について、当初は2要素間を比較する専用の再帰関数を実装していたが、そのようなことをしなくても zipWith f xs (tail xs) で隣り合う要素を計算できる。増加列毎に要素数を数えておくと、こちらも同じ計算で整数列の数を数えられる。

main :: IO ()
main = do
    _ <- val ucInt
    as <- list1 ucInt

    let ys = map snd $ filter fst $ map (\x -> (head x, length x)) $ L.group $ zipWith f as (tail as)
            where f :: Int -> Int -> Bool
                  f x y | x < y = True
                        | x > y = False
                        | otherwise = error "Not come here"

    print $ sum $ zipWith (*) ys (tail ys)

D - Garbage Removal

コンテスト中は解法思いつかず。当初、各クエリについて1行or1列のゴミを削除してから各列or各行のゴミの有無を検査していると、計算量が大きくなりすぎて間に合わないと考えていたが、実際には行毎or列毎に残っているゴミを管理しておけば愚直に計算できる。計算量は、1行or1列のゴミを削除する処理が \(O(Q)\) 、行毎or列毎に残っているゴミを管理する処理が \(O(N)\) で、合計 \(O(N+Q)\) 。

解説を読んで愚直とわかりがっかり・・・こういうのはコンテスト中に思いつきたい。

残っているゴミを管理するのに Data.IntSet を使っているが、 Data.IntSet.size は \(O(n)\) の計算量なので、残っているゴミの数も一緒に管理すると良さげ（全体の計算量には影響しないけど・・・）。

main :: IO ()
main = do
    (h,w,n) <- int3
    xys <- int2list n
    q <- val ucInt
    queries <- int2list q

    xary <- newArray @IOArray (1,h) (0 :: Int, IS.empty)
    yary <- newArray @IOArray (1,w) (0 :: Int, IS.empty)

    for_ xys $ \(x,y) -> do
        modifyArray xary x (cross ((+1), IS.insert y))
        modifyArray yary y (cross ((+1), IS.insert x))

    for_ queries $ \query -> do
        case query of
            (1,x) -> do
                (c,s) <- readArray xary x
                print c
                writeArray xary x (0,IS.empty)
                unless (c == 0) $ for_ (IS.toList s) $ \y -> modifyArray yary y (cross (subtract 1, IS.delete x))
            (2,y) -> do
                (c,s) <- readArray yary y
                print c
                writeArray yary y (0,IS.empty)
                unless (c == 0) $ for_ (IS.toList s) $ \x -> modifyArray xary x (cross (subtract 1, IS.delete y))
            _ -> notComeHere

感想・振り返り

Cで、変化の山・谷に囚われすぎたのは良くなかった。後知恵だが、入力例をちゃんと眺めてみれば割とすっとわかる問題だったので残念。見切り発車で実装しようとせず、多少時間がかかってもちゃんと考察するようにしたい。また、リストの隣接要素同士の計算は zipWith f xs (tail xs) をさっと使えるようになろう。

Dは行と列を一緒に考えようとしていたのが良くなかったと思う。 \(H,W \le 2 \times 10^5\) なので \(H\times W\) の配列を用意するのは無理、というのはすぐにわかったけど、そこから行と列を別々に考える、ということに思い至らなかったな。愚直で解くという方針にしてしまえば思いついていたかも？クエリを処理する系の問題、計算量を落とすためにどう問題を言い換えるか？をちゃんと考察していきたい。

ABC406振り返り

A - Not Acceptable

B - Product Calculator

C - ~

D - Garbage Removal

感想・振り返り