ABC330 A～F をHaskellで

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

---

A - Counting Passes

問題 ABC330A

シグネチャを決める。

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

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

B - Minimize Abs 1

問題 ABC330B

シグネチャを決める。

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$ でクランプした値が要求されている。

結果

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

C - Minimize Abs 2

問題 ABC330C

シグネチャを決める。

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

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

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

結果

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

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

import qualified Data.ByteString.Char8 as BS

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

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

結果

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

シグネチャを決める。

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で見てください。

セグメント木？

アライさんによるとセグメント木で解けるという。

• セグメント木の第$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
IOArrayをつかったmex版より速いとか立場ないな。

別解解説

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

F - Minimize Bounding Square

問題 ABC330F

シグネチャを決める。

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

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

考える

（この考え方はアライさん解説と同じアプローチのようだ。）

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

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

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

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

公式解説たち

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

わかりやすい最後のアプローチを実装した。1526ms, 105MB