ABC269 A～E をHaskellで

# A - Anyway Takahashi

[問題 ABC269A](https://atcoder.jp/contests/abc269/tasks/abc269_a)

計算する内容は $(a+b)\times(c-d)$だと問題文に明記されているので、これ以上説明することはない。

## 結果

せっかくなので `main` から書いてみる。
`read`の型が明示されていないが、defaultingで`Integer`になっていると思われる。

```haskell
main = do
  li <- getLine
  let [a,b,c,d] = map read $ words li
  print $ (a + b) * (c - d)
  putStrLn "Takahashi"
```

# B - Rectangle Detection

[問題 ABC269B](https://atcoder.jp/contests/abc269/tasks/abc269_b)

シグネチャを決める。横着する。

```haskell
abc269b :: [String]  -- Si
        -> [Int]     -- 答え A,B,C,D
```

行について、「`#` が現れる」ような行が $A$ 行めから $B$ 行めであることを知りたい。
そのような $A$ 行めの文字列について、「`#` である」ような文字が $C$ 文字めから $D$ 文字めであることを知りたい。
Haskellの文字列は文字のリストなので、この二つの段階は共通化できる。
それぞれ性質 `elem '#'`, `('#' ==)` を満たす先頭の要素と末尾の要素の番号を知りたい、ということになる。

## 結果

```haskell
abc269b ss = [a,b,c,d]
  where
    (a,b) = sub (elem '#') ss
    (c,d) = sub ('#' ==) $ ss !! pred a

sub p xs = (head is, last is)
  where
    is = map fst $ filter (p . snd) $ zip [1..] xs
```

# C - Submask

[問題 ABC269C](https://atcoder.jp/contests/abc269/tasks/abc269_c)

シグネチャを決める。

```haskell
abc269c :: Int    -- N
        -> [Int]  -- 答え
```

数 $N$ の2進表記に対して、1である各桁について、それを1のままにした数と、0にした数の両方が出力に含まれる。そして後者は前者より小さい。
最上位桁から調べて、ビットが1であるとき、そのビットを0にした数から（再帰的に）作られる数のリストに、1のままにした数から（再帰的に）作られる数のリストを連結すればよい。

```haskell
import Data.Bits

abc269c :: Int -> [Int]
abc269c n = recur n (bit 59)

recur x 0 = [x]
recur x b
  | x .&. b == 0 = recur x (shiftR b 1)
  | otherwise    = recur (xor x b) (shiftR b 1) ++ recur x (shiftR b 1)
```

`(++)` はダサいので、「この関数の結果に続けるリスト」を追加の引数にする Haskell の定番の高速化を追加する。

## 結果

```haskell
import Data.Bits

abc269c :: Int -> [Int]
abc269c n = recur n (bit 59) []

recur x 0 rest = x : rest
recur x b rest
  | x .&. b == 0 = recur x b1
  | otherwise    = recur (xor x b) b1 $ recur x b1 rest
  where
    b1 = shiftR b 1
```

# D - Do use hexagon grid

[問題 ABC269D](https://atcoder.jp/contests/abc269/tasks/abc269_d)

シグネチャを決める。

```haskell
abc269d :: Int          -- N
        -> [(Int,Int)]  -- Xi,Yi
        -> Int          -- 答え
```

「連結成分」と言われたらUnionFind。
通常の碁盤の目状の画像について連結成分を考えるときは全ての画素をUnionFindの要素にするが、この問題設定では無駄が多そうなので、入力に現れる座標のマスのみを要素とする。

それぞれのマスについて、6近傍のマスで入力に現れているものと Union を行う。
最終的な UnionFind で連結成分の個数を数えれば答えが得られる。

## 結果

自作のUnionFindは要素が整数なので、$(X_i,Y_i)$ に $i$ を対応させる `Map` を併用し、近傍が現れているかの判断もこれを利用して行う。ついでにその近傍のマスの番号も取得できる。

`Data.Maybe.maybe b f ma` は、`ma` が成功して `Just a` ならさらに続きの処理をした `f a` を返すが、`ma` が失敗して `Nothing` ならデフォルト値 `b` を返す。
`step2`で、近傍 `zw` の番号 `j` と `xy` の番号 `i` を `uniteUF` するが、`zw` が入力にない場合は元のままの `uf` を返すのに使っている。

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

abc269d n xys = length $ allDivisions $ foldl' step1 (newUF n) xyis
  where
    xyis = zip xys [0..]
    m = M.fromList xyis
    step1 uf (xy, i) = foldl' (step2 i) uf $ neighbors xy -- xyと周囲のマスをunionする
    step2 i uf zw = maybe uf (uniteUF uf i) $ M.lookup zw m -- 周囲で入力に現れるマスのみ

neighbors (x,y) =
  [ (z,w)
  | z <- [pred x, x, succ x]
  , w <- [pred y, y, succ y]
  , z + w /= x + y    -- 8近傍のうち(x+1,y-1),(x-1,y+1),そして (x,y) は含まない
  ]

-- UnionFind APIのみで実装は略

-- 0からN-1を要素とするUnionFindを作る
newUF :: Int -> UnionFind

-- iとjを統合する
uniteUF :: UnionFind -> Int -> Int -> UnionFind

-- 全ての分割を得る
allDivisions :: UnionFind -> [[Int]]
```

完全版は[こちら。](https://atcoder.jp/contests/abc269/submissions/34956638)

# E - Last Rook

[問題 ABC269E](https://atcoder.jp/contests/abc269/tasks/abc269_e)

シグネチャを決め…られない。
- 答えがわかったら "! X Y" の形式で出力して停止、
- まだわからないなら "? A B C D" の形式で問い合わせ、返答Tが
  - -1 なら、何かやらかしたので非常停止
  - 0以上の数なら、それを手がかりにして推測を続行するために再帰
という形の再帰的計算になると予想が立つ。

> 答えが複数ある場合、どれを出力しても正解とみなされます。

などと目くらましが書いてあるが、結局、それぞれの行に必ず1つルークがある、それぞれの列に必ず1つルークがある、という最終状態からどれか一つのルークを隠した場面なので、その「ルークのない行」と「ルークのない列」は唯一に定まる。

行と列で条件が変わらないので、別々に二分探索する。絞り込めていない $2M$ 行の前半分について問い合わせた結果が $M$ なら全ての行にルークがいるので空行は反対側に、1少なければ今調べた範囲に空行がある。
$N \leq 10^3 = 1000 < 1024 = 2^{10}$ なので、10回あれば行は特定でき、列についても同様で、20回あれば間に合う。

## 結果

行と列の二分探索は共通化する。
範囲は下開区間で扱っている。
$-1$を返された場合の異常系は省略している。プログラムは正しい。

```haskell
import System.IO

main = do
  n <- readLn
  i <- loop True n 0 n
  j <- loop False n 0 n
  putStrLn $ unwords ["!", show i, show j]

loop :: Bool -> Int -> Int -> Int -> IO Int
loop _    _ lb ub | succ lb == ub = return ub
loop vert n lb ub =
  do
    putStrLn $ unwords $ "?" : map show abcd1
    hFlush stdout                 -- これを入れないと TLE してしまう
    t <- readLn
--  if t == -1 then error "something wrong" else
    if t == d2 then loop vert n mid ub
    else            loop vert n lb mid
  where
    d2 = div (ub - lb) 2
    mid = lb + d2
    abcd1 = if vert then [succ lb, mid, 1, n] else [1, n, succ lb, mid]
```

`vert`引数の意味を取り違え、"! Y X" を出力して `WA` になりしばらく悩んだ。
サンプルを含めて対角線上に答えがあるテストケースに関してちらほら `AC` してしまうため、逆に何がおかしいのかしばらくわからなかった。