たすのーと - ABC416振り返り

AtCoder Beginner Contest 416に参加したので振り返り。

ABの2完。あれ・・・？

A - Vacation Validation

問題文のとおりに確認すれば良い・・・のだけど、実装に手間取った。 drop と take でどの要素まで見るか、混乱してしまった。

main :: IO ()
main = do
    (n,l,r) <- int3
    ss <- list1 ucChar

    printYn $ all (=='o') $ take (r - l + 1) $ drop (l - 1) ss

もっと素直に、以下の様に書いても良かったかな（なんとなく !! を使うのに気が引けてしまい、コンテスト中はこのように書こうと思わなかった。制約的には何も問題ないね）。

main :: IO ()
main = do
    (n,l,r) <- int3
    ss <- list1 ucChar

    printYn $ all ((=='o') . (ss !!)) [l-1..r-1]

B - 1D Akari

Akariって、最近Xのタイムラインでよく見るコレのことかな・・・？と思いつつ問題。手元で実験してみると、

\(S\) 中のある # とその次の # との間に、1つ以上の . が存在する場合に
. の1つを o に置換することで、条件を満たす \(T\) となる

ことがわかる。

main :: IO ()
main = do
    ss <- L.group <$> list1 ucChar

    let result = concatMap (\xs -> if head xs == '.' then 'o':tail xs else xs) ss

    putStrLn result

C - Concat (X-th)

今回のドハマりその1。

\(f(A_1,\dots,A_K)\) を、「 \(S_1,\dots,S_N\) から \(K\) 個を選ぶ順列を考え、順列の順に文字列を結合したもの」として定める、と読んでしまった。。。 Data.List にはリストのすべての順列を返す permutations という関数があるが、「 \(N\) 個から \(K\) 個を選ぶときのすべての順列」を返す関数はない。

どうやって実装するのかと四苦八苦していたが結局できず、コンテスト後に重複順列が問われていることに気がついてがっくり。

main :: IO ()
main = do
    (n,k,x) <- int3
    sss <- replicateM n getLine

    let cands = L.sort . map concat . replicateM k $ sss
    -- let cands = L.sort . map concat . sequenceA . replicate k $ sss

    putStrLn $ cands !! (x-1)

解説では、重複順列を得るためにDFSをすれば良い、とあったが、リストであれば replicateM k で重複順列を得られる（もともとは sequenceA . replicate k としていたが、HLSからサジェストされた。こんなのも提案してくれるんだね、びっくり）。

sequenceA やら replicateM やらの動作の理解がちょっと怪しいので、どこかでちゃんと勉強したい。

そもそも \(\sum_{i=1}^N \{(A_i + B_i) \mod M\}\) のように、剰余を更に足し合わせるという操作をどのように考えればよいか、よくわからずだった。「 \(A_i + B_i \ge M\) なる \(i\) の個数」という観点は全く無かったので勉強になる・・・のだけど、今回は入力サンプルを手元であーだこーだしていただけで、式をいじってみよう、とはならなかった。もう少し式変形して遊んでみたら、手がかりがつかめていたかもしれない。

解説によれば、数列 \(A\) を降順・ \(B\) を昇順に並べて、しゃくとり法の要領で \(A_k + B_i \ge M\) なる条件でマッチングさせれば良い、ということだったが、コレもコンテスト中には絶対思いつけないな、と思う。確かに、マッチング条件は「しゃくとり法が使える条件」を満たしているが、よくあるしゃくとり法の構造とは微妙に異なっているように見える（マッチングしたら \(A\) 、 \(B\) 両方とも1個進める必要があるし、どちらかがどちらかを追い越しても問題ない。そもそも異なる2列にしゃくとり法を適用するのがあまりなさそう）。

こういう方法もあるんだなぁ、くらいで覚えておくと良さそう。

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

    for_ [1..t] $ \i -> do
        (n,m) <- int2
        as <- L.sortOn Down <$> list1 ucInt
        bs <- L.sort <$> list1 ucInt

        let result = shakuMatch (\l r -> l + r >= m) as bs

        print $ sum as + sum bs - length result * m

-- | しゃくとり法により、2つの列について、述語を満たす要素同士のマッチング (l,r) のリストを返す。
-- x <= l, r <= y なる任意の x,y について、マッチング (x,y) は述語を満たす。
shakuMatch :: forall a b.
              (a -> b -> Bool) -- ^ 区間に対する述語
           -> [a]                   -- ^ 計算対象列1
           -> [b]                   -- ^ 計算対象列2
           -> [(Int, Int)]
shakuMatch predicate as bs = go (0,as) (0,bs)
    where go :: (Int, [a]) -> (Int, [b]) -> [(Int, Int)]
          go (nl,lls) (nr,rrs) = case (lls,rrs) of
              (l:ls,r:rs) -> if predicate l r
                  then (nl,nr) : go (nl+1,  ls) (nr+1 ,rs)
                  else           go (nl  ,l:ls) (nr+1, rs)
              _ -> []

Xのポストや他の人の提出を見ていると、しゃくとり法ではなく

\(A\) の要素の降順に、以下を実施
- \((A_k + B_i) \ge M\) となる最小の \(B_i\) を二分探索
- 上記 \(B_i\) が存在すれば、数列 \(B\) から \(B_i\) を取り除く

としている人も結構いたように見える。

こちらのほうが思いつきやすそうだと思う反面、この方法には multiset が必要になる¹ので、用意していない自分はしゃくとり法を思いつく必要があった。。。早めに multiset を整備しておこう。

感想

C問題は完全に問題の読み間違い。うーんこの・・・視野狭窄に陥ってしまっていたね。解けないなーと思ったら、ちゃんと問題文に戻ってよく読んでみよう。

一方、 \(N\) 個から \(K\) 個を選ぶ順列のパターンを全列挙するという問題も、答えを出せていない。実装はめんどくさそうだけど、ちょっと考えてみようと思う。（DFSを使えば、とても非効率だけど明快な実装は作れそうではある）

あとは、リストにおける replicateM の使い方。上でも言ったが、少し理解が怪しいところがあるのでちゃんと勉強しておこう。

D問題については、あまり経験がない考え方とはいえ、全く手も足も出ない、という感じではなさそうに感じた。サンプル問題をいじってみるだけでなく、式が与えられているなら式変形も試してみるといいかな。手元で実験するやり方は一つではないね。

https://x.com/kyopro_friends/status/1949111869375164845 ↩︎

ABC416振り返り

A - Vacation Validation

B - 1D Akari

C - Concat (X-th)

D - Match, Mod, Minimize 2

感想