ABC338 A～F をHaskellで

# A - Capitalized?

[問題 ABC338A](https://atcoder.jp/contests/abc338/tasks/abc338_a)

Regular Expressionがあればそれで一発？

シグネチャを決める。

```haskell
import Data.Char

abc338a :: String -- S
        -> Bool   -- 答え
abc338a (c:cs) =isUpper c && all isLower cs
```

# B - Frequency

[問題 ABC338B](https://atcoder.jp/contests/abc338/tasks/abc338_b)

シグネチャを決める。

```haskell
abc338b :: String -- S
        -> Char   -- 答え
```

## 結果

配列で数える。
最頻の文字が複数ある場合に対応するため、最大個数を求めるステップと、その個数だけある文字を取り出す段階を分ける。

```haskell
import Data.Array

abc338b :: String -> Char
abc338b cs = head [c | (c,k) <- assocs cnt, k == x]
  where
    cnt = accumArray (+) 0 ('a','z') [(c, 1) | c <- cs]
    x = maximum $ elems cnt
```

個数を左、文字を右にした対の最大値を取り出すと、最頻の文字の中でアルファベット順で最も遅いものが選ばれてしまうので、個数をマイナスにして最小値を取り出すと唯一に決まる。

```haskell
import Data.Array
import Data.Tuple

abc338b :: String -> Char
abc338b cs = snd . minimum . map swap . assocs $
             accumArray (+) 0 ('a','z') [(c, -1) | c <- cs]
```



# C - Leftover Recipes

[問題 ABC338C](https://atcoder.jp/contests/abc338/tasks/abc338_c)

シグネチャを決める。

```haskell
abc338c :: Int  -- N
        -> [Int] -- Qi
        -> [Int] -- Ai
        -> [Int] -- Bi
        -> Int   -- 答え
```

とりあえず料理Bを無視して料理Aだけ作るとしたとき、作れる個数は $Q_i / A_i$ の最小値。
Aを作る個数を0からこの上限まで試して、残りの材料で作れる料理Bの個数も同様に導く。
合計の最大値をとる。

## 結果

```haskell
abc338c _n qs as bs = maximum [s + tfun s | s <- [0..smax]]
  where
    smax   = minimum [div q a | (q,a) <- zip qs as, a > 0]
    tfun s = minimum [div (q - a * s) b | (q,a,b) <- zip3 qs as bs, b > 0]
```

## 別解

$s = 0,1,\dots$について $Q_i - s A_i$ を求める代わりに、$Q_i$から$A_i$を引くことを繰り返す。$s$の最大値は引けなくなったときがそれなので自然に判る。

```haskell
abc338c :: Int -> [Int] -> [Int] -> [Int] -> Int
abc338c _n qs as bs =
    maximum $
    zipWith (+) [0..] $       -- Aを作る個数を加える
    map bfun $                -- Bの作れる個数
    takeWhile (all (0 <=)) $  -- どれかがマイナスになったら終了
    iterate afun qs           -- QiからAiを引くことを繰り返す
  where
    afun xs = zipWith (-) xs as -- Aをもう一つ作る
    bfun rs = minimum [div r b | (b,r) <- zip bs rs, b /= 0] -- Bの作れる個数
```

`takeWhile`～`iterate`は`unfoldr`でかっこよくなるけど、そこまで凝らなくてもね。

```haskell
    qs : unfoldr step qs -- QiからAiを引くことを、引けなくなるまで繰り返す
  where
    step qs
      | all (0 <=) qs1 = Just $ (qs1, qs1)
      | otherwise = Nothing
      where
        qs1 = zipWith (-) qs as
```

# D - Island Tour

[問題 ABC338D](https://atcoder.jp/contests/abc338/tasks/abc338_d)

シグネチャを決める。

```haskell
abc338d :: Int  -- N
        -> Int  -- M
        -> [Int] -- Xi
        -> Int   -- 答え
```

島は数珠つなぎになっているので、元々はどちら向きにでも回ることができる。島の番号が増える向きを「順回り」、逆を「逆回り」と呼ぶことにする。
橋をどれか一つ落とすと、どちらか片方でしか行けなくなる。（逆に言うと、どちらかの回りが必ず妨害される。）
島$A$と$B$ ($A < B$)の間を移動するとき、順回りで渡る橋は$F = B - A$本、逆回りでは$R = N - F$本。
順回りで使う橋のどれかを落としたとき、逆回りの行程が必要になる。順回りで使う橋とは、橋$A$から$B-1$のこと。
逆に、それ以外の橋を落としたときは、順回りの行程が必要になる。全ての橋について、どちらかの行程が必ず必要である。
全ての行程について、その橋を落としたときに必要になる行程を足し込むことで、ツアー全体の行程が得られる。その最小値が求める値。

しかしこれを素朴にやると、要素$N$個の配列に$M$回の足し込みを行うため$O(NM)$で間に合わない。

足し込むべき行程は、橋$A$から橋$B-1$が$N - F$で、それ以外、つまり1から$A-1$までと$B$から$N$までは$F$で一定値である。1から順に見て変化するのは1,X,Yのとき。
これは累積和による積分の出番。

## 結果

```haskell
import Data.Array

abc338d :: Int -> Int -> [Int] -> Int
abc338d n _m xs = minimum $ scanl1 (+) $ elems da  -- 累積して最小値をとる
  where
    da = accumArray (+) 0 (1,n)
      [ p
      | (x0, x1) <- zip xs (tail xs)         -- Xi, Xi+1
      | let (a, b) = (min x0 x1, max x0 x1)  -- A < B にする
      , let f = b - a                        -- F
      , let r = n - f                        -- R
      , p <- [ (1, f)                        -- 1～にFを足す
             , (a, r - f)                    -- A～にRを足すように差分をインパルス
             , (b, f - r)                    -- B～にFを足すように差分をインパルス
             ]
      ]
```

<!--
### いわゆる「いもす法」というあだ名について

当初提案された「いもす法」は確か、二次元累積和に限定した話だったはずなのが、いつの間にか累積和全般をそう呼ぶようになってしまったのが頂けない。
提唱者自身の固有名詞で呼ぶことで、内容がわからない、いわゆる「内輪受け」な呼称であることがひっかかる。「ダイクストラ法はよくていもす法は駄目な理由を言え」と言われると困るけど、多分彼はもっと将来にもっと凄いアルゴリズムを発明して、未来のアルゴリズムの教科書にはそっちにその名前が付くから、今違うものに使ってしまうのはもったいないんじゃないかな。あと、自称ではあるけど本名でないとか。
累積和には、ここで使ったような、差分関数を積分することで関数復元をする使い方と、もう一つ別の使い方があるので（なんだっけ？）、使い方と合わせて内容のわかる呼称を自分は使う。
-->

## 別解

[ユーザ解説 by AngrySadEight](https://atcoder.jp/contests/abc338/editorial/9186)は、思いがけない切り口からの解法だった。

橋$N$を落としたときの総行程は、上で言う順方向の距離の総和として計算できる。

その他の橋を落とすことを一般化して考える代わりに、橋$N$が落ちたまま、島の方を一つ手前にずらす。つまりそれぞれ1減らす、ただし$0$は$N$に戻す。
すると、1だった島が$N$になることにより、この島発着の行程が全て、その時点の順方向から逆方向に切り替えることになる。
より詳しく見ると、最初の番号で$X$と$Y$を結ぶ行程$(X < Y)$があったとして、ずらすことで$X$が1から$N$に変わるとき、この行程は初めて、逆方向に切り替えられる。
さらにずれて今度は$Y$が1から$N$に変わるとき、逆方向だった行程が順方向に戻される。
一回転させることで、全ての行程が2度切り替えを受ける。

元の島$X$が1から$N$に変わるときに起きる行程の変化量を調べておき、初期状態の順方向の総和を初期値として累積和をとると、それぞれのステップでの行程の距離が得られるので、その差以上値をとればよい。

```haskell
abc338d :: Int -> Int -> [Int] -> Int
abc338d n m xs = minimum $ scanl1 (+) $ elems diffs
  where
    diffs = accumArray (+) 0 (0,n)
      [ p
      | (x0, x1) <- zip xs (tail xs)     -- Xi, Xi+1 の間の行程
      , let d = abs $ x - y              -- 行程の長さ
      , let d1 = n - d - d               -- 1度めの切り替えでの増分
      , p <- [ (0, d)          -- 初期状態での総行程はdの総和
             , (min x y, d1)   -- 1度めの切り替え
             , (max x y, -d1)  -- 2度めの切り替えで元に戻る
             ]
      ]
```

ひとつめの解法とこの別解とで、根底の考え方は違うのに、結果として出てきたコードはどちらも累積和を用いた、似たような計算をするのは興味深い。

# E - Chords

[問題 ABC338E](https://atcoder.jp/contests/abc338/tasks/abc338_e)

シグネチャを決める。

```haskell
abc338e :: Int     -- N
        -> [[Int]] -- Ai, Bi
        -> Bool    -- 答え
```

[フレンズさんのtweet](https://twitter.com/kyopro_friends/status/1751240830646698040)の絵が判りやすい。どこで切っても同じで、開いて一本にしたときに線が重ならないとは、（全て異なる文字による）括弧の対応がとれていることと同じなので、スタックで判定できる。

このとき、切る位置はもちろん自然にNと1の間にすると、AとBの小さい方が先に出現し、大きい方が後に出現する位置だと判るので、先に出現する方が開き、後が閉じ括弧となり、「今K番の括弧は開き中かどうか」を、スタックの中を探したり、別に表を持ったりする必要すらない。

## 結果

```haskell
import Data.Array

abc338e :: Int -> [[Int]] -> Bool
abc338e n abs = loop [] $ elems circle
  where
    circle = array (1, n + n)
             [ p
             | (i, a:b:_) <- zip [1..] abs
             , p <- [ (min a b,  i)     -- 開き括弧
                    , (max a b, -i)]]   -- 閉じ括弧
    loop _ [] = False                                -- 最後まで交差はなかった
    loop    js  (i:is) | i > 0      = loop (i:js) is -- 開き括弧はpush
    loop (j:js) (i:is) | i + j == 0 = loop     js is -- スタックトップと一致する閉じ括弧はpop
                       | otherwise  = True           -- 違うなら、交差した。
```

公式解説のコードは、開きか閉じかを示す0/1と番号のタプルで真面目にやっていた。
符号を流用するこれの方がズボラだ…

# F - Negative Traveling Salesman

[問題 ABC338F](https://atcoder.jp/contests/abc338/tasks/abc338_f)

シグネチャを決める。$U_i,V_i,W_i$は手抜きする。

```haskell
abc338f :: Int       -- N
        -> Int       -- M
        -> [[Int]]   -- Ui, Vi, Wi
        -> Maybe Int -- 答え 経路がないとき Nothing
```

## 考える

さっぱりわからなかったので[アライさんのヒント](https://twitter.com/kyopro_friends/status/1751241385968374200)を見る。

> F問題は巡回セールスマンなのだ！　最初にワーシャルフロイドで全点間最短経路問題を求めておけばあとは普通にbitDPやるだけなのだ！

「普通に」でどうしていいかまだ判らなかったので公式解説を見た。

つまり、「意図的に目的地として設定して移動した先の頂点の集合だけを考える。次の目的地まで行く経路に、初めて通る頂点があるかもしれないが、それは無視してよい。
なぜなら、その頂点も意識して通った方が低コストなら、そのように選んだ順路もどこかで意図的に探索されるから。」

なるほど。最小コストをDPして、その添え字は次のようにする。

- 意図的に到達済みの頂点集合 $S$ 、$N \leq 20$なのでビット表現で扱う
- 訪問を終えて最後に至った頂点 $i$
（頂点が頂点集合に含まれないような状況については、コスト無限大とする）

すると、$cost[S][i]$は、

- $i \not\in S$ のときは $\infty$
- 到達済み頂点が1つ $|S| = 1$ のときは当然0
- 複数のときは、$S$の$i$意外に到達済みの全ての場合に対して、何らかの終点$j$から$i$に向かったときのコストの最小値 $\displaystyle \min_{j \in S, j \neq i} \left ( cost[S \setminus \\{i\\}][j] + dist[j][i] \right )$

とすることで集めるDPで計算できる。
bitDPでは、部分集合を表す整数はより小さな値になるので、添え字の小さい方から順に値を確定できるのが面白い。

ワーシャルフロイド法は骨の髄まで命令型配列なのでSTモナドで計算し、結果を`runSTArray`でimmutable配列として取り出し、Arrayを使った暗黙の集めるDPで書いてみた。
が、[どうあがいてもTLEする。](https://atcoder.jp/contests/abc338/submissions/50239466)

結局、ワーシャルフロイド法の結果をSTArrayのまま持ち、コストのDPもSTモナドで命令的に回してやったら[2616ms, 175MBでAC](https://atcoder.jp/contests/abc338/submissions/49790727)できた。
上のArray実装のときの集める関数 `costf` が原型を保って流用できてはいるが、本体の計算を関数型でできなかったのはくやしい。

# G - evall

[問題 ABC338G](https://atcoder.jp/contests/abc338/tasks/abc338_g)

シグネチャを決める。

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

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

皆目見当も付かない。

[すごいH~~な~~の人のtweet](https://twitter.com/tanakh/status/1751475654972104853) の「すごい綺麗」さを理解するためには何とかするしかない。
（といっても、公式解説のコード例もユーザ解説のコード例も、問題の難解さに見合わないコンパクトさで言葉が出てこない。

降参。