ABC407 A～F をHaskellで

# A - Approximation

[問題 ABC407A](https://atcoder.jp/contests/abc407/tasks/abc407_a)

シグネチャを決める。

```haskell
abc407a :: Int -- A
        -> Int -- B
        -> Int -- 答え
```

$A \div B = q \dots r$ とする。つまり $\displaystyle \frac{A}{B} = q + \frac{r}{B}$ である。
$B$が奇数であることに注意して、$\displaystyle \frac{r}{B} < \frac{1}{2}$ なら答えは $q$ さもなくば $q + 1$ となる。
条件式は $2r < B$ と変形できる。

## 結果

```haskell
abc407a a b
  | r + r < b = q
  | otherwise = succ q
  where
    (q, r) = divMod a b
```

# B - P(X or Y)

[問題 ABC407B](https://atcoder.jp/contests/abc407/tasks/abc407_b)

シグネチャを決める。

```haskell
abc407b :: Int    -- X
        -> Int    -- Y
        -> Double -- 答え
```

$6 \times 6 = 36$ 通りの全ての場合について調べ、条件を満たすものを数える。場合の数で割れば答え。

## 結果

```haskell
abc407b x y = fromIntegral c / 36
  where
    c = length [() | a <- [1 .. 6], b <- [1 .. 6], x <= a + b || y <= abs (a - b)]
```

# C - Security 2

[問題 ABC407C](https://atcoder.jp/contests/abc407/tasks/abc407_c)

シグネチャを決める。長いので `ByteString` で受け取る。

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

abc407c :: BS.ByteString -- S
        -> Int           -- 答え
```

## 自分の解法

$S$ の $i$ 文字めの数字を $D[i]$ とする。$S$ の長さを $N$ とする。
自分の操作は「Aを押して0を出す、Bを何回か押してそれをどれかの数字にする」の繰り返しになる。
$i$ 文字めについて、Bを押す回数を $R[i]$ とする。
この数字はさらに後続のBの押下により、さらに変化する。最終結果は $\displaystyle D[i] \equiv \sum_{k=i}^N R[k] \bmod 10$ になる。

もう少し平たく書くと  
$D[i] \equiv R[i] + R[i+1] + R[i+2] + \dots + R[N] \bmod 10$ 次の項は  
$D[i+1] \equiv R[i+1] + R[i+2] + \dots + R[N] \bmod 10$ 辺々引いて  
$D[i] - D[i+1] \equiv R[i] \bmod 10$

「次の数字との差だけ回せばヨシ」で、末尾まで考える必要がなくなってしまった。不思議。

Aを押す回数も加えて $\sum (1 + R[i])$ の和が答え。
`zipWith` を使うと $D[N]$ を数え忘れるので補正する。

```haskell
abc407c s = (dN +) $ sum $ between op $ map digitToInt $ BS.unpack s
  where
    op a b = succ $ mod (a - b) 10
    dN = succ $ digitToInt $ BS.last s

between :: (a->a->b) -> [a] -> [b]
between f xs = zipWith f xs $ tail xs
```

## フレンズさんのヒント版

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

<!--
> C問題は逆からシミュレーションなのだ！
> 逆から考えると
> ボタンA：末尾の0を取り除く
> ボタンB：Sの数字を全部1小さくする
> になって、「Sの最後が0になるようにボタンBを押す→ボタンAを押す」を繰り返せばいいのだ」
> ボタンBで実際にS全部を書き換えるとO(|S|^2)になってTLEするから、ボタンBが何回押されたかだけ覚えておいて、Sの最後が何になってるかをその場で計算すればいいのだ！
-->

時計を逆回しにして数えるとき「ボタンBが何回押されたか」はつまり $\sum_{k=i}^N R[i]$ で、これを $S[i]$ と置いて上の式  
$D[i] \equiv R[i] + R[i+1] + R[i+2] + \dots + R[N] \bmod 10$ 置き換えて  
$D[i] \equiv R[i] + S[i+1] \bmod 10$ 移項して  
$R[i] \equiv D[i] - S[i+1] \bmod 10$ これを使って  
$S[i] \equiv R[i] + S[i+1] \bmod 10$ を繰り返せと言っている。

```haskell
abc407c bs = sum $ snd $ mapAccumL step 0 [n1, pred n1 .. 0]
  where
    n1 = pred $ BS.length bs
    step s1 i = (s, succ r)
      where                            -- s1 = S[i+1]
        d = digitToInt $ BS.index bs i -- D[i]
        r = mod (d - s1) 10  -- R[i] ≡ D[i] - S[i+1] mod 10
        s = mod (r + s1) 10  -- S[i] ≡ R[i] + S[i+1] mod 10
```

# D - Domino Covering XOR

[問題 ABC407D](https://atcoder.jp/contests/abc407/tasks/abc407_d)

シグネチャを決める。

```haskell
abc407d :: Int     -- H
        -> Int     -- W
        -> [[Int]] -- Aij
        -> Int     -- 答え
```

$H, W \leq 20$ と思い込んで諦めてしまったが、実は $HW \leq 20$ というごく小規模の話で、総当たりをするだけだった。

(1,1) から (H,W) まで順にマスを見て、

- ドミノが既に置かれていたら何もできないので続きの結果をそのまま返す
- ドミノを置かれていないとき、以下の3通りの場合を計算して、最終結果の最大値を返す
  - 置かずに、その数を使う
  - 横に置く（右端でないとき）（右隣のマスもドミノが塞いでいないとき）
  - 縦に置く（下端でないとき）

という深さ優先探索を実装する。

## 結果

マスはたかだか20個なので、immutable arrayで書く。

```haskell
import Data.Array.Unboxed
import Data.Bits

abc407d :: Int -> Int -> [[Int]] -> Int
abc407d h w ass = dfs 0 f0 $ range ((1,1),(h,w))
  where
    f0 = listArray ((1,1),(h,w)) $ repeat False :: UArray (Int,Int) Bool -- ドミノが置かれているかフラグ配列の初期値
    a  = listArray ((1,1),(h,w)) $ concat ass   :: UArray (Int,Int) Int
    dfs acc _f [] = acc
    dfs acc f (ij@(i,j):ijs)
      | f ! ij    = dfs acc f ijs
      | otherwise = maximum $
          [dfs ac1 f  ijs | let !ac1 = xor acc $ a ! ij] ++
          [dfs acc f1 ijs | j < w, let ij1 = (i, succ j), not $ f ! ij1, let f1 = f // [(ij,True), (ij1,True)]] ++
          [dfs acc f2 ijs | i < h, let f2 = f // [(ij,True), ((succ i,j),True)]]
```

# E - Most Valuable Parentheses

[問題 ABC407E](https://atcoder.jp/contests/abc407/tasks/abc407_e)

シグネチャを決める。テストケース一つ分の計算を考える。

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

## ハマった

前から順にDPして、位置 $i$ に対して
- 開き括弧の開いている数 $p$ $(0 \leq p, p \leq i, p \leq 2N - i)$ をキー
- $p$ で達成できる総和の最大値を値

という表を更新していけば答えが得られる。
しかし $i = N$ のとき $p \leq N$ で、$O(N^2)$ になって計算量が大きすぎる。

## ヒントから

[フレンズさんいわく](https://x.com/kyopro_friends/status/1926276491555250553)
> ～「2個追加して1個丸をつける」を貪欲にやっていけばいいのだ。プライオリティキューでできるのだ！

正しい括弧列の性質から、どの位置でも、閉じていない開き括弧の個数が0以上である必要がある。
そして問題の性質として、開き括弧でない位置は閉じ括弧になる。（開きの数が減る）
つまり、先頭から任意の位置までの区間で、半数以上が開きである必要がある。

ここからがアイデアで、この条件を満たすことを先頭から考えると、
- 先頭は必ず開き
- 次から、2文字追加するごとに、開きと指定していなかった1文字を開きに指定する
これは、新規の2文字でなく、これまでの中から自由に選んでよい

このとき、問題の目標を達成するためには、選べる候補のうちで最大の値をもつマスを選べばよい。
つまり優先度付きキューに溜め込んでおけばよい。

### 結果

大きい方を優先するために、全てを符号反転して扱う。

```haskell
import qualified Data.Heap as PQ
import Data.List.Split
import Data.Tuple
import Data.Maybe

abc407e :: Int -> [Int] -> Int
abc407e _n (a:as) = (a -) $ sum $ snd $ mapAccumL step PQ.empty $ chunksOf 2 $ map negate as
  where
    step pq [a1] = (PQ.insert a1 pq, 0) -- 実際には何もしない
    step pq [a1, a2] = swap $ fromJust $ PQ.uncons $ PQ.insert a1 $ PQ.insert a2 pq
```

<!--
## カッコ問題について

[ひとのマシュマロ](https://x.com/kyopro_friends/status/1926968371087626346)に横から口を出すのもアレかもだけど…

Advent of Code の[最初(2015年)の最初(day1)](https://adventofcode.com/2015/day/1)（[拙訳](https://gotoki-no-joe.github.io/AdventOfCode-myAnswer/2015/day1.html)）も括弧にまつわる話だったなぁとか。
この問題文での正しい括弧列の定義
> 正しい括弧列とは、 `()` である部分文字列を削除することを 0 回以上繰り返して空文字列にできる文字列を指します。

も間違いではないけど少し手抜き感があって、
```
<括弧列> ::= ε | (<括弧列>) | <括弧列><括弧列>
```
という文法で定義するのが普通なのでは。

そして、括弧の並びが正しい括弧列かどうかの判定はよくあるタイプの問題で、パーサ書いてもいいんだけど、「対となる閉じ括弧がまだ出現していない開き括弧の個数」を先頭からカウントして、
- 途中でマイナスになったらアウト
- 最後にちょうど0になっていたら成功

が正しいことの十分条件、は考えたことあるよねみんな。
-->

# F - Sums of Sliding Window Maximum

[問題 ABC407F](https://atcoder.jp/contests/abc407/tasks/abc407_f)

シグネチャを決める。

```haskell
abc407f :: Int    -- N
        -> [Int]  -- Ai
        -> [Int]  -- 答え
abc407f n as = ...
  where
```

ぜんぜんわからないので[ヒント](https://x.com/kyopro_friends/status/1926277608263544988)をもらう。

話が複数段階あるのが難しかった理由かな。

## ステップ1

長さ1の連続部分列はN個、長さ2は$N-1$個、…、長さNは1個ある。
これらに対して、各 $A_i$ がその部分列の最大値であるような場合がいくつあるかを知りたい。

$A_i$ の大きい方から順に考えて、
$i$ より左と $i$ より右に、未使用な値（つまり $A_i$ 以下の値）がいくつあるかを数える。
左右がその範囲に収まる部分列全てについて、最大値は $A_i$ となる。

という区間を調べるために、「使用済みな整数の集合」を状態にしてループする。
番兵として0と$N+1$を最初から入れておく。

```haskell
import qualified Data.IntSet as IS
import Data.Function

    (_, alrs) = mapAccumL step is0 $ sortBy (flip compare `on` fst) $ zip as [1 ..]
    is0 = IS.fromList [0, succ n]
    step is (ai, i) = (IS.insert i is, (ai, i - l, r - i))
      where
        Just l = IS.lookupLT i is
        Just r = IS.lookupGT i is
```

`alrs` は $A_i$ の大きい順に、$A_i$ の値、位置 $i$ の左右で未使用な値の個数、の3項組のリスト。

## ステップ2

長さkを気にしないとき、`alrs` の要素 $(a,l,r)$ について、$a$ を最大値とする部分列の個数は $(l+1)(r+1)$ である。
長さを考慮するとき、$(0,0),(l,0),(0,r),(l,r)$ を頂点とする長方形の内部の格子点について、
$x + y = k - 1$ という直線が通過する個数が部分列の個数になる。

一般性を損なわずに $l \leq r$ と仮定して、この値は $k=0$ から順に
これは $1, 2, 3, \dots, l, l+1, l+1, \dots, l+1, l, l-1, \dots, 1$ という長さ $l + r + 1$ の列となり、
以降は0になる。

これをkごとに足し合わせれば答えになるはず。

```haskell
import Data.Array.Unboxed

abc407f n as = elems arr
  where
    ...
    arr :: UArray Int Int
    arr = accumArray (+) 0 (1, n)
      [ (k, a * m)
      | (a, l, r) <- alrs, let ll = min l r, let rr = max l r, let l1 = succ ll
      , (k, m) <- zip [1 ..] $ [1 .. ll] ++ replicate (succ rr - ll) l1 ++ [ll, pred ll .. 1]
      ]
```

しかしこれでは TLEx5 になる。$O(N^2)$ の演算をしているので当然。

## ステップ3

ステップ2で、$N$ 個の台形状の数列を作り、要素ごとに足し合わせた。
個々に作る代わりに、全てを足し合わせた数列を一度に作るために、累積和による積分を行う。

つまり、ひとつの台形数列
$0, 1, 2, \dots, l, l+1, \dots, l+1, l, \dots, 1, 0, 0, \dots$ は前後の差分をとると
$1, 1, 1, \dots, 1, 0, \dots, 0, -1, -1, \dots, -1, 0, 0, \dots$ となり、もう一度すると
$1, 0, \dots, 0, -1, 0, \dots, 0, -1, 0, \dots, 0, 1, 0, \dots$ となる。
この2階差分を全ての台形について足し合わせてから、2度累積和を行うと、全体を足し合わせた数列が$O(3N)$で求められる。

```haskell
abc407f n as = tail $ scanl' (+) 0 $ tail $ scanl' (+) 0 $ elems arr
  where
    ...
    arr :: UArray Int Int
    arr = accumArray (+) 0 (0, pred n) $ concatMap alr2e alrs
    alr2e (a, l, r) = [(i,b) | (i,b) <- [(0,a),(l,-a),(r,-a),(l + r,a)], inRange (0, pred n) i]
```

ヒントには
> 遅延セグ木でできるのだ！　工夫すればimos法でもできるのだ

とあったが、後者しか思いつかなかった。

# G - Domino Covering SUM

D問題より100倍広く、その代わりにXORではなく和をとる。
いずれかの幅がある程度制限されていれば、ドミノで埋まっているマスのパターンごとの最大値を持ってDPできるが、この問題では制約がないので最大で $44 \times 45$ マスになり、計算量が爆発する。

[フレンズさんいわく](https://x.com/kyopro_friends/status/1926277823246843929)
> アライグマ「G問題はフローなのだ！　
> マスを頂点、隣接するマスの間に重みAij+Ai'j'の辺を張ったグラフで、最小重みマッチングを求めれば良いのだ。
> 全部の辺の重みに定数Mを足して重みを0以上にしてから最小費用流を求めれば、min_k(流量kの最小費用-kM)で求まるのだ！」

蟻本に最小費用流の項があるのは確認した。