ABC413振り返り

投稿日: 2025-07-10(木)
タグ: , ,

デンソークリエイトプログラミングコンテスト2025（AtCoder Beginner Contest 413）に参加したので振り返り。 振り返り記事を書くのは久しぶり（参加はしていました）。

コンテスト成績証

Dが詰めきれず、非常に悔しい結果でした。。。

A - Content Too Large

和が \(M\) 以下か判定するだけ。

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

    printYn $ sum as <= m

B - cat 2

問題文の通り、 \((i, j)\) の組み合わせが異なっても同じ文字列が出来上がる場合があるので、 同じ文字列を重複して数えないよう、連結結果を Data.Set に入れて要素数を求めれば良い。

main :: IO ()
main = do
    n <- val ucInt
    as <- zip [1..] <$> replicateM n getLine

    let result = S.fromList $ [x <> y | (i,x) <- as, (j,y) <- as, i < j]

    print $ S.size result

C - Large Queue

制約に \(1 \le c \le 10^9\) とあるので、素直に要素を出し入れしてたらTLEになる。 そのため、要素を直接キューに入れるのではなく、要素の値と要素の数のペア \((x,c)\) を入れれば良さそう。 ただし、クエリ \(2\) で先頭の同じ値の要素をすべて削除しきれない場合には、 （削除した数だけ \(c\) を減らした上で）ペアをキューの先頭に戻す必要がある。 そのため、 Data.Sequence にペアを入れるよう実装した。

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

    let f :: Seq.Seq (Int, Int) -> [Int] -> IO (Seq.Seq (Int, Int))
        f sq query = case query of
            [1,c,x] -> return $ sq Seq.|> (x,c)
            [2,k] -> do
                let (result, restSeq) = go sq k 0
                print result
                return restSeq
            _ -> notComeHere

        go :: Seq.Seq (Int, Int) -> Int -> Int -> (Int, Seq.Seq (Int, Int))
        go sq rest acc = case Seq.viewl sq of
            Seq.EmptyL -> notComeHere
            (x,c) Seq.:< restSq -> if | c < rest -> go restSq (rest-c) (acc+x*c)
                                      | c == rest -> (acc+x*c, restSq)
                                      | otherwise -> (acc+x*rest, (x,c-rest) Seq.<| restSq)

    void $ foldlM f Seq.empty qs

D - Make Geometric Sequence

並べ替えたあとの数列が等比数列になるためには、数列を絶対値の昇順もしくは降順で並べたあとに、 すべての隣り合う2項間の比が同じであれば良い。

・・・ということはすぐにわかったが、そこから先を詰めきれず撃沈。 実装ミスを疑って時間を溶かしてしまった。

各項の絶対値が等しい場合、以下の4つの場合に、適切に並び替えたあとの数列が等比級数になりうる。

  1. すべての項の符号が正
  2. すべての項の符号が負
  3. 符号が正の項の数と、符号が負の項の数の差が1
  4. 符号が正の項の数と、符号が負の項の数が同じ

今回は、3と4の場合が考慮できていなかった（3であれば、 \((1, 1, 1, -1, -1, -1, -1)\) のようなケース）。 終了5分前に3に気づいたけど、4の実装を忘れていてあえなくWA。

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

    for_ [1..t] $ \_ -> do
        _ <- val ucInt
        as <- L.sortOn snd . map (\x -> (signum x, abs x)) <$> list1 ucInt

        let result = nubOrd $ zipWith (\(p,x) (q,y) -> (p * q, let g = gcd x y in (x`div`g, y`div`g))) as (tail as)
            isSameAbs = let (x:xs) = map snd as in all (== x) xs
            (ps,ms) = bimap length length $ L.span (==(-1)) $ L.sort $ map fst as

        printYn $ length result == 1 || isSameAbs && (abs (ps - ms) == 1 || ps == ms || ps == 0 || ms == 0)

今回は、手元で自作のテストケースをいくつか試しているうちにコーナーケースに気がついた。 サンプルのテストケースが通ったら提出して良いが、WAしたときはいくつかケースを作って試してみるようにしよう。

E - Reverse 2i

コンテスト後のAC。Xもチラチラ見てしまったので完全に独力ではないが、おおよそ自分の力で解けたのは嬉しい。

問題文に記載されている「反転」操作のイメージが湧かなかったため、 まずはいくつかの \((a,b)\) について手元で実験してみた（サンプル3で実験）。

ここから、問題文にある「反転」操作は、 \(a \times 2^b\) の位置の要素（つまり偶数番目の位置の要素）と、 そこから \(2^b-1\) だけ離れた位置の要素について行われることがわかる （ \(b=0\) の場合は、2つの要素の位置が同じになるため考慮不要）。 上の実験では、反転する範囲ごとに \(0 \sim 6\) までの番号をつけている。

次に、反転操作を実施すべきか否かについて。 たとえば、範囲 \(0\) 、 \(1\) を反転するか否かに関わらず、範囲 \(4\) については反転したほうが、辞書順としては小さくなる。 別の例として、範囲 \(5\) については、反転しないほうが辞書順としては小さくなる。 一般に、ある範囲 \(k\) を反転すべきか否かは、その範囲を前半・後半で2分割し、 範囲内の最小値が前半に存在する場合にはそのまま・後半に存在する場合は反転したほうが良いことがわかる。 ここから、以下のアルゴリズムで辞書順最小を得ることができる。

  1. 数列を前半・後半の2つに分割する。数列の長さが \(1\) の場合はそのまま返す。
  2. 分割した各数列にこのアルゴリズムを適用し、各々辞書順最小の列を得る。
  3. 各列を比較し、前半のほうが小さければ「前半・後半」の順に、後半のほうが小さければ「後半・前半」の順に結合する。

実際には、2で得た辞書順最小列の大小を比較するのではなく、各列の最小値を求め、 その大小で結合順を決めるようにしたほうが時間は短くなった （前半列・後半列へのアルゴリズムの適用は、結合のときに行っている）。

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

    let f :: Int -> [Int] -> [Int]
        f _ [] = notComeHere
        f _ [x] = [x]
        f n as@(_:_:_) = let d = n `div` 2
                             (xs,ys) = L.splitAt d as
                         in if minimum xs < minimum ys
                            then f d xs <> f d ys
                            else f d ys <> f d xs

    for_ [1..t] $ \_ -> do
        n <- val ucInt
        ps <- list1 ucInt

        putStrLn $ unwords $ map show $ f (2^n) ps

感想など

やはりD問題を落としたのは辛い。 正直なところ、問題としてはかなり簡単めだったと思うので、ああいったコーナーケースを如何に早く検出できるかが大事になると思う。 そういった目的のためにはQuickCheckも使えるようになったほうが良いと思うが、 コンテスト時間中に等比数列を生成するGeneratorを書くのは中々キツイ・・・ （現状QuickCheckは、精進でWAが取れないときに使っている）。 手実行でいい感じのケースをさっと作るにはどうすればよいだろう？QuickCheckにもっと習熟していくほうが良いのかな？

ABC411で久しぶりに緑パフォ&過去最高パフォ出していい気になっていたら、そこからの2回はいずれも敗北。 やはり、4問解き切れるかどうかが、緑パフォになるかどうかの境目のように見える。 （自分はあまり速解きが得意ではないので、3問だけで緑パフォは出せない。 ABCの3問で緑パフォ出してる人はだいたい15分くらいで3問解いているみたい）

最近精進にも身が入っていなかったので、問題を解くのを習慣づけよう。