ABC266 A～E をHaskellで

A - Middle Letter

問題 ABC266A

シグネチャを決める。

abc266a :: String -> String

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

結果

main = getLine >>= putStrLn . abc266a

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

B - Modulo Number

問題 ABC266B

シグネチャを決める。

abc266b :: Int  -- N
        -> Int  -- 答え x

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

結果

abc266b n = mod n 998244353

C - Convex Quadrilateral

問題 ABC266C

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

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軸が正なら左周り、負なら右回りと判別できる。

結果

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

シグネチャを決める。

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である。

結果

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

シグネチャを決める。

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 を使ってみる。

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