ABC266 A～E をHaskellで

# A - Middle Letter

[問題 ABC266A](https://atcoder.jp/contests/abc266/tasks/abc266_a)

シグネチャを決める。

```haskell
abc266a :: String -> String
```

文字数が必ず奇数なので、中央の文字は必ずあり、長さ/2だけdropすれば先頭がそれ。
リスト処理の練習問題。
`(!!)`で文字を取り出してしまうと、`putStrLn` が使えなくて余計に面倒になるのがHaskellの罠か。

## 結果

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

abc266a s = take 1 $ drop (div (length s) 2) s
```

# B - Modulo Number

[問題 ABC266B](https://atcoder.jp/contests/abc266/tasks/abc266_b)

シグネチャを決める。

```haskell
abc266b :: Int  -- N
        -> Int  -- 答え x
```
$P = 998244353$ として、「$N - x$ は $P$ の倍数」を言い直すと
$N - x = kP$　（$k$ は何らかの整数）
$N - x = 0 \bmod P$
$N = x \bmod P$
なので `mod` をとるだけ。

## 結果

```haskell
abc266b n = mod n 998244353
```

# C - Convex Quadrilateral

[問題 ABC266C](https://atcoder.jp/contests/abc266/tasks/abc266_c)

シグネチャを決める。手抜きする。

```haskell
abc266c :: [(Int,Int)]   -- A,B,C,Dの X,Y
        -> Bool          -- 答え
```

「ベクトルのなす角」で検索すると、$\cos^{-1}$ を用いて $0 \leq \theta \leq 180^\circ$ の範囲で求める、という話が見つかるばかりで役に立たない。
問題設定で、点が反時計回りの順だと保証されているので、$\vec{AB}, \vec{BC}, \vec{CD}, \vec{DA}$ が、順に左に曲がっている向きなら凸で、右に曲がっているなら凸でない。
2次元ベクトルの回っている向きは、外積を求めてZ軸が正なら左周り、負なら右回りと判別できる。

## 結果

```haskell
abc266c abcd = all (0 <) cp3s
  where
    ds = zipWith sub (tail $ cycle abcd) abcd
    cp3s = zipWith cp3 ds (tail $ cycle ds)

sub (x1,y1) (x2,y2) = (x1 - x2, y1 - y2)
cp3 (x1,y1) (x2,y2) = x1 * y2 - y1 * x2
```

# D - Snuke Panic (1D)

[問題 ABC266D](https://atcoder.jp/contests/abc266/tasks/abc266_d)

シグネチャを決める。

```haskell
abc266d :: Int              -- N
        -> [(Int,Int,Int)]  -- Ti,Xi,Ai
        -> Int              -- 答え
```

各時刻に位置 $0 \sim 4$ に位置できる高橋君の、最も高いスコアを長さ 5 のリストで時刻ごとに構築する。ただし、時刻1での位置4など、到達できない場合に対応するため、`Maybe` で包む。
時刻0の初期状態は `[Just 0, Nothing, Nothing, Nothing, Nothing]` となる。
時計の針が進むとき、まず、前後1から移動してこれるので、それらの最大値をとる。次いで、その時刻にすぬけ君が出現するなら、その位置のスコアに大きさを追加する。

全てのすぬけ君が出終わった段階でのスコアの最大値が答えである。
自然なシミュレーションに見えるが、立派なDPである。

## 結果

```haskell
import Data.Maybe

abc266d :: Int -> [(Int,Int,Int)] -> Int
abc266d n txas = maximum $ catMaybes las
  where
    ini = [Just 0, Nothing, Nothing, Nothing, Nothing]  -- 初期状態
    las = loop 0 ini txas                               -- 最終状態

loop _ state [] = state
loop now state txatxas@((t,x,a):txas)
  | now1 == t = loop now1 state2    txas
  | otherwise = loop now1 state1 txatxas
  where
    now1 = succ now
-- 左からくる、動かない、右からくる、のスコアの最大値をそれぞれとる
    state1 = zipWith3 getmax (Nothing : state) state (tail state ++ [Nothing])
-- すぬけ君が出現するとき、その位置のスコアにAiを足す
    state2 = take x state1 ++ fmap (a +) (state1 !! x) : drop (succ x) state1

getmax a b c =
  case catMaybes [a,b,c] of
    [] -> Nothing
    vs -> Just $ maximum vs
```

# E - Throwing the Die

[問題 ABC266E](https://atcoder.jp/contests/abc266/tasks/abc266_e)

シグネチャを決める。

```haskell
abc266e :: Int -> Double
```

- $0$ 投の期待値は $0$ である。
- $N$ 投の期待値が $P_N$ のとき、$N+1$ 投の期待値は、まず1回投げて、$D$ が出たとすると
  - $D \geq P_N$ なら、今回で終了するべき。そうしたとき得られる得点は $D$
  - そうでないなら、続投するべき。そうしたとき得られる得点の期待値は $P_N$
- で、それぞれの場合の得点を合計して6で割ればそれが $P_{N+1}$ である

## 結果

$N \leq 100$ なので、正確に計算してもなんとかなりそうなので `Data.Ratio` を使ってみる。

```haskell
import Data.Ratio

abc266e :: Int -> Double
abc266e n = fromRational $ iterate step 0 !! n

step p = sixth * sum [max p i | i <- onetosix]

onetosix = [i % 1 | i <- [1..6]]
sixth = 1 % 6
```