ABC402振り返り

投稿日: 2025-04-20(日)
タグ: , ,

東京海上日動プログラミングコンテスト2025（AtCoder Beginner Contest 402）に参加したので振り返り。

コンテスト成績証

A - CBC

英大文字だけ filter すれば良い。

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

    putStrLn $ filter isUpper s

B - Restaurant Queue

クエリに従ってキューに出し入れする問題。 Data.Sequence のインタフェースに慣れておらず、ちょっと手間取ってしまった。

main :: IO ()
main = do
    q <- val ucInt
    qs <- fmap words  <$> replicateM q getLine

    let y = unlines $ reverse $ fst $ foldl' f ([], Seq.empty) qs
            where f (result, sq) query = case query of
                      ["1",x] -> (result, sq Seq.|> x)
                      ["2"]   -> (let v Seq.:< rest = Seq.viewl sq in (v:result, rest))
                      _       -> error "not come here"

    if null y then putStrLn "" else putStr y

C - Dislike Foods

こちらは時間内に解けず、終了1分後にAC（悲しい）。

方針は以下。

  1. 各料理について、すべての食材を克服するのが何日目になるか求める
    • 配列の \(B_i\) 番目の要素に \(i\) を入れておくことで、食材に対応する克服日を高速に求められる
    • 料理の各食材について克服日を求め、最大値を取ればよい。
  2. 上記より、 \(i\) 日目に何個の料理が食べられるようになるかを計算する
    • いつもの map (pair (head, length)) . group . sort で計算可能。
main :: IO ()
main = do
    [n,m] <- list1 ucInt
    kas <- fmap (\(_:as) -> as) <$> list2 m ucInt
    bs <- array @UArray (1,n) . (\x -> zip x [1..]) <$> list1 ucInt

    let xys'' = VU.create $ do
            let xys' = map (pair (head, length)) . L.group . L.sort . map (maximum . map (bs !)) $ kas
            result <- VUM.new n
            forM_ xys' $ \(h,l) -> do
                VUM.write result (h-1) l
            return result

    ref <- newRef 0

    forM_ [0..n-1] $ \i -> do
        let v = xys'' VU.! i
        modifyRef' ref (+v)
        readRef ref >>= print

当初、料理毎に食材を Data.IntSet で持っておき、克服した食材を順番に IntSet.delete していく、という愚直な方法で実装したが、 この方法では該当食材を含まない料理に対しても IntSet.delete を実行することになる。 そのためおよそ \(O(N\sum_i^M K_i)\) の計算量がかかってしまい、あえなくTLE。

もともと、「 \(i\) 日後に克服する食材はなにか」という情報が与えられていたが、 これを「食材 \(B_i\) が克服されるのは何日後か」という情報に読み替えたことで、各料理の食材がすべて克服される日を求めることができるようになった。

解説を見ると、「ある料理に含まれる食材はなにか」という情報から、「ある食材を含む料理はどれか」という情報に変換する方法もあるようだ。 この情報により、 \(i\) 日目に克服した食材 \(B_i\) を含む料理がわかるため、愚直な方法よりも効率的に処理できる。

上記の方針で実装したバージョンは以下1 。

main :: IO ()
main = do
    [n,m] <- list1 ucInt
    kas <- zip [1..] . fmap (\(k:as) -> (k,as)) <$> list2 m ucInt
    bs <- list1 ucInt

    ryori <- newListArray @IOUArray (1,m) [k | (_,(k,_)) <- kas]
    ref <- newRef 0

    let invertedIndex = accumArray @Array (flip (:)) [] (1,n) [(a, i) | (i,(_,as)) <- kas, a <- as]

    for_ bs $ \b -> do
        for_ (invertedIndex ! b) $ \i -> do
            modifyArray ryori i (subtract 1)
            r <- readArray ryori i
            when (r == 0) $ modifyRef' ref (+1)

        readRef ref >>= print

D - Line Crossing

こちらも時間内には解けず。

円周上に等間隔に点が並んでおり、2点を選ぶと直線が引ける。このように引いた直線が何本か与えられており、そのうちから2本選んだとき、それが交差するのは何通りか？という問題。

直線が交差するというのは、すなわち直線の傾きが異なっているということ。 ・・・ということはすぐわかったが、では今回の問題設定で、2直線の傾きが大きいとはどういうことだろう？

一見すると、点の番号と傾きには関係がなさそうに見えるが、手元で色々実験してみると、 \((A_i + B_i) \bmod N\) が同じ直線は傾きが同じである、ということがわかる。

そこまでわかれば、あとは一本道。 \((A_i + B_i) \bmod N\) が等しい入力毎にグルーピングし、各直線について、異なるグループにいる直線の件数を集計する（すべて交差するので）。 2重に数えているので、2で割ることも忘れずに。

main :: IO ()
main = do
    [n,m] <- list1 ucInt
    print . (`div`2) . sum . fmap ((\x -> x*(m-x)) . length) . L.group . L.sort . fmap (\(a,b) -> (a+b)`mod`n) =<< int2list m

振り返り・感想

以前出場していたときの感覚でいると、CやDってこんなに難しかったか？と思ってしまう。 なにか特別なアルゴリズムやデータ構造を知ってないと解けない、というよりは、ちゃんと考察することが求められているようにも感じる（考察後は、それほど難しい実装が求められているわけではなさそう）。 そうなると、もう本当に色々な問題に触れて、考察テクニックを磨いていくのが良いのかな。

赤ん坊を抱っこしながらだとなかなか書いたりするのも難しいけど、キーボードと画面だけで考えるのではなく、ちゃんと書いて実験したり、整理するようにしてみよう。

  1. https://atcoder.jp/contests/abc402/submissions/65051138 を参考にさせていただきました（ほとんど一緒）。↩︎