ABC393 A～F をHaskellで

# A - Poisonous Oyster

[問題 ABC393A](https://atcoder.jp/contests/abc393/tasks/abc393_a)

消費期限10日過ぎた加熱用の生牡蠣を生で食べた話があったところでのこの出題。

シグネチャを決める。

```haskell
abc393a :: String -- S1
        -> String -- S2
        -> Int    -- 答え
```

答えが X であるのはどういう状況のときか、を書き出してみる。

| 答え | 高橋 | 青木 |
|:-:|:-:|:-:|
| 1 |sick|sick|
| 2 |sick|fine|
| 3 |fine|sick|
| 4 |fine|fine|

fineを1、sickを0の2進数で解釈すると、答え-1の値になる対応が見えてくる。

## 結果

```haskell
import Data.Bool

abc393a :: String -> String -> Int
abc3c3a (t:_) (a:_) = succ $ bool 0 2 (t == 'f') + bool 0 1 (a == 'f')
```

# B - A..B..C

[問題 ABC393B](https://atcoder.jp/contests/abc393/tasks/abc393_b)

シグネチャを決める。

```haskell
abc393b :: String -- S
        -> Int    -- 答え
```

注目する位置を先頭から1文字ずつ進め、通過済みの、より左の部分は逆順にリストに繋ぐ。
注目する位置が `B` のとき、より左の部分とより右の部分が `(A,C)` となる組の個数を数える。

## 結果

```haskell
abc393b s = sum $ loop [] s
  where
    loop _ [] = []
    loop ls (c:rs)
      | c == 'B' = cnt : loop (c:ls) rs
      | otherwise =      loop (c:ls) rs
      where
        cnt = length $ filter (('A','C') ==) $ zip ls rs
```

# C - Make it Simple

[問題 ABC393C](https://atcoder.jp/contests/abc393/tasks/abc393_c)

シグネチャを決める。

```haskell
abc393c :: Int -- N
        -> Int -- M
        -> [[Int]] -- ui,vi
        -> Int -- 答え
```

重複を除去して数えるために、辺の集合を作り、その要素数を数える。
ただし、自己ループは集合に加えず弾く。
例1の `2 3` と `3 2` のような場合を同一視するため、小さい順に正規化する。

## 結果

```haskell
import qualified Data.Set as S

abc393c :: Int -> Int -> [[Int]] -> Int
abc393c _n m uvs = m - S.size s
  where
    s = S.fromList [(min u v, max u v) | u:v:_ <- uvs, u /= v]
```

# D - Swap to Gather

[問題 ABC393D](https://atcoder.jp/contests/abc393/tasks/abc393_d)

シグネチャを決める。Sは長いので `ByteString` にしておく。

```haskell
import qualified Data.ByteString.Char8 as BS

abc393d :: Int -- N
        -> BS.ByteString -- S
        -> Int -- 答え
```

全体で `1` は $C$ 個あるとする。

間に `0` が $Y$ 個あるとき、これを詰めることを考える。
それより左に `1` が $X$ 個あるとき、これらを右に動かす手間は $XY$ である。
より右には `1` が $C - X$ あり、それらを左に動かす手間は $(C-X)Y$ である。
この小さい方を選ぶ。

`group` を使って、`1` の並びの塊と `0` の並びの塊に分け、その長さのリストを持つ。
先頭と末尾は `1` のものとする。
- 個数リストが長さ1のとき、目標は達成されている。
- 個数リストが長さ3以上のとき、`x:y:z:xs` として、`y` 個の0の並びを詰めるコストは上のように計算できる。詰めた後の状況は `(x+z):xs` となるので、同じ事を繰り返す

とすればよい。

## 結果

```haskell
import Data.Bool

abc393d :: Int -> BS.ByteString -> Int
abc393d _n s = sum $ loop ks
  where
    ks0 = map BS.length $ BS.group s
    ks = bool id init (BS.last s == '0') $ bool id tail (BS.head s == '0') ks0
    c = BS.count '1' s
    loop [_] = []
    loop (x:y:z:xs) = y * min x (c - x) : loop (x+z:xs)
```

# E - GCD of Subset

[問題 ABC393E](https://atcoder.jp/contests/abc393/tasks/abc393_e)

シグネチャを決める。

```haskell
abc393e :: Int -- N
        -> Int -- K
        -> [Int] -- Ai
        -> [Int] -- 答え
```

なんもわからん。

https://x.com/kyopro_friends/status/1890760786269655550

ゼータ関数！？

なんもわからんが、克明に計算手順が書かれているから実装することはできる。

## 結果

```haskell
import Data.Array.Unboxed
import Data.Bool

abc393e :: Int -> Int -> [Int] -> [Int]
abc393e n k as = map (ans !) as
  where
    ub = maximum as -- 10^6決め打ちでもいいけど
    cnt0, cnt, ans0, ans :: UArray Int Int
    -- A中の値iの個数
    cnt0 = accumArray (+) 0 (1,ub) [(a,1) | a <- as]
    -- A中の値iの倍数の個数：ここでAiに存在しない数についても勘定しているのがミソ？
    cnt = listArray (1,ub) [sum [cnt0 ! j | j <- [i, i + i .. ub]] | i <- [1 .. ub]]
    -- 値iの倍数がA中にK個以上あるとき、A中のK個の数をうまく選べばgcdをiにできる（最大値）
    -- そうでない数はもっと小さい数にしかできない。具体的な値はまだ不明
    ans0 = listArray (1,ub) [bool 0 i (c >= k) | (i,c) <- assocs cnt]
    -- 値iについて、その約数jのans0の最大値が、値iを含むK個の数をA中から選んで作れるgcdの最大値
    ans = accumArray max 0 (1,ub) [(j, a) | (i,a) <- assocs ans0, j <- [i, i + i .. ub]]
```

アライさんの説明だと、mutable arrayの値を壊さないようにループの向きを気にしたりしてDPだと捉えているけれど、immutable arrayの観点から解釈すると、何かを単に数えているだけに見える。

### 蛇足

`ans0` の値 0 は、max をとったときに無視される値として選んでいるので、もっと厳密に、`Maybe` で包んでやる方法も考えられる。
また、`ans` を配るDPで計算すると `ans0` の全てを舐めることになるが、そもそもこれは $A_i$ に出現する値だけを計算すればよいので、その約数全ての `ans0` の値を集めてくる形にすれば不要な箇所の計算をlazyに回避できる。

```haskell
    ans0 :: Array Int (Maybe Int)
    ans0 = listArray (1,ub) [bool Nothing (Just i) (c >= k) | (i,c) <- assocs cnt]
    ans :: Array Int Int
    ans = listArray (1,ub) $ map (maximum . catMaybes . map (ans0 !) . factors) [1 .. ub]

-- 約数列挙
factors :: Int -> [Int]
-- 実装略
```

しかしこうすると、ひとつの `factors` の計算に $O(\sqrt M)$ （ここで$M = \max A_i$ とする）かかるため、全体で $10^9$ オーダーの計算量になってTLEする…

`cnt` や `ans` の二重ループの方が $O(M^2)$ になりそうなものだが、各 $i$ に対して $M/i$ 要素しか触らないので、全体では
$$M + M/2 + M/3 + \dots + M/M = M(1 + 1/2 + 1/3 + \dots + 1/M)$$
ググると
$$\log (n + 1) < \sum_{k=1}^n \frac{1}{k} < 1 + \log n$$
という式が[見つかって](https://manabitimes.jp/math/627#5) 結局 $O(M \log M)$ で収まるということか。

# F - Prefix LIS Query

シグネチャを決める。

```haskell
abc393f :: Int -- N
        -> Int -- Q
        -> [Int] -- Ai
        -> [[Int]] -- Ri, Xi
        -> [Int] -- 答え
```

頭が回らないのでヒントをもらう。

https://x.com/kyopro_friends/status/1890761194237046800

問題文はオンラインクエリっぽくても、オフラインでやるというのは常套手段だった。

## 結果

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

abc393f :: Int -> Int -> [Int] -> [[Int]] -> [Int]
abc393f n q as rxs = elems ans
  where
-- Aiまで調べた後に対応するべきクエリのリストが qarr[i]
    qarr = accumArray (flip (:)) [] (1,n) [(r, (i,x)) | (i, r:x:_) <- zip [1 ..] rxs]
-- LISを求めつつ、クエリに対応する
    (_, anss) = mapAccumL step (IM.singleton 0 0) $ zip as $ elems qarr
-- クエリの答えを番号順に戻す
    ans = array (1,q) $ concat anss
-- LIS計算とクエリ対応のステップ
    step im (ai, ixs) = (im1, map f ixs)
      where
    -- LIS部
        Just (_, cnt) = IM.lookupLT ai im -- 末尾Ai未満な最長のLISの~末尾の値~と長さ
        im1 = case IM.lookupGE ai im of -- Ai以上なLISがあれば、その長さもcnt+1と等しいはずなので、単調性からこれは消す
          Just (ak,_) | ak > ai   -> IM.insert ai (succ cnt) $ IM.delete ak im
                      | otherwise -> im
          Nothing                 -> IM.insert ai (succ cnt) im
    -- クエリ部
        f (i, x) = (i, ans)
          where
            Just (_, ans) = IM.lookupLE x im1
```

# G - Unevenness

https://x.com/kyopro_friends/status/1890761389108560146

公式解説を開いてそっ閉じ。