たすのーと - ABC405振り返り

AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）に参加したので振り返り。

A - Is it rated?

まずDiv.1/2で場合分けし、次にレーティングが範囲内か否かを判定する。

main :: IO ()
main = do
    (r,x) <- int2

    printYn $ case x of
        1 -> 1600 <= r && r <= 2999
        2 -> 1200 <= r && r <= 2399

B - Not All

問題文の通り、後ろから1つずつ削除しながら、条件を満たすか否かをチェックすればよい。 flip fix を使うと雑にループを書けて便利。

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

    let result = flip fix (0,reverse as) $ \loop (acc,bs) ->
            case bs of
                [] -> acc
                _ -> if any (`notElem` bs) [1..m]
                     then acc
                     else loop (acc+1,tail bs)

    print result

foldl' 等を使用した実装は思い浮かばなかった。。。あとは明示的に再帰を書くくらいしかできないかな？

go :: Int -> Int -> [Int] -> Int
go _ acc [] = acc
go m acc as@(_:bs) = if any (`notElem` as) [1..m]
                     then acc
                     else go m (acc+1) bs

C - Sum of Product

\(S_i = \sum_{j=i}^N A_j\) とおけば、

\[\begin{align*} \sum_{1 \le i < j \le N} A_i A_j &= A_1 \sum_{j=2}^N A_j + A_2 \sum_{j=3}^N A_j + \dotsb + A_{N-1}A_N& \\ &= \sum_{i=1}^{N-1} A_i S_{i+1} & \end{align*} \]

\(S_i\) は scanr1 で簡単に計算できる。

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

    let si = L.scanr1 (+) as

    print $ sum $ zipWith (*) as $ tail si

D - Escape Route

まず、各 \((i,j)\) について E からの最短距離をBFSで求める。各点から距離を1ずつ減らす向きに進むと最寄りの E に到達するので、進む向きに応じて \((i,j)\) に ^v<> をおけばよい。

コンテスト中は、進む向きに応じて ^v<> をおく処理で良い感じの実装が思いつかず、可変配列を使って手続き的にゴリゴリと書いて時間がかかった。あと、 \((i,j)\) の上下左右4点を列挙する処理 nei4 をライブラリとして用意していたが、これにバグがありちょっと躓いた。

処理の中で、ある点と周囲の点の座標を明示的に計算していてごちゃごちゃしてしまった。。。以下のようなデータ型を用意しておくと、実装が簡単になりそう。

data Direction = L | R | U | D
    deriving (Eq, Bounded, Enum)

allDirections :: [Direction]
allDirections = [minBound..maxBound]

d2c :: Direction -> Char
d2c L = '<'
d2c R = '>'
d2c U = '^'
d2c D = 'v'

d2i :: Direction -> (Int, Int)
d2i L = (0,-1)
d2i R = (0,1)
d2i U = (-1,0)
d2i D = (1,0)

(^+) :: (Int, Int) -> (Int, Int) -> (Int, Int)
(i, j) ^+ (u, v) = (i+u, j+v)

また、矢印の向きは点の座標から導出できるので、可変配列を使用する必要もない。

上記を踏まえ、書き直したものが以下。

main :: IO ()
main = do
    (h,w) <- int2
    grid <- charGrid h w

    let exits = map fst $ filter (\(_,e) -> e == 'E') $ assocs grid
        bnd = ((1,1),(h,w))

        dist = runSTUArray $ bfs (nexts ((/='#').(grid!)) bnd nei4) bnd exits
        result = array @UArray bnd [(ij, f ij) | ij <- range bnd]
            where f ij = case grid ! ij of
                      '.' -> d2c . head . concat . flip map allDirections $
                               \d -> [d | let ij' = ij ^+ d2ij d, inRange bnd ij', dist ! ij - dist ! ij' == 1]
                      x  -> x

    printGrid result

E - Fruit Lineup

残り20分くらいで取り掛かり始めたが、クリティカルな考察にはたどり着かず時間切れ。

一番左にあるブドウを境に、列を左右に分ける。「リンゴはすべて、ブドウよりも左側に並べる」「オレンジはすべて、ブドウよりも左側に並べる」という条件から、左にはすべてのリンゴとオレンジが存在する。また左に存在するバナナの個数を \(x \ (0 \le x \le C)\) 個とすると、残りの「リンゴはすべて、バナナよりも左側に並べる」という条件から、左の並べ方の総数は、「🍎🍎🍎🍎🍎🍎🍎🍎🍌🍌🍌🍌🍌🍌🍌🍌🍌」のように並べたリンゴとバナナの間にオレンジを挿入する場合の数となり、これは \(\dbinom{A+x+B}{B}\) に等しい。

また右には、 \(C-x\) 個のバナナと \(D-1\) 個のブドウが存在する。ブドウとバナナの並べ方に条件はないため、並べ方の総数は \(\dbinom{C-x+D-1}{D-1}\) となる。したがって、並べ方の総数は、各 \(x\) について和をとった

\[\begin{equation*} \sum_{x=0}^C \dbinom{A+x+B}{B}\dbinom{C-x+D-1}{D-1} \end{equation*} \]

となる。

実装は以下を参考にした（前処理なしで計算したらサンプル問題から計算が終わらなかった）。

競プロでよく使う二項係数(nCk)を素数(p)で割った余りの計算と逆元のまとめ

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

    let tbl = initNCK (a+b+c+d)
        f x = nCkMod tbl (a + x + b) b * nCkMod tbl (c - x + d - 1) (d - 1)

    print $ sum $ map f [0..c]

data NCKTable =
    NCK { size :: Int
        , factTable :: VU.Vector IntMod
        , invTable :: VU.Vector IntMod
        , factInvTable :: VU.Vector IntMod
        }

initNCK :: Int -> NCKTable
initNCK n = let ft = VU.constructN n $ \vec ->
                    case VU.length vec of
                        0 -> 1
                        1 -> 1
                        x -> IntMod x * vec VU.! (x - 1)
                it = VU.constructN n $ \vec ->
                    case VU.length vec of
                        0 -> 1
                        1 -> 1
                        x -> - vec VU.! (modulus `mod` x) * IntMod (modulus `div` x)
                fit = VU.constructN n $ \vec ->
                    case VU.length vec of
                        0 -> 1
                        1 -> 1
                        x -> vec VU.! (x - 1) * it VU.! x
            in NCK n ft it fit

nCkMod :: NCKTable -> Int -> Int -> IntMod
nCkMod (NCK size factTable _ factInvTable) n k
    | size < n || size < k = error "size over"
    | n < k = error "invalid k"
    | otherwise = factTable VU.! n * factInvTable VU.! k * factInvTable VU.! (n-k)

感想

方針が立っても実装がうまく行かなくて解けない、といった場面が自分にはよく見られるが、Dはごちゃつきながらもなんとか通せたのは良かったかな。

とはいえ、今回のDはそれほど難しい問題でもなかったので、さくっと実装したいところ。単純にパターンが自分に染み込んでない。

いつもながらの振り返りだけど、もっと精進しようね、と。

そういえば

https://x.com/drken1215/status/1919710467066626284

ABC 212〜317 の A〜F を、思考を自動化できるレベルまで練習を繰り返すことが良いそうです！！！

たとえば、C 問題を 2 分で解けとまでは言わないけど、10 分かかってるようだと何かしら身に付いていない可能性があって、そのままではいけないと言っていました

https://x.com/drken1215/status/1919746815135506631

りんごさん曰く、同じ問題を 3 回解き直すくらいは当たり前みたいです。

そのくらいやらないと、「思考の自動化」はできて来ないと。

https://x.com/drken1215/status/1919703191857295621

これ一応、正確には

・ABC 212〜317 の A〜F を完全にマスターすれば、・黄色になれる

という設計みたいです。

よーしがんばるぞ