ABC330 A～F をHaskellで

宿題：Eをセグメント木で解くためのセグメント木ライブラリの機能追加
宿題：Fの自分答案のバグ解明

----

# A - Counting Passes

[問題 ABC330A](https://atcoder.jp/contests/abc330/tasks/abc330_a)

シグネチャを決める。

```haskell
abc330a :: Int   -- N
        -> Int   -- L
        -> [Int] -- Ai
        -> Int   -- 答え
abc330a _n l as = length $ filter (l <=) as
```

問題文の要求どおり、条件を満たすものだけ取り出し、その個数を数えた。

# B - Minimize Abs 1

[問題 ABC330B](https://atcoder.jp/contests/abc330/tasks/abc330_b)

シグネチャを決める。

```haskell
abc330b :: Int   -- N
        -> Int   -- L
        -> Int   -- R
        -> [Int] -- Ai
        -> [Int] -- 答え
```

また目の滑る問題文…

$[L,R]$という区間と、ある$A$が指定されるとき、次の二つの条件を満たす$X$を求めよ。
という問題を$A_1$～$A_N$について解け。

- 条件1 : $L \leq X \leq R$
- 条件2 : $\forall Y ; L \leq Y \leq R, | X - A | \leq | Y - A |$

$L \leq A \leq R$ のときは、$X = A$ とすれば、$LHS = | X - A | = 0$ なので確実に $LHS \leq RHS$ となる。
$A < L$ のとき、$L \leq X,Y$ より、$LHS = X - A, RHS = Y - A$ ここで $LHS \leq RHS$ を満たすには $X = L$
$R < A$ のとき、$X,Y \leq R$ より、$LHS = A - X, RHS = A - Y$ ここで $LHS \leq RHS$ すなわち $-X \leq -Y, X \geq Y$ を満たすには $X = R$

結局、$A$ を $L,R$ でクランプした値が要求されている。

## 結果

```haskell
abc330b _n l r = map (max l . min r)
```

# C - Minimize Abs 2

[問題 ABC330C](https://atcoder.jp/contests/abc330/tasks/abc330_c)

シグネチャを決める。

```haskell
abc330c :: Int  -- D
        -> Int  -- 答え
```

つまり、二つの平方数の和（もしくは片方が0で一つの平方数）で、$D$を超えても超えなくてもいいのでなるべく近い値を作って、その誤差を最小にせよ、ということ。

$D$以下の平方数を$X^2$の候補として全て調べ、$D$との差をもう一つの平方数で埋めるために、$D-X^2$以下の最大の平方数と、その次の平方数の両方について誤差を調べる。
また、$D$を超える平方数について、$Y=0$としてそれ自体との差も候補に入れる。

## 結果

```haskell
abc330c :: Int -> Int
abc330c d = minimum $
    x2b - d :
    [ abs (x2 + y * y - d)
    | x2 <- x2a
    , let sqy = sqrt $ fromIntegral $ d - x2
    , y <- [floor sqy .. ceiling sqy]
    ]
  where
    (x2a, x2b:_) = span (d >=) $ map (^ 2) [1..]
```

問題文の「非負整数」を「正の整数」と勝手に誤読して、答えがずっと合わなくてベソをかいていたのは秘密。

# D - Counting Ls

[問題 ABC330D](https://atcoder.jp/contests/abc330/tasks/abc330_d)

シグネチャを決める。
入力が多くなってきたので `Data.ByteString` を使う。

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

abc330d :: Int             -- N
        -> [BS.ByteString] -- Si
        -> Int             -- 答え
```

全ての `o` の位置について、同じ行にある他の `o` と、同じ列にある他の `o` が求める位置関係をひとつ作るので、その個数-1の積をとり、その総和を求める。
行と列の`o`の個数をあらかじめ数えておかないと無駄が多い。

## 結果

```haskell
abc330d0 n ss = sum
    [ pred l * pred c
    | (l, s)   <- zip ls ss           , l > 1
    , (c, 'o') <- zip cs (BS.unpack s), c > 1
    ]
  where
    ls = map (BS.count 'o') ss
    cs = map (\i -> length [() | s <- ss, 'o' == BS.index s i]) [0 .. pred n]
```

# E - Mex and Update

[問題 ABC330E](https://atcoder.jp/contests/abc330/tasks/abc330_e)

シグネチャを決める。

```haskell
abc330e :: Int   -- N
        -> Int   -- Q
        -> [Int] -- Ai
        -> [[Int]] -- i_k x_k
        -> [Int] -- 答え
```

## ストレートに解く

### mexの実現

整数集合を、連続する値 $x, x+1, \dots, y$ が含まれているとき、$x$を$y$に映す（$x \mapsto y$ と表す）写像として表現する。
- 値$z$がこれに含まれるかどうかは、$z$以下のキーを`lookupLE`して、その値が$z$以上かどうかでわかる。
- 含まれていない値$z$を追加するには、元から $z-1, z+1$ が含まれていたか否かによって、
  - 両方含まれていたら、両側の区間を一つに繋ぐ
  - 片方含まれていたら、それを伸ばす
  - どちらもなければ、$z \mapsto z$ という対応を追加する
- 含まれている値$z$を取り除くには、追加の逆で場合分けをして対処する
- $z$以上で含まれていない最小値を探すには、$z$以下のキーを`lookupLE`して、何も見つからなければ$z$自体、何かが見つかったときその値が$z$未満なら$z$、$z$以上ならばその値+1が捜し物である。

### 異なるデータ構造との連携

上で表現できたmexだけでは問題の要求を満たすことができない。
$A_i$の内容を多重集合でも表して、ここから値がなくなった場合にだけmexからも値を取り除く。
$A_i$の内容を書き換え可能な配列でも保持して、どんな値が消えてどんな値が加わるかを追跡する必要がある。

### 結果

配列を `Data.Array.IO` で実現した上、mexも大きいので[提出 1825ms 130MB](https://atcoder.jp/contests/abc330/submissions/47953414)で見てください。

## セグメント木？

[アライさんによると](https://twitter.com/kyopro_friends/status/1728411799882801501)セグメント木で解けるという。

- セグメント木の第$k$要素は、$A_i = k$ である値の個数にする。これを$C[k]$と書く。
- セグメント木の演算は $\min$ とする。つまりセグメント木に$[l,r)$でクエリをすると$\min(C[l],C[l+1],\dots,C[r-1])$ が得られる。
- $\min(C[0],C[1],\dots,C[x]) = 0$となる最小の$x$がmex

この最後の演算は、セグメント木の外から二分探索をするのではなくて、セグメント木の構造がそもそも二分木なので、左の子の結果が0なら左に、そうでなければ（必ず0な）右の子に進み、葉まで到達したときのその葉の番号を答えとする、セグメント木に内蔵されるべき機能である。

これはACLには付いているようだが、自前のライブラリには付けていないので今後の課題にしておきます。

ちなみに、セグメント木の要素数は$A_i$の上限を上回る必要があるので添え字は0から $10^9+1$ まで。とするとメモリがあふれるので、初期状態がびっちりと0から$N-1$までを塞ぎ、かつクエリが総出で続きを塞いでも $N+Q-2$までしか塞げないので、$4 \times 10^5$ まであればよい。これを超える値は単に無視する。

## 公式解説のやり方

多重集合で$A_i$の現状が把握できていれば、それと連動して「$A_i$に含まれていない整数の集合」を追跡するだけでいい、言われてみればそのとおり。ただし下限と上限は必要。

無精して`IntMap`を配列代わりにしたimmutable版で通ってしまった。[1745ms, 166MB](https://atcoder.jp/contests/abc330/submissions/48036884)
IOArrayをつかったmex版より速いとか立場ないな。

## 別解解説

『[「区間を set で管理するテクニック」と俗に呼ばれている手法](https://atcoder.jp/contests/abc330/editorial/7754)』というタイトル以上のことはC++で書いてあるのを斜め読みすると、上の mex では区間 $[x,y]$ を写像`IntMap Int`の対応 $x \mapsto y$ で表したところを、$(x,y)$という対の集合`Set (Int,Int)`で表すというバリエーションの話のようだ。

# F - Minimize Bounding Square

[問題 ABC330F](https://atcoder.jp/contests/abc330/tasks/abc330_f)

シグネチャを決める。

```haskell
abc330f :: Int     -- N
        -> Int     -- K
        -> [[Int]] -- Xi Yi
        -> Int     -- 答え
```

広大なグラウンドに石がいくつも落ちていて、巨大なトンボで上下左右から押して寄せる。
最後に正方形にまとめるその大きさをなるべく小さくしたい。
同時に押す石の個数と移動距離だけの労力がかかり、労力総計には上限がある。

## 考える

（この考え方は[アライさん解説](https://twitter.com/kyopro_friends/status/1728412964540309699)と同じアプローチのようだ。）

まず、縦軸と横軸は独立して考えてよい。
今、右と左の両方のトンボがいくつか石に当たっていて、さらに押し込むとき、石の少ない方を押す方が得になる。
左から押すとき、最初の石にトンボが当たった位置から始めて、新たに石に当たるたびに重さが増える。石が増えない間の重さは一定。X座標ごとに石がいくつあるかを数えると、どれだけの距離をいくつの石を押して進むことになるかを調べられる。
右から押すトンボについても、逆順に調べると同様の情報を取り出せる。
この両者を前から見比べて、軽い方を優先して押していき、左右のトンボ間の距離の距離ごとに、そうするのにかかる最小の労力総計が、トンボ間の距離0まで決められる。
これらを折れ線グラフの変曲点として、`IntMap`に入れておく。

この`IntMap`からグラフを読み解くことで、トンボの距離をある値にしたいときに必要な労力が求められる。
上下方向についても同じ事をする。
すると、任意の正方形の大きさについて、そうするために必要な労力が、左右方向と上下方向の労力の和として求められる。

正方形の大きさの最小値は0、最大値は現状（手を抜くなら最大値の$10^9$）で、労力合計が $K$ 以下で済む最小の正方形の大きさを、二分探索で求めることができる。

という方針で書いて[WA x 7](https://atcoder.jp/contests/abc330/submissions/48028582)になってしまった。
AtCoder Companionsさんにも「そんな間違い見た事ねぇわ」と言われてしまって打つ手なし。
次項のAC解と答え合わせするQuickCheckを走らせても反例が見つからない。
テストケースの公開を待つ。

## 公式解説たち

- [公式](https://atcoder.jp/contests/abc330/editorial/7753)は、縦と横のうち、大きい方を押す。向かい合ったトンボのうち、軽い方を押す、コストが足らなくなったら終了、という感じ？書いてあるとおり、1ずつ動かしているとキリがないので、まとめて押す必要があるのを正しく行うのが面倒そう。
- [Slope Trick](https://atcoder.jp/contests/abc330/editorial/7777)とは、ここで出てくるような折れ線グラフを上手いこと表現する手法のよう。それでどうやると（今回の問題Bの計算の総和）が高速に解けるのかは…
- [2N個の座標の中央値を求める別解](https://atcoder.jp/contests/abc330/editorial/7774)は、どんな計算をすればいいのかはとてもわかりやすい。ただ、どうしてそれでいいのかがさっぱりわからない。

わかりやすい最後のアプローチを実装した。[1526ms, 105MB](https://atcoder.jp/contests/abc330/submissions/48030855)