たすのーと - ABC415振り返り

日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415）に参加したので振り返り。

Cで時間をかけすぎ、わずかに下げてしまった。。。

A - Unsupported Type

\(A\) に \(X\) が含まれるか確認するだけ。

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

    printYn $ x `elem` as

B - Pick Two

予め # の位置を振っておき、前から2つずつとっていけば良い。

main :: IO ()
main = do
    ss <- map fst . filter ((=='#') . snd) . zip [1..] <$> list1 ucChar

    let f [] = []
        f [_] = notComeHere
        f (a:b:as) = (a,b) : f as

    for_ (f ss) $ \(a,b) -> putStrLn $ show a <> "," <> show b

C - Mixture

問題の意味を理解するのに時間がかかってしまった。。。問題文には、以下のように記載されている。

まず、 \(1\) 種類以上の薬品が混ざった状態 \(i ( 1 \le i \le 2^N −1 )\) を次のように定義する。 \(i\) を \(2\) 進法で表記した際に下から \(k ( 1 \le k \le N )\) 桁目が \(1\) である、またその時に限り、薬品 \(k\) が含まれている。

上記だけだとよくわからないので、例を挙げてみる。

\(N=3, \ S=\) 0010000 とすると、 \(S\) の \(3_{(10)} = 011_{(2)}\) 桁目が \(1\) となっている。これは薬品 \(1_{(10)} = 001_{(2)}\) と薬品 \(2_{(10)} = 010_{(2)}\) が混ざった状態 \(011_{(2)}\) が危険である、という意味になる。

そのため、薬品を1種類混ぜることは、「ある \(2\) 進法で表された状態において、薬品の番号に対応する桁を \(0\) から \(1\) に変えること」に対応する。

この理解の下で、問題は次のように言い換えられる:

\(N\) 桁の \(2\) 進数において、 \(0\) である桁のいずれかを \(1\) に変更する操作を考える。 \(0_{(2)}\) から始めて、すべての桁を \(1\) とするような操作列は存在するか。ただし、文字列 \(S\) で指定される数への変更は禁止する。

単に \(\underbrace{00\dots0}_{N}\) から \(\underbrace{11\dots1}_{N}\) に到達できるかどうかだけなので、DFSで解くことができる。状態遷移関数 nextStatus では、今の状態が危険なら遷移先なし、安全なら遷移先の状態を列挙する（問題文からは、危険な状態への遷移は禁止しているように読めるが、危険な状態からは次の状態に遷移できない、としても同じである）。

main :: IO ()
main = do
    t <- val ucInt

    for_ [1..t] $ \i -> do
        n <- val ucInt
        ss <- array @UArray (0::Int,2^n-1) . ((0,'0'):) . zip [1..] <$> list1 ucChar

        let nextStatus x = if ss ! x == '1' then []
                else map (setBit x . fst) . filter ((==0) . snd) . zip [0..] <$> take n $ endig 2 x <> repeat 0

            result = dfs nextStatus (0,2^n-1) [0]

        printYn $ ss ! (2^n-1) /= '1' && result ! (2^n-1)

D - Get Many Stickers

貪欲で行けそうには見えていたが、どの順番で操作するかわからず、コンテスト中には解けなかった。。。（当初は \(A_i\) と \(B_i\) の比を考えるのかと思っていたが、それだとうまくいかない）

解説の通り、 \(A_i - B_i \equiv D_i\) が小さい順にとっていけばよく、操作の回数が本問題の答えとなる。整数 \(i\) に対応する操作を \(x_i\) 回行う場合、現在持っている瓶入りコーラの本数を \(C\) とすると、

\[\begin{equation*} C - D_i \times x_i < A_i \Leftrightarrow x_i > \frac{C-A_i}{D_i} \Leftrightarrow x_i = \biggl\lfloor \frac{C-A_i}{D_i} \biggr\rfloor + 1 \end{equation*} \]

となる。ただし、 \(C - A_i < 0\) の場合は操作ができないため、その場合は \(x_i = 0\) とする。

main :: IO ()
main = do
    (n,m) <- int2
    ablist <- L.sortOn snd . map (\(a,b) -> (a,a-b)) <$> int2list m

    let f :: (Int, Int) -> (Int, Int) -> (Int, Int)
        f (bin, seal) (a,d) = let x = max 0 $ (bin-a)`div`d + 1
                              in (bin - d * x, seal + x)

        result = snd $ foldl' f (n,0) ablist

    print result

E - Hungry Takahashi

コンテスト中ちょっと触ってみたが、方針立たず。解説を読むと、DPが想定解法とのこと。

あるマス \((i,j)\) からマス \((H,W)\) に行くために持っておくべきコインの枚数の最小値を \({dp}_{i,j}\) とする。マス \((i,j)\) で所持金が負にならないために必要なコインの枚数は、

マス \((H,W)\) では、「このマスで失うコインの枚数」
それ以外のマスでは、「次のマスで持っておくべきコインの枚数」-「このマスで得られるコインの枚数」

である（ \({dp}_{i,j} \ge 0\) なので、上記の値は非負）。「次のマス」は今いるマスの右か下なので、以下の緩和式が成り立つ。

\[\begin{equation*} {dp}_{i,j} = \begin{cases} \max (0, P_{H+W-1} - A_{H,W}) & (i,j) = (H,W) \\ \max (0, \min ({dp}_{i+1,j},{dp}_{i,j+1}) - (A_{i,j} - P_{i+j-1})) & \text{otherwise} \end{cases} \end{equation*} \]

main :: IO ()
main = do
    (h,w) <- int2
    ag <- intGrid h w
    ps <- list1 ucInt

    let pa = array @UArray (1,h+w-1) $ zip [1..] ps

        result = runSTUArray $ do
            dp <- newArray ((1,1),(h,w)) (maxBound :: Int)
            writeArray dp (h,w) $ max 0 (pa ! (h+w-1) - ag ! (h,w))

            for_ [h,h-1..1] $ \i -> for_ [w,w-1..1] $ \j -> do
                when ((i,j) /= (h,w)) $ do
                    rpj <- if i < h then readArray dp (i+1,j) else return maxBound
                    rip <- if j < w then readArray dp (i,j+1) else return maxBound
                    writeArray dp (i,j) $ max 0 (min rpj rip - (ag ! (i,j) - pa ! (i+j-1)))

            return dp

    print $ result ! (1,1)

回答見ればどういう緩和式になるのかはわかるけど、まだまだ本番でこの緩和式は思いつかない・・・

感想

C問題は、2進数の状態遷移を扱う問題があった（ABC410-D）のを思い出し、自力で実装できたのは良かった。むしろ、問題文を読み解くのに時間がかかってしまった（薬品と状態という2つの概念の関係の理解が難しかった）。 2進数で表された情報を文字列にエンコードする、という考え方は新鮮で面白いと思ったので、覚えておこう。

D問題は、全然詰めきれなかったなという感覚。 \(A_i\) と \(B_i\) の比が同じならより \(A_i\) が小さいほうが良い、というところまでは気づけていたので、操作で瓶入りコーラの本数がどう変化するか、計算してみたら良かったかもしれない（紙上での実験が足りなかった）

E問題、まずDPというのが思いつかなかったのと、upsolveでも降順に遷移させることに気づかず、随分時間を食ってしまった。単純に経験が足りないだけな気もするので、どんどん問題を解いて慣れていこう。