ABC254 A～E をHaskellで

# A - Last Two Digits

[問題 ABC254A](https://atcoder.jp/contests/abc254/tasks/abc254_a)

シグネチャを決めるまでもない。必ず3桁な入力を整数として解釈したら負けである。

## 結果

```haskell
main = getLine >>= putStrLn . tail
```

# B - Practical Computing

[問題 ABC254B](https://atcoder.jp/contests/abc254/tasks/abc254_b)

シグネチャを決める。

```haskell
abc254b :: Int -> [[Int]]
```

これはパスカルの三角形、または二項係数そのものであるが、たかだか $N \leq 30$ なので問題文どおりに生成する。

## 結果

```haskell
abc254b n = take n ncrs

ncrs = [1] : map step ncrs

step ncr = zipWith (+) (0 : ncr) (ncr ++ [0])
```

# C - K Swap

[問題 ABC254C](https://atcoder.jp/contests/abc254/tasks/abc254_c)

シグネチャを決める。

```haskell
abc254c :: Int  -> Int   -- N, K
        -> [Int]         -- ai
        -> Bool          -- 結果
```

添え字を0始まりにして考える。
どのように操作を行っても、数列の $i$ 番目の要素は、$K$ 間隔の位置である $i + nK$ 番目（$n$ は負を含む任意の整数）にしか来ることができない。
つまり、$A$ を $K$ 間隔で取り出した多重集合 $A_j = \\{ a_{nK+j} \\;|\\; n = 0,1\dots \\} \\; (0 \leq j < K)$ と、$A$ を整列した列 $S = (s_1, s_2, \dots, s_N)$ を $K$ 間隔で取り出した多重集合 $S_j = \\{ s_{nK+j} \\;|\\; n = 0,1,\dots \\} \\; (0 \leq j < K)$ が、$A_j = S_j \\; (0 \leq j < K)$ である必要がある。

## 結果

```haskell
import Data.List
import Data.Function

abc254c :: Int -> Int -> [Int] -> Bool
abc254c n k as = and $ zipWith ((==) `on` sort) ds es
  where
    f = transpose . chop k
    ds = f        as
    es = f $ sort as

chop :: Int -> [a] -> [[a]]
chop n = unfoldr step
  where
    step [] = Nothing
    step xs = Just $ splitAt n xs
```
`chop` は `Data.List.Split` の関数であるが、`import` すると怒られた。

# D - Together Square

[問題 ABC254D](https://atcoder.jp/contests/abc254/tasks/abc254_d)

シグネチャを決める。

```haskell
abc254d :: Int -> Int
```

公式解説、ユーザ解説が非常に豊富にあるのでそちらも参照して。

素数を $[P_i]$ とする。数を素因数分解して考える。
任意の整数 $t = \prod P_i^{T_i}$ に対して、$t^2 = \prod P_i^{2 T_i}$ である。すなわち、平方数はべき乗の数がすべて偶数である。
この事実をもとに考えると、$a = \prod P_i^{A_i}$ と掛け合わせたら平方数になるような数 $b = \prod P_i^{B_i}$ は、$a \times b = \prod P_i^{A_i + B_i}$ について、$A_i + B_i$ が全て偶数である必要がある。つまり、$A_i$ と $B_i$ の偶奇が全て同じとなるような $b$ の個数だけ、$a$ と掛け合わせたら平方数となる数がある。

よって、べき乗の数の偶奇パターン全て $[偶,偶,\dots] \sim [奇,奇,\dots]$ について、$1 \leq i \leq N$ にそのような数がいくつあるかを数えられれば、その個数の二乗の和が答えである。

偶奇パターンを網羅しようとすると、$N$ 以下の最大の素数が $P_c$ であるときパターンは長さ $c$ になる。$2 \times 10^5$ 以下の素数は17984個もあるので、長さ17984の `[Bool]` で表すか、ビット列に落とし込んでも $0 \sim 2^{17984}-1$ の整数でこれを表現するには `Int` では収まらない。（なお、[力づくで `Integer` で表して `Map` で数えて AC することもできる。](https://atcoder.jp/contests/abc254/submissions/34122850)）

しかしよく考えると、$P_{17983} \cdot P_{17984} > 2 \times 10^5$ のように、全てのビット列が現れるわけではないので、べき乗の数が奇数な素数だけの積で代表させることができる。つまり $t = \prod P_i^{T_i}$ であるとき、$N(t) = \prod P_i^{T_i \bmod 2}$ とする。これは $t \geq N(t)$ なので `Int` で扱える。

素因数分解は作り置きのスニペットを使う。

## 結果

```haskell
import Data.Array.Unboxed
import Data.List

abc254d :: Int -> Int
abc254d n = sum . map (^ 2) . elems arr
  where
    arr :: UArray Int Int
    arr = accumArray (+) (1,n) [(norm i, 1) | i <- [1 .. n]]

norm :: Int -> Int -- 関数 N
norm = product . map head . filter (odd . length) . group . primeFactors

-- @gotoki_no_joe
primeFactors :: Int -> [Int]
primeFactors n = loop n pprimes
  where
    pprimes = 2 : 3 : [y | x <- [5,11..], y <- [x, x + 2]]  -- pseudo primes
    loop n pps@(p:ps)
      | n == 1    = []
      | n < p * p = [n]
      | r == 0    = p : loop q pps
      | otherwise = loop n ps
      where
        (q,r) = divMod n p
```

## 続き

[ひとつめの公式解説](https://atcoder.jp/contests/abc254/editorial/4065)で言っている $\frac{i}{f(i)}$ は上の $N(\cdot)$ と同じものである。
$f(i)$ を高速に求めるために、候補となる $i$ 以下の平方数の降順のリストを素早く取り出せる `sqm :: IntMap [Int]` を作った。

```haskell
import qualified Data.IntMap as IM
import Data.List
import Data.Maybe
import Data.Array.Unboxed

abc254d :: Int -> Int
abc254d n = sum $ map (^2) $ elems arr
  where
    arr :: UArray Int Int
    arr = accumArray (+) 0 (1,n) [(idivfi i, 1) | i <- [1..n]]

    sqs = reverse $ takeWhile (n >=) $ map (^ 2) [1 ..]
    sqm = IM.fromAscList $ reverse [(head sq, sq) | sq <- init $ tails sqs]
    idivfi i = head
      [ q
      | sq <- snd $ fromJust $ IM.lookupLE i sqm
      , let (q,r) = divMod i sq
      , r == 0]
```

[結果、](https://atcoder.jp/contests/abc254/submissions/34124565)素因数分解した方が速かった。

# E - Small d and k

[問題 ABC254E](https://atcoder.jp/contests/abc254/tasks/abc254_e)

シグネチャを決める。

```haskell
abc254e :: Int -> Int   -- N,M
        -> [(Int,Int)]  -- (ai,bi)
        -> Int          -- Q
        -> [(Int,Int)]  -- (xi,ki)
        -> [Int]        -- 答え
```

グラフの問題と聞いて身構えてしまうが、問題文に太字で「各頂点の次数は3以下」とヒントが書いてある。また、毎回のクエリで聞かれる距離も $0 \leq k_i \leq 3$ と小さい。
出発点 $x_i$ から距離1の頂点は、次数が3として3個、そこから距離1の頂点は次数3のうち $x_i$ でないものはもう2個、さらに距離1の頂点はもう2個で、$1 + 3 + 3 \times 2 + 3 \times 2 \times 2 = 22$ 頂点しかない。親を除くのをさぼっても $1 + 3 + 3 \times 3 + 3 \times 3 \times 3 = 40$ しかないので、力づくで挙げてしまえば済む。

## 結果

```haskell
import Data.Array
import Data.List

abc254e :: Int -> Int -> [(Int,Int)] -> Int -> [(Int,Int)] -> [Int]
abc254e n m abs q xks = map (query g) xks
  where
    g = accumArray (flip (:)) [] (1,n) [p | (a,b) <- abs, p <- [(a,b),(b,a)]]

query g (x,k) = sum $ nub $ concat $ take (succ k) $ iterate (concatMap (g !)) [x]
```