ABC 372

ABC 372 に参加しました。

Table 1: Diff 予想
問題 A 問題 B 問題 C 問題 D 問題 E 問題 F 問題
提出 AC AC AC AC AC -
Diff 予想 1 300 400 1,200 1,200 1,600
Diff 実際 12 131 341 901 1,042 1,722

A 問題

. を除外せよ。 filter します。

main=interact$filter(/='.')

B 問題

\(M\) をなるべく少ない数の \(3^{A_i}\) の和に分解せよ。大きな \(3^{A_i}\) から順に割っていきます。

再帰を使いました。 concatMapM があれば良かったのですが。

eat :: Int -> [Int] -> [Int]
eat = inner
  where
    inner 0 _ = []
    inner x (i : is)
      | y > x = inner x is
      | otherwise = replicate q i ++ inner r is
      where
        !y = 3 ^ i :: Int
        (!q, !r) = x `divMod` y
    inner x y = error $ show (x, y)

solve :: StateT BS.ByteString IO ()
solve = do
  !m <- int'
  let !res = eat m $ revese [0 .. 10]
  printBSB $ length res
  printList res

cojna さんの提出 (91 Byte) は素朴なコードですが真似できません。極まっています。

C 問題

文字列 s を書き換えるとき、連続部分列 ABC の数を追跡せよ。可変配列を持って愚直に解きました。

MaybeT の使い方を理解しました。

isABC <- fmap (fromMaybe False) . runMaybeT $ do
  a <- MaybeT $ UM.readMaybe s i
  b <- MaybeT $ UM.readMaybe s $ i + 1
  c <- MaybeT $ UM.readMaybe s $ i + 2
  return $ [a, b, c] == "ABC"

D 問題

ビルの列 \(\{H_i\}_i\) が与えられた時、 \(\forall k \in (i, j), H_k \le H_j\) が成り立つ \(j\) の数を \(i\) ごとに求めよ。原文よりややこしいですね。

問題文とは逆に、右端のビル j を固定します。 i = j から始めると、 (i, j] の区間最大値は i を左へ動かすごとに単調増加します。したがって j 毎の i への寄与は区間加算となり、 Imos 法で計算できます。

\(O(N \log^2 N)\) 解 (\(O(N \log N)\) 解)

セグメント木の 2 分探索を使ってしましました。 301 ms.

\(O(N)\) 解

スライド最小値で解けると教えてもらいました。 21 ms. アルゴリズムは後述します。

solve :: StateT BS.ByteString IO ()
solve = do
  !n <- int'
  !hs <- intsU'

  let !imos = U.create $ do
         vec <- UM.replicate n (0 :: Int)
         -- スライド最小値により、各ビルよりも左のビルであって、
         -- そのビルよりも高い最寄りのビルを求める
         let !ls = lookBackHigherIndices hs
         U.iforM_ ls $ \r l_ -> do
           let !l = max 0 l_
           GM.modify vec (+ 1) l
           GM.modify vec (subtract 1) r
         return vec

  printVec $ U.scanl1' (+) imos

E 問題

\(N\) 頂点 \(0\) 辺のグラフがあり、以下の 2 種類のクエリを処理します。 1. 辺を追加する。 2. 頂点 v が属する連続成分の中で k 番目に大きな頂点の番号を求める。

TLE 解

頂点の集合を Union-FInd で管理しつつ、別途頂点番号の集合もマージして行きます。 Set を使えば マージテクによりマージが償却 \(O(\log N)\) になる気がしていました が、 TLE しました。どうして……。

追記: TLE 解への修正

同一集合のマージが \(O(N)\) になっていると指摘を頂きました。完全に盲点！　ありがとうございます！

しばらく気になっていたんですが、どうももともと２頂点が同一連結成分にすでに属している場合に問題が発生しているような気がします。実際、when (root1 /= root2) $ do を挟むとACしました： https://t.co/6YrNwypsVV

— 符号/gksato (@Fine_sugar_hill) September 23, 2024

類似の問題でも要注意です。

AC 解 (制約を活かす)

実は集合のサイズは 10 まで持てば良い制約でした。 Set (Down Int) を持って take 10 すれば TLE 解が高速になります。

F 問題

これは面白いですね。ムキーッ

スライド最小値

私はスライド最小値のアルゴリズムを思い出すため、写経ライブラリを覗き込みました。それには虫が付いていました。私は悲しいです。

参照

元ネタはこちら: スライド最大（最小）値・ヒストグラム内最大長方形問題を俯瞰する 。写経して理解しました。ありがとうございます！

以降は完全に焼き直しです。

(1) 固定幅の窓で見るスライド最小値

概要

数列 xs を幅 k の窓で見た時に、それぞれの窓の中の最小値 (の添字) を \(O(N)\) で求めます:

indices: 0 1 2 3 4 5  |
values:  5 1 2 4 0 3  | min value indices
----------------------+-----------------------------
        [--*--]       | 1
          [*----]     | 1
            [----*]   | 4
              [--*--] | 4

操作

窓 [---] と合わせて deque を持ち、窓を動かす度に以下の処理を実施します:

  1. 窓の左側に出た値 (の添字) は捨てる
  2. 窓の右端の値 \(\ge\) (\(\gt\)) 新しく追加する値 \(\Rightarrow\) 捨てる (繰り返す)
    言い換えると (a, Down Int) の広義 (狭義) 単調性を保つように deque を更新します。

これにより deque の左端の値が常に窓の中の最小値 (の添字) を表します。頭良いです。

例

以下の例では窓と合わせて deque (<i1 i2 ..>) を管理してスライド最小値を計算します。 Deque の中の左端の値が窓の中の最小値です。

indices: 0 1 2 3 4 5 |
values:  5 1 2 4 0 3 | max value indices:
----------------------+-----------------------------
        [--*--]      | 1
        <  1 2>      |
          [*----]    | 1
          <1 2 3>    |
            [----*]  | 4
            <    4>  |
              [--*--]| 4
              <  4 5>|

もう少し分かりやすい図を……募集しています。

(2) ヒストグラム問題

固定幅の窓で見るスライド最小値を改造します。前述の操作 1. を削除し、 deque の末尾にある値を読むことにすると、各ビル i よりも高い最寄りのビルが分かります。

-- | \(O(N)\) Solution to the histogram problem. Find the nearest higher building for each @i@..
--
-- @
-- index:  -1  0   1   2   3   4
-- height: --  1   5   2   4   3
--           <---- |
--                 | <---- |
--                 |       | <-|
--                 | <-|   |   |
--           <-|   |   |   |   |
-- look back: -1  -1   1   1   3
-- @
lookBackHigherIndices :: U.Vector Int -> U.Vector Int

これで今回の ABC 372 - D も一発撃墜です。頭良い！

Q & A

Link/cut tree (1)

Link/cut tree は憧れのデータ構造でした。 Library Checker で大活躍します。 1 問解けた ので、取り急ぎ教材だけメモします。

後は maspy さんの graph/ds/link_cut_tree.hpp を写経すれば分かってきました。 Wiki とは言葉遣いがやや異なります。

Wiki maspy さんのライブラリ
Preferred path Heavy path
Path-parent Light edge
Access Expose

Top tree? も意外と簡単らしいので、制覇したいです。

Misc

NixOS