ABC294 A～F をHaskellで

https://twitter.com/autotaker1984/status/1637451044048478208

https://qiita.com/autotaker1984/items/2929937cd1fea6137d1f

> ChatGPTを用いてAtCoder Beginners Contest 294に参加した
> A問題からE問題の５問を30分で解くことができた。

だそうで、急いでラッダイト運動に参加してこようと思います。

# A - Filter

[問題 ABC294A](https://atcoder.jp/contests/abc294/tasks/abc294_a)

数として `read` するまでもなく、末尾が `0,2,4,6,8` な語だけ取り出せばよい。

## 結果

```haskell
main = getLine >>
       getLine >>= putStrLn . unwords . filter abc294a . words

abc294a :: String -> Bool
abc294a s = elem (last s) "02468"
```

# B - ASCII Art

[問題 ABC294B](https://atcoder.jp/contests/abc294/tasks/abc294_b)

`ord` のような関数を持ち出すまでもなく、それぞれの数を対応する文字に置き換えられる。

## 結果

```haskell
main = getLine >>
       getContents >>= putStrLn . unlines . map abc294b . lines

abc294b :: String -> String
abc294b = map ((tbl !!) . read) . words

tbl = '.' : ['A'..'Z']
```

# C - Merge Sequences

[問題 ABC294C](https://atcoder.jp/contests/abc294/tasks/abc294_c)

シグネチャを決める。

```haskell
abc294c :: Int    -- N
        -> Int    -- M
        -> [Int]  -- Ai
        -> [Int]  -- Bi
        -> ([Int],[Int]) -- 答え
```

元々 $\\{ A_i \\}$ も $\\{ B_i \\}$ も昇順なので、まるごとソートする代わりに、「マージソート」のマージ操作をすれば整列される。
そのとき、マージ結果を求める代わりに、現在位置が何番目で、A側とB側のどちらの数を取ったかを記録すればいい。

## 結果

`merge`は、現在位置と $A_i, B_i$ の列をとり、$A_i$ を選んだら `Left 番号`, $B_i$ を選んだら `Right 番号` を結果のリストに置く。

```haskell
import Data.Either

abc294c :: Int -> Int -> [Int] -> [Int] -> ([Int],[Int])
abc294c n m as bs = partitionEithers $ merge 1 as bs
 
merge k (a:as) (b:bs)
  | a < b = Left  k : merge (succ k) as (b:bs)
  | True  = Right k : merge (succ k) (a:as) bs
merge k [] bs = [Right i | (i,_) <- zip [k..] bs]
merge k as [] = [Left  i | (i,_) <- zip [k..] as]
```

`Data.Either.partitionEithers` を使わなくても、A側の番号だけを返す定義にして、A側とB側を入れ替えて2度実行するというズボラなやり方をしてもいい。

```haskell
abc294c :: Int -> Int -> [Int] -> [Int] -> ([Int],[Int])
abc294c n m as bs = (merge 1 as bs, merge 1 bs as)
 
merge k (a:as) (b:bs)
  | a < b = k : merge (succ k) as (b:bs)
  | True  =     merge (succ k) (a:as) bs
merge k as _ = map fst $ zip [k..] as
```
`bs`が先に尽きたときは2つめの等式で`as`の残りに正しく番号が振られ、`bs`を残して`as`が先に尽きたときも2つめの等式で空リストが生成される。

あるいは、A側の結果から、出現しなかった数を取り出す計算で、B側を復元することもできるだろう。

# D - Bank

[問題 ABC294D](https://atcoder.jp/contests/abc294/tasks/abc294_d)

問題をよく読むと、「既に呼ばれている人は誰か」を気にする必要はないことがわかる。イベント2で、呼ばれていない人や、受付に行った人を呼ぶことはないことが保証されている。
つまり、イベント1は無視して、イベント2で終わった人だけチェックし、そうでない最小の番号の人がイベント3で呼ばれる。
MEXというやつだが、普通に`IntSet`を用いて解けばよいだろう。

## 結果

1からNをIntSetに入れておき、イベント2で呼ばれた人を消し、イベント3では残っている人の最小の番号を返す。

```haskell
import Control.Monad
import qualified Data.IntSet as IS

main = do
  [n,q] <- map read . words <$> getLine
  let is0 = IS.fromAscList [1..n]
  foldM_ (\is _ -> do
    ev <- map read . words <$> getLine
    case ev of
      [1]   -> return is                          -- （何もしない）
      [2,x] -> return $ IS.delete x is            -- xは立ち去る
      [3]   -> print (IS.findMin is) >> return is -- まだ居る最小の番号を出力
    ) is0 [1..q]
```

命令型の場合は、まだ居るかどうかの大きさNのフラグ配列を持ち、イベント3に対して、まだ居る最小の番号を、毎回先頭から検索していると大変なので、「前回のイベント3で調べた最終の番号から再開する」ロジックが必要になるのかな。

# E - 2xN Grid

[問題 ABC294E](https://atcoder.jp/contests/abc294/tasks/abc294_e)

シグネチャを決める。$v_\*, l_\*$ は横着する。

```haskell
abc294e :: Int      -- L
        -> Int      -- N1
        -> Int      -- N2
        -> [[Int]]  -- v1i, l1i
        -> [[Int]]  -- v2i, l2i
        -> Int      -- 答え
```

それぞれの行の内容がランレングス圧縮された形で与えられて、それを展開したときに、同じ位置に同じ文字がくる箇所を数えろ、と言っている。
$L \leq 10^{12}$ と膨大なので、本当に展開して数える訳にはいかない。

圧縮された状態のまま、同じ文字数ずつ消費して、それが同じ文字のランであれば結果にその長さを足しこむ、という方針で計算する。

## 結果

```haskell
abc294e :: Int -> Int -> Int -> [[Int]] -> [[Int]] -> Int
abc294e l n1 n2 vls1 vls2 = loop 0 vls1 vls2
 
loop acc ([v1,l1]:vls1) ([v2,l2]:vls2) =
  acc1 `seq`
  case compare l1 l2 of
    LT -> loop acc1 vls1 ([v2,l2-l1]:vls2)
    EQ -> loop acc1 vls1 vls2
    GT -> loop acc1 ([v1,l1-l2]:vls1) vls2
  where
    acc1 = if v1 == v2 then acc + min l1 l2 else acc
loop acc _ _ = acc
```

```acc1 `seq` ``` は無くても動くが、スペースリークが抑えられて少し速くなる。
この問題では「少し速くなる」程度だが、`foldl`をダッシュに置き換えたり、その中の関数を正格評価するように調整したりする必要にちょくちょく迫られるのは、

https://twitter.com/dico_leque/status/1632410340456812544
> A programming language is low level when its programs require attention to the irrelevant. 

「プログラミング言語は、そのプログラムが無関係なものに注意を払う必要がある場合、低レベルである。」(by [みんなの自動翻訳TexTra](https://mt-auto-minhon-mlt.ucri.jgn-x.jp/))
「この文の意味は、低水準言語では、本質的でない細かい動作まで記述しなければならないということです。」(BingAIによる補足説明）

に該当するのだろうか。（確かに、本来気にしなくてもいいはずの部分なのだけど。）

# F - Sugar Water 2

[問題 ABC294F](https://atcoder.jp/contests/abc294/tasks/abc294_f)

というか今回そもそも

https://twitter.com/terry_u16/status/1637449853373665280

が流れてくるまで、ABCがあったことも気づかなかった。

https://twitter.com/nagisa5101/status/1637461144431661056

今までの過去問でときどき遭遇していた濃度問題は全て敗退していたので、テリー氏に従ってググったところ、[ABC034D](https://atcoder.jp/contests/abc034/tasks/abc034_d)がやはりWA,TLEで終わっていたので、大人しく解説を読んだ。

目標とする濃度を設定した後、個々の液体に関して、溶質が絶対量でどれだけ過不足があるかを計算し、その合計が負なら足らなくて薄くなる、さもなくば足りている、と判断する。

液体が $W$[g]、濃度が$100P$[%]のとき、溶質は $WP$ [g] ある。
目標の濃度が$100Q$[%]のとき、$WP - WQ$ [g] の過不足がある。
$P$と$Q$だけを比較しても判断できず、$W$によってこの値は符号を含めて変わりうるのが、ややこしいポイント。

公式の解説スライドをさらに見ると、この種の問題を「平均の最大化問題」と呼ぶらしい。

## 結果

目標の濃度に対して、$C_j,D_j$ のそれぞれの過不足を求める。これを大きい順に番号を振ると、つまり、ある必要量以上に余剰のある溶液の個数が得られるので、これを持つ `Map` を作る。
$A_i,B_i$のそれぞれの過不足に対して、これを補填できる$C_j,D_j$の個数が上の`Map`を一度検索することで得られるので、その総数がK以上になるような濃度の下限を二分探索で探す。

命令型言語で、ソートした配列に対する二分探索した結果の添え字により、ある値以上の要素の個数を数える計算は、キー以上の値の個数を持つ `Map` への `lookupGE` と同等である。

```haskell
import qualified Data.Map as M
import Data.Maybe

abc294f :: Int -> Int -> Int -> [[Int]] -> [[Int]] -> Double
abc294f n m k abs cds = binsearch prop 0 100
  where
    pm q a b = fromIntegral (100 * a) - q * fromIntegral (a + b) -- 濃度qに対する過不足
    prop q = cnt >= k
      where
        cdm = M.fromDescList $                        -- Ci,Diの濃度qに対する過不足のMap
              flip zip [1..] $
              sortBy (flip compare) [pm q c d | c:d:_ <- cds]
        cnt = sum                        -- Ai,Biに対して濃度q以上にできるCj,Djの個数の和
          [ maybe 0 snd $ M.lookupGE x cdm
          | a:b:_ <- abs, let x = - pm q a b
          ]

binsearch f l h = loop l h
  where
    loop l h
      | term = l
      | f m  = loop m h
      | True = loop l m
      where
        m = (l + h) / 2
        term = h - l <= l * 1e-9 -- HとLの差がL*10^-9以下になったら止める
```

`binsearch`は[ABC292F](https://qiita.com/gotoki_no_joe/items/afe9848a41470b251559#f---regular-triangle-inside-a-rectangle)と同じものだが、[決め打ちで100回ループではTLEした](https://atcoder.jp/contests/abc294/submissions/39919316)ので、問題の要求する精度を満たしたところでループを終えるように変えている。
判定関数の中で`Data.Map`を生成するので割と重く、ループ回数を節約する必要があった。
結果は[3948ms](https://atcoder.jp/contests/abc294/submissions/39924195)とギリギリ。
<!--
`fromDistinctDescList`とウソを吐いたら[3808ms](https://atcoder.jp/contests/abc294/submissions/39924270)になったがこれはズル。
-->

# 感想

食塩水問題完全に理解した。
（しかし公式解説には[誤差のない値を得る方法 by MMNMM](https://atcoder.jp/contests/abc294/editorial/6017)というさらにブッとんだ話があって、とうてい理解が及ばない。今後の課題袋に入れておく。）

## AI

AIに話を戻して、画像の機械学習を妨害する加工のように、プログラミング演習問題の問題文にもそういう細工をすることになるのかしら。
その前に、プログラミングの授業がなくなってしまうのかしら。

東大京大をはじめとして、文系理系問わず、リテラシーレベルのデータサイエンス教育を目的としたPython入門講義が蔓延している現状だけど、ExcelにAIが載って、やりたいことを伝えたら勝手にやってくれるようになれば、その程度の授業は本当に不要になってしまう。

ドライワロス。

人知の及ばないような並列計算のアクロバティックなプログラムをAIが紡いで、そのコードの正しさをAI支援のcoq的なもので保証するとか、量子コンピュータのプログラムを作るとか、そういう方向に進んでいくなら夢があるけど。

## 計算機の能力

問題Eの $L \leq 10^{12}$ は、今のCPUの速度を考慮に入れて、naiveな解法を防ぐための設定になっている。シングルタスクなアルゴリズムを念頭に置いた場合、これはなかなか突破されそうにない。

一方、問題Fの $N,M \leq 5 \times 10^4$ は、最近のGPUだとCUDAコアが1万個とか載って、タワー型マシンにそれを4枚突っ込んだり、4Uラックマウントに8枚突っ込んだりできるみたいなので、全ての場合をエレファントに求めることも可能な時代になりつつある？