ABC364をHaskellで

# A - Glutton Takahashi

[問題 ABC364A](https://atcoder.jp/contests/abc364/tasks/abc364_a)

シグネチャを決める。

```haskell
abc364a :: Int      -- N
        -> [String] -- Si
        -> Bool     -- 答え
```

`sweet` と `salty` では1文字目では区別が付かないので、2文字目を見比べる。
`w` が連続しなければ問題ない。
例2のように、連続していても、それが末尾ならセーフなのがちょっと意地悪。

## 結果

```haskell
import Data.List

abc364a :: Int -> [String] -> Bool
abc364a _n ss =
  case dropWhile (('w','w') /=) $ zip was $ tail was of
    [_] -> True
    []  -> True
    _   -> False
  where
    was = map (!! 1) ss
```

# B - Grid Walk

[問題 ABC364B](https://atcoder.jp/contests/abc364/tasks/abc364_b)

シグネチャを決める。

```haskell
abc364b :: [Int]    -- H,W
        -> [Int]    -- Si,Sj
        -> [String] -- Cij
        -> String   -- X
        -> [Int]    -- 答え
```

地図を作って忠実にシミュレーションする。

## 結果

```haskell
import Data.Array.Unboxed

abc364b :: [Int] -> [Int] -> [String] -> String -> [Int]
abc364b [h,w] [si,sj] ss x = [gi,gj]
  where
    bnds = ((1,1),(h,w))
    arr :: UArray (Int,Int) Bool
    arr = listArray bnds [c == '.' | s <- ss, c <- s]
    (gi,gj) = foldl step (si,sj) x
    step ij d
      | inRange bnds ij1, arr ! ij1 = ij1
      | otherwise = ij
      where
        ij1 = move ij d
    move (i,j) 'L' = (i, pred j)
    move (i,j) 'R' = (i, succ j)
    move (i,j) 'U' = (pred i, j)
    move (i,j) 'D' = (succ i, j)
```

# C - Minimum Glutton

[問題 ABC364C](https://atcoder.jp/contests/abc364/tasks/abc364_c)

シグネチャを決める。

```haskell
abc364c :: [Int] -- N,X,Y
        -> [Int] -- Ai
        -> [Int] -- Bi
        -> Int   -- 答え
```

コストを大きい順に整列し、前から足し合わせると、食べる個数を極力少なくして稼げるコスト合計が個数ごとにわかる。
達成目標のXまたはYを**越えたら止める**までの個数は、累積和が目標以下である個数+1であるが、例2のように全部食べても足らない場合がありうるのでNを上限にする。


## 結果

```haskell
import Data.List

abc364c :: [Int] -> [Int] -> [Int] -> Int
abc364c [n,x,y] as bs = min (f x as) (f y bs)
  where
    f u = min n . length . takeWhile (u >=) . scanl (+) 0 . sortBy (flip compare)
```

# D - K-th Nearest

[問題 ABC364D](https://atcoder.jp/contests/abc364/tasks/abc364_d)

シグネチャを決める。

```haskell
abc364d :: Int     -- N
        -> Int     -- Q
        -> [Int]   -- Ai
        -> [[Int]] -- Bi,Ki
        -> [Int]   -- 答え
```

差 $R$ について、$[B_i - R, B_i + R]$ の範囲に入る $A_j$ の個数が $K_i$ である（以上である最小の）$R$ を二分探索で探す。

## 結果

```haskell
import qualified Data.IntMap as IM

abc364d :: Int -> Int -> [Int] -> [[Int]] -> [Int]
abc364d _n _q as bks = map f bks
  where
    cnt = IM.fromListWith (+) [(a, 1) | a <- minBound : maxBound : as] -- 各Aiの個数
    (_,acc) = IM.mapAccum (\a b -> let c = a + b in (c,c)) 0 cnt  -- Ai以下の値の個数
-- BiからKi番目の値との差
    f (b:k:_) = snd $ binarySearch (prop b k) (-1) (succ $ 2 * 10^8)
-- Bi±R の範囲にあるAiはK個以上
    prop b k r = k <= c4 - c1
      where
        Just (_, c1) = IM.lookupLT (b - r) acc
        Just (_, c4) = IM.lookupLE (b + r) acc

binarySearch :: (Int -> Bool) -> Int -> Int -> (Int, Int) -- 定義略
```

# E - Maximum Glutton

[問題 ABC364E](https://atcoder.jp/contests/abc364/tasks/abc364_e)

シグネチャを決める。

```haskell
abc364e :: [Int]   -- N,X,Y
        -> [[Int]] -- Ai,Bi
        -> Int     -- 答え
```

甘さと塩辛さの二つのコスト軸を持つナップザック問題と捉えられる。
合計 $X, Y$ 以下で選べる最大の料理数を求める。次にもう一つ何か選ぶと制限を超えるので最後に+1する。ただし $N$ を越えない範囲で。

選んだ料理の個数 $0 \leq i \leq N$
甘さの総和 $0 \leq p \leq X$
に対して、その状態になる塩辛さの総和の最小値 $0 \leq q \leq Y$ を表 $T$ にする。
次の料理 $(A_i, B_i)$ に対して $T[j + 1, p + A_i]$ を $T[j, p] + B_i$ と小さい方で更新する。$T$ は広範囲が更新されるのでimmutable arrayでよい。

全ての料理を検討した後、料理の個数添え字の最大値を探す。

## 結果

```haskell
import Data.List
import Data.Array.Unboxed

abc364e :: [Int] -> [[Int]] -> Int
abc364e [n,x,y] abs = min n $ succ $ maximum [j | ((j, _p), q) <- assocs arrN, q < tooBig]
  where
    tooBig = succ y
    arr0 = accumArray min tooBig ((0,0),(n,x)) [((0,0),0)] :: UArray (Int,Int) Int
    arrN = foldl' step arr0 abs
    step arr (a:b:_) =
      accum min arr
        [ ((succ j, pa), q1)
        | ((j, p), q) <- takeWhile ((n >) . fst . fst) $ assocs arr
        , let pa = p + a, pa <= x
        , let q1 = q + b ]
```

メモリ消費を抑えてキャッシュに入りやすくするために `arr` の要素を `Word16` にしてみたが `Int` のままと結果は変わらなかった。
一方、`Array` を `UArray` にすると劇的に高速化した。

# F - Range Connect MST

[問題 ABC364F](https://atcoder.jp/contests/abc364/tasks/abc364_f)

シグネチャを決める。

```haskell
abc364f :: Int     -- N
        -> Int     -- Q
        -> [[Int]] -- Li,Ri,Ci
        -> Int     -- 答え
```

## 公式解説ベースの解き方

公式解説、別解 by evima と本質的に同じ考え方。区間の管理の仕方が違うだけ。

1～Nの範囲の頂点について、普通は「辺を張り終わったもの」を記録していくと発想するが、逆に「まだ辺が張っていない範囲」を記録する。
クルスカル法の発想で、$C_i$ の小さいクエリから処理し、指定の範囲 $[L_i,R_i]$ の中で、まだ辺が張ってないもの全てを取り除く。このとき、その個数分だけ辺が必要になる。しかしこれだと、相互に接続されたのか、$R_j + 1 = R_k$ のようにぴったり並んだ区間があるだけで接続されていないのか判別できない。

$[L_i,R_i]$ を「辺の張っていない範囲」から取り除くことで、これを含む空白の範囲 $[\ell \leq L_i, R_i \leq r]$ （$l-1,r+1$ は残っている）ができる。この区間のうち一箇所、代表として $\ell$ は取り除かずに残しておく。この配慮をすることで、互いに接続になるために必要な辺の最安コストも同時に算出できる。

最終的に「辺の張っていない範囲」が $[1]$ になれば成功となる。

```haskell
import qualified Data.IntSet as IS

abc364f :: Int -> Int -> [[Int]] -> Int
abc364f n _q lrcs
  | isOK      = sum ss
  | otherwise = -1
  where
    isOK = [1] == IS.elems isN
    (isN, ss) = mapAccumL step is0 $ sortOn (!! 2) lrcs
    is0 = IS.fromDistinctAscList [1 .. n]
    step is (l:r:c:_) = (is123, c * c2)
      where
        Just l1 = IS.lookupLE l is -- \ell
        c2 = IS.size $ fst $ IS.split (succ r) $ snd $ IS.split (pred l1) is -- [L1,R]にある要素数
        is1 = fst $ IS.split (succ l1) is
        is3 = snd $ IS.split r  is
        is123 = IS.union is1 is3
```

`IS.size` は $O(n)$ だが、一度数えたものは（$\ell$以外）消されるため、全体で$O(N+Q)$で済む。

## イベントソートによる方法

別解 by nyoguta で説明されているもの。
時系列の情報は配列で、現在使える重みは多重集合で表現した。

```haskell
import Data.Array
import qualified Data.IntMap as IM

abc364f :: Int -> Int -> [[Int]] -> Int
abc364f n _q lrcs = loop c0 1 emptyMIS
  where
    c0 = sum [c | _:_:c:_ <- lrcs]
    events = accumArray (flip (:)) [] (1, n) $
        concat [[(l, c), (r, - c)] | l:r:c:_ <- lrcs, l /= r]
    loop !acc i ws
      | i == n = acc -- Nまでたどり着いたら成功
      | otherwise =
          case lookupminMIS ws1 of
            Nothing -> -1 -- 次に張る辺がないならアウト
            Just w  -> loop (acc + w) (succ i) ws1
      where
        ws1 = foldl' step ws (events ! i)
        step s c
          | c < 0     = deleteMIS (- c) s
          | otherwise = insertMIS    c  s

type MultiIntSet = IM.IntMap Int
-- 多重集合の実装略
```

[提出したもの](https://atcoder.jp/contests/abc364/submissions/63479199)
時刻の幅が広いときは `Array` でなく `IntMap` を使うべき。[そうした版](https://atcoder.jp/contests/abc364/submissions/63477676)
区間で使える辺の最安コストを`[Maybe Int]` で求めておいて、`sequence` で `Maybe [Int]` にひっくり返すところが気に入っている。

[フレンズさんのヒント](https://x.com/kyopro_friends/status/1817195762121642085)の「クリーク」は筆が滑ってしまっているような。

# G - Last Major City

[問題 ABC364G](https://atcoder.jp/contests/abc364/tasks/abc364_g)

シグネチャを決める。

```haskell
abc364g :: [Int]   -- N,M,K
        -> [[Int]] -- Ai,Bi,Ci
        -> [Int]   -- 答え
```

ABC395Gから
https://x.com/climpet/status/1895832199934722384
G、ABC364GをN回繰り返すだけで間に合う

で流れてきた。

[フレンズさんいわく](https://x.com/kyopro_friends/status/1895843827975626916)
このスライドが詳しいのだ！
https://www.slideshare.net/wata_orz/ss-12131479
p.50～53で言及されてはいるけど、これだけでは何とも。

https://x.com/terry_u16/status/1817194293725188325
とりあえずwataさんの爆速最小シュタイナー木ライブラリを見に行って
→
https://x.com/wata_orz/status/1667842772861333504
シュタイナー木の厳密最適解を爆速で求めるライブラリです
https://github.com/wata-orz/steiner_tree

どれを読んでもなかなか理解し難い話だったけれど、ABC395GのPythonコード例で何となく理解した。

グラフ中の特定のノード群（これをターミナルと呼ぶ）を連結にする最も安い辺のコスト合計を求めたい。
動的計画法で、ターミナルのノード集合を特定の頂点 $v$ とそれ以外の集合 $X$ に分けて $\textit{Cost}[X][v]$ の形で求める。
（なのでこの問題では $X = \{1,\dots,K-1\}, v = i$ とできて座りがよい。）
$K \leq 10$ と小さいので、$X$ は集合のビット表現を用いて表せるので、$\textit{Cost}[X][v]$ は整数添え字の配列で表現する。

- $|X| = 0$ の場合、$\textit{Cost}[\emptyset][v] = 0$ である。
- $|X| > 0$ の場合、2段階の計算を行う。
  - 分割ステップ：$X$ を真に2分割するあらゆるやり方 $(Z,W)$ s.t. $X = Z \cup W, Z \cap W = \emptyset$ について
$C_1[v] = \min_{Z,W} (\textit{Cost}[Z][v] + \textit{Cost}[W][v])$
  - 分配ステップ：グラフにノード0を追加し、$C_{0,v} = C_1[v]$ という辺を追加したグラフにおける、ノード0から各ノード$v$への距離 $d[v]$ をダイクストラ法で求める。
  - $\textit{Cost}[X][v] = d[v]$ となる。
- $|X| = 1$ のとき、真の二分割は存在しないので分割ステップが行えないが、代わりに、
  - $\textit{Cost}[\{u\}][u] = 0, \textit{Cost}[\{u\}][v \neq u] = \infty$ とする。
  - 分配ステップは同様に行う。

### 実装

```haskell
import Data.Array.UArray

abc364g :: [Int] -> [[Int]] -> [Int]
abc364g [n, _m, k] abcs = ...
  where
    k1 = pred k
    tooBig = div maxBound 4 :: Int
-- グラフ
    g :: Array Int [(Int,Int)]
    g = accumArray (flip (:)) [] (1,n) $
      [(a,(b,c)) | a:b:c:_ <- abcs] ++
      [(b,(a,c)) | a:b:c:_ <- abcs]
```

ノード1～$K-1$にビット0～$K-2$を対応させる。
```haskell
import Data.Bits

type BitSet = Int
```

それら全て
```haskell
    core :: BitSet
    core = bit k1 - 1
```

要素数を数える
```haskell
    bsSize :: BitSet -> Int
    bsSize bs = popCount bs
```

最小の番号のノード番号（1始まりに戻る）
```haskell
    theBit :: BitSet ->Int
    theBit bs = popCount $ bs .^. pred bs
```

分割を全て列挙する
先頭は必ず $(X,\emptyset)$
```haskell
    powerIntSet :: BitSet -> [(BitSet,BitSet)]
    powerIntSet bs = takeWhile (uncurry (>)) $ loop bs
      where
        loop x = (x, bs .^. x) : loop (bs .&. pred x)
```
0からカウントアップすると、$X$に含まれない要素の処理に手間取るが、
カウントダウンと `(.&.)` によるマスクを使うと、不要な部分を飛ばして効率的に全列挙できる。

$\textit{Cost}[X][v]$ 配列は、二次元配列ではなく、$X$ に関して $v$ が一斉に計算されるため入れ子で作る。
```haskell
    cost :: Array BitSet (UArray Int Int)
    cost = listArray (0, core) $ map build [0 .. core]
```

各要素を求める関数 `build`
$X$ の要素数が0,1,2以上、により動作が切り替わる。
```haskell
    build :: BitSet -> UArray Int Int
    build is =
      case bsSize is of
        0 -> listArray (1, n) $ repeat 0
        1 -> sending $ accumArray (flip const) tooBig (1, n) [(theBit is, 0)]
        _ -> sending $ splitting is
```

分割ステップは、`powerIntSet` で得られる分割のうち、先頭以外について自己参照した結果を足し合わせる。
```haskell
    splitting :: BitSet -> UArray Int Int
    splitting bs = accumArray min tooBig (1, n)
      [ (v, c1 + c2)
      | (bs1, bs2) <- tail $ powerIntSet bs
      , ((v, c1), c2) <- zip (assocs $ cost ! bs1) (elems $ cost ! bs2)]
```

分配ステップでは、ダイクストラ法を用いて距離を更新する。
```haskell
    sending :: UArray Int Int -> UArray Int Int
    sending costbs = runST $ do
        arr <- dijkstra (0, n) ef 0
        listArray (1, n) . map (min tooBig) . tail <$> getElems arr
      where
        ef 0 = filter ((tooBig >) . snd) $ assocs costbs
        ef a = g ! a
```

$\textit{Cost}[\\{1,\dots,K-1\\}][v]$ が求まれば、その $v = K,\dots,N$ の値が答えである。

```haskell
abc364g [n, _m, k] abcs = drop k1 $ elems $ cost ! core
  where
    ...
```

[提出：時間ギリギリ4732ms](https://atcoder.jp/contests/abc364/submissions/63461668)
<!-- 自分にできるのはここまでだが、-->
なお、Haskellでも[551msで終わらせる](https://atcoder.jp/contests/abc364/submissions/56123528)ことも可能なようだ。
wata_orz氏の示している枝刈りとか入っているのだろうか…