ABC278 A～F をHaskellで

# A - Shift

[問題 ABC278A](https://atcoder.jp/contests/abc278/tasks/abc278_a)

シグネチャを決める。$A_i$ は数である必要がない。

```haskell
abc278a :: Int       -- N
        -> Int       -- K
        -> [String]  -- Ai
        -> [String]  -- 答え
```

基本的に、$A_i$ の前から $K$ 要素を除き、後ろに $K$ 要素の `"0"` を追加すればよいが、
$N < K$ のときに（削除しすぎ、）追加しすぎる。

## 結果

```haskell
abc278a n k as = take n $ drop k as ++ repeat "0"
```

# B - Misjudge the Time

[問題 ABC278B](https://atcoder.jp/contests/abc278/tasks/abc278_b)

シグネチャを決める。

```haskell
abc278b :: Int        -- H
        -> Int        -- M
        -> (Int,Int)  -- 答え (時,分)
```

24時制で AB時CD分が、AC時BD分も時刻としてありうる数字の配置であるとは、

- BはAが0,1のとき全ての数字が現れる。Aが2のときは3以下の数字が現れうる。
- Cは常に5以下の数字である。

より、BとCが入れ替わっても時刻として違和感を起こさない条件は、

- Bが5以下である
- Cは、Aが2のとき3以下、Aが1以下のときは条件なし

の両方が満たされることである。
このような条件を満たす時刻を、1分ずつ進めながら見つける。

## 結果

```haskell
abc278b h m = until prop tick (h,m)

tick (23, 59) = (0, 0)
tick (h , 59) = (succ h, 0)
tick (h ,  m) = (h, succ m)

prop (h, m) = b <= 5 && (a /= 2 || c <= 3)
  where
    (a,b) = divMod h 10
    (c,d) = divMod m 10
```

質問に「0X時X0分のように、BとCが等しい場合も**見間違えやすい**に含むか？」とあった。そんなこと全く考えなかったが、確かに言われてみると、それは見間違えても時刻は変わらない。

# C - FF

[問題 ABC278C](https://atcoder.jp/contests/abc278/tasks/abc278_c)

シグネチャを決める。（本番での実装はクエリごとに計算する形にしたが、ここでは一括して計算する形にする。）

```haskell
abc278c :: Int      -- N
        -> Int      -- Q
        -> [[Int]]  -- Ti,Ai,Bi
        -> [Bool]   -- 答え
```

フォロー状況を、整数のペアの集合で表現する。
「ユーザーXがユーザーYをフォローしている」を要素 (X,Y) で持つ。

## 結果

```haskell
import qualified Data.Set as S
import Data.Maybe

abc278c :: Int -> Int -> [[Int]] -> [Bool]
abc278c n q tabs = catMaybes $ snd $ mapAccumL step S.empty tabs

step s [1,a,b] = (S.insert (a,b) s, Nothing)
step s [2,a,b] = (S.delete (a,b) s, Nothing)
step s [3,a,b] = (s, Just $ S.member (a,b) s && S.member (b,a) s)
```

# D - All Assign Point Add

[問題 ABC278D](https://atcoder.jp/contests/abc278/tasks/abc278_d)

シグネチャを決める。
続けてクエリ問題。

```haskell
abc278d :: Int      -- N
        -> [Int]    -- Ai
        -> Int      -- Q
        -> [[Int]]  -- query_q
        -> [Int]    -- 答え
```

$A$ の初期値が与えられているのに、1で行うことは「$A$ の全ての要素に $x_q$ を加える。」ではなくて「$A$ の全ての要素を $x_q$ にする。」である点がいつもと違う。

$N \leq 2 \times 10^5$ 要素の配列を $Q \leq 2 \times 10^5$ 回クエリ「$1 \\; x_q$」でリフレッシュさせられてはかなわないので、クエリ2で値を与えられた要素だけ `IntMap` で保持し、それ以外は直近のクエリ1で与えられたデフォルト値とする。

## 結果

```haskell
import qualified Data.IntMap as IM
import Data.Maybe

abc278d :: Int -> [Int] -> Int -> [[Int]] -> [Int]
abc278d n as q qs = catMaybes $ snd $ mapAccumL step (im0, 0) qs
  where
    im0 = IM.fromList $ zip [1..] as

step (im, def) query =
  case query of
    [1,x]   -> ((IM.empty , x  ), Nothing)
    [2,i,x] -> ((imadd i x, def), Nothing)
    [3,i]   -> ((im       , def), Just $ a i)
  where
    imadd i x = IM.insert i (a i + x) im
    a i = IM.findWithDefault def i im
```

`def`の初期値は`undefined`でも問題ないはず。

# E - Grid Filling

[問題 ABC278E](https://atcoder.jp/contests/abc278/tasks/abc278_e)

シグネチャを決める。

```haskell
abc278e :: Int      -- H
        -> Int      -- W
        -> Int      -- N
        -> Int      -- h
        -> Int      -- w
        -> [[Int]]  -- Aij
        -> [[Int]]  -- 答え
```

全ての塗りつぶしに対して定義通りに数えると $O(H^2W^2)$ で大変なので、計算量を節約したい。そこで塗りつぶしされていない部分に、どの数字が何回出現しているのかを、大きさ$N$の配列で数えて把握する。この配列の0でない要素の個数が、それぞれに対して問題が要求している数になる。

塗りつぶし範囲が(1,1)から(h,w)の場合については、素直に数える。
このカウント結果があるとき、塗りつぶし範囲を右または下に1マスずらした場合のカウント結果は、塗りつぶし範囲から復帰する部分のマスについてカウントを増やし、新たに塗りつぶされる部分のマスについてカウントを減らすだけで構築できる。

最初の塗りつぶしについて数えたものから、下に範囲をずらしたものを行数分だけ作る。
これらをスタート地点として、塗りつぶし範囲を右にずらしたものを列数分だけ作る。
という２次元の走査で全ての結果を効率的に得られる。

## 結果

```haskell
import Data.Array.Unboxed

abc278e :: Int -> Int -> Int -> Int -> Int -> [[Int]] -> [[Int]]
abc278e hh ww n h w ass = map countXYs $ zip [1..] countX1s
  where
    aa :: UArray (Int,Int) Int
    aa = listArray ((1,1),(hh,ww)) $ concat ass
-- 素直に数える
    count11 :: UArray Int Int
    count11 = accumArray (+) 0 (1,n)
      [(a, 1) | (i,as) <- zip [1..] ass, (j,a) <- zip [1..] as, h < i || w < j]
-- 下にずらしたカウント
    countX1s = scanl stepV count11 [1..hh-h]
    stepV cnt h0 = accum (+) cnt $
      [(aa ! (h0  , j),  1) | j <- [1..w]] ++
      [(aa ! (h0+h, j), -1) | j <- [1..w]]
-- 右にずらしたカウント
    countXYs (h0, countX1) = map countNZ $ scanl (stepH h0) countX1 [1..ww-w]
    stepH h0 cnt w0 = accum (+) cnt $
      [(aa ! (h0 + i, w0  ),  1) | i <- [0..pred h]] ++
      [(aa ! (h0 + i, w0+w), -1) | i <- [0..pred h]]
-- 0でない要素の個数を数える
    countNZ = length . filter (0 <) . elems
```

やることは判っているのだけど、配列をごちゃごちゃするのが面倒で飛ばしてしまった。
それでタイムアップするのだから情けない。

# F - Shiritori

[問題 ABC278F](https://atcoder.jp/contests/abc278/tasks/abc278_f)

シグネチャを決める。

```haskell
abc278f :: Int       -- N
        -> [String]  -- Si
        -> Bool      -- 答え True なら "First", False なら "Second"
```

ある語から開始して、行き詰まるまでしりとりを続ける様子は木構造をなす。
「ある語を読んだ」ことで「まだ読まれていない語の集合」と「次に読むべき語の先頭の文字」という状況が定まった状態をノードの識別子とする。
この状況から、次に遷移できるノード（読める語）が決定できる。

- 次に読める語がない状態なら相手は手詰まりなので勝ち。
- 次に読める語の状態に一つでも勝ち（これは相手が、という意味になる）なら、相手はそれを選択するはずなので負け。
- そうでないときとは、全ての相手の選択肢が全て相手の負け確定になっているので、勝ち。

$N \leq 16$ と大したことないので、「使用済みの語」をビット集合で表現し、「次の先頭の文字」に対して、読める語の番号とその末尾の文字の対を`Map`で持つことで、これを全探索する。
どこかの語から始めることで先攻が勝ちにできるなら "First" さもなくば "Second" が答えとなる。

## 結果

次の状態を読んだ結果を `rs` とすると、上の分析は以下の場合分けになる。

```haskell
  | null rs   = True
  | or rs     = False
  | otherwise = True
```
これは `= not $ or rs` と等しい。

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

abc278f :: Int -> [String] -> Bool
abc278f n ss = or [check (bit i) (last s) | (i, s) <- zip [0..] ss]
  where
    g = M.fromListWith (++) [(head s, [(i, last s)] | (i, s) <- zip [0..] ss]

    check bs c = not $ or
      [ check (setBit bs j) d
      | (j, d) <- M.findWithDefault [] c g
      , not $ testBit bs j]
```

わずか $N \leq 16$ にもかかわらずTLEする。
`check` 関数の呼び出しは重複するので、これをメモ化して計算量を抑える必要がある。

## メモ化

```haskell
import qualified Data.Map as M
import Data.Bits
import Data.Array

abc278f :: Int -> [String] -> Bool
abc278f n ss = or [checkA ! (bit i, last s) | (i, s) <- zip [0..] ss]
  where
    g = M.fromListWith (++) [(head s, [(i, last s)] | (i, s) <- zip [0..] ss]

    checkA = array ((1,'a'),(2^n-1,'z'))
      [((bs, c), checkF bs c) | bs <- [1..2^n-1], c <- ['a'..'z']]

    checkF bs c = not $ or
      [ checkA ! (setBit bs j, d)
      | (j, d) <- M.findWithDefault [] c g
      , not $ testBit bs j]
```

愚痴：メモ化が必要なのはTLEしてすぐ気づいたのだが、そこで混入したしょうもないバグに気づくのに20分もかかってしまった。

https://twitter.com/gotoki_no_joe/status/1593968161476718592

`Data.Array.array` は要素が足りていなくてもその場では文句を言わず、
定義が与えられなかった要素にアクセスがあったところで初めて

```
a.out: (Array.!): undefined array element
```

と実行時エラーを起こす。
よく見るとこれは添え字の範囲外へのアクセスをしたときのエラー

```
a.out: Error in array index
```

とは異なるので、エラーメッセージはちゃんと読みましょう。

または、`array` や `listArray` で配列要素を生成するときには、自分で添え字を生成せずに、　`Data.Ix.range` に任せると失敗がない。

```haskell
bounds = ((1,'a'),(2^n-1,'z'))
checkA = listArray bounds $ map checkF $ range bounds

checkF (bs, c) = ...
```

`checkF` 関数の引数を非カリー化して配列の添え字と合わせている。