A - Full House
シグネチャを決める。
abc263a :: [Int] -- A,B,C,D,E
-> Bool -- フルハウスかどうか
Data.Listの関数を使うと楽に解ける。
groupを使うと同じものをひとまとめにできるが、連続している必要がある。
そのため groupする前にsortしておく。
まとめたリストの長さが2,3もしくは3,2になっていたらフルハウスである。
結果
import Data.List
abc263a xs =
case map length $ group $ sort xs of
[2,3] -> True
[3,2] -> True
_ -> False
B - Ancestor
シグネチャを決める。
abc263b :: Int -- N
-> [Int] -- Pi
-> Int -- 答え
人 $N$ から始めて、人1に至るまで、親を辿った回数を数える。
リストの (!!) は0始まりなこと、線形探索なことから、$P_i$ は配列に移して使うと行儀がよいのでそうするが、$N \leq 50$ と大した規模ではないので大袈裟だったかもしれない。
結果
import Data.Array
abc263b n ps = loop n
where
pa = listArray (1,n) ps
loop 1 = 0
loop k = succ $ loop (pa ! k)
追記
(2022-8-19)
より（無駄に）Haskellらしい解き方として、遅延評価な配列を使ったDPでも解ける。
import Data.Array
abc263b n ps = pa ! n
where
pa = listArray (1,n) $ 0 : [succ $ pa ! p | p <- ps]
C - Monotonically Increasing
シグネチャを決める。
abc263c :: Int -> Int -- N, M
-> [ [Int] ] -- 答え
これから生成する数列の長さと、先頭要素の最小値のふたつを引数にとり、これを満たす狭義単調増加列のリストを作る補助関数を考える。
長さ0なものは空リストである。
長さ $\ell$ なものは、先頭要素 $b$ を指定値から $M$ まで振って、$b+1$ を次の先頭要素の最小値として再帰的に作った数列の前に繋げば作れる。
ただ、$\ell > 1$のときに $b$ を $M$ まで振ってしまうと、後続のリストが作れなくなるので、振る上限は $M - \ell + 1$ までで充分である。
結果
abc263c n m = loop n 1
where
loop 0 _ = [ [] ]
loop l a = [ b : bs | b <- [a .. m - l + 1], bs <- loop (pred l) (succ b)]
D - Left Right Operation
シグネチャを決める。
abc263d :: Int -> Int -> Int -- N, L, R
-> [Int] -- Ai
-> Int -- 答え
$y$ をある値に固定する。すると後ろ $y$ 項の和は $yR$ である。
このとき前 $N - y$ 項について、$x$ を変化させたときの和の最小値を求められれば、これに $yR$ を足した値がそのときの数列の総和である。
$0 \leq y \leq N$ についてその最小値が求める値である。
さて、例えば$N-y=3$とすると、このとき $x$ を0から3まで変えた数列の和は順に以下のとおりである。
$\begin{array}{ccccc}
A_1 & + & A_2 & + & A_3 \\
L & + & A_2 & + & A_3 \\
L & + & L & + & A_3 \\
L & + & L & + & L
\end{array}$
これら4行の最小値を$m_3$とおく。
$N-y=4$ のときのも同様に考えることができる。
$\begin{array}{ccccccc}
A_1 & + & A_2 & + & A_3 & + & A_4 \\
L & + & A_2 & + & A_3 & + & A_4 \\
L & + & L & + & A_3 & + & A_4 \\
L & + & L & + & L & + & A_4 \\
L & + & L & + & L & + & L
\end{array}$
上4行のうちの最小値は$m_3+A_4$、5行めの値は$4L$なので、これら5行の最小値は$m_4 = \min(m_3+A_4,4L)$で求められる。
一般化して、前 $i$ 項の和の最小値は $m_i = \min(m_{i-1} + A_i, iL)$ という漸化式で前から
順に求められる。このとき数列全体の和は $m_i + R(N-i)$ である。
実装にはmapAccumLを用いると、前からリストの要素を使いつつ、状態を持ちまわせるので書きやすい。ただmapAccumLはscanlと異なり、リストをひとつも消費しない状態の出力を持たないので、そこだけ工夫が必要である。
結果
abc263d n l r as = minimum (mN:ms)
where
((_, mN), ms) = mapAccumL step (0, 0) as
step (i, m) ai = ((i1, m1), m + r * (n - i))
where
i1 = succ i
m1 = min (m + ai) (l * i1)
E - Sugoroku 3
（解説を見ないとわからなかった。FF256grhy氏の解説を参考にしている。）
$ex[1 \leq i \leq N]$ ：マス $i$ からマス $N$ まで至るまでにサイコロを振る回数の期待値、を考える。
$ex[N] = 0$である。
マス $i$ について考えると、ここからはマス $i + 1$ から $i + A_i$ のどれかに進む。マス $i + j \; (1 \leq j \leq A_i)$ に進んだと仮定する。
$i+j$ へ進むためにサイコロを振る回数の期待値 $X$ は、$x$ 回連続で $0$ を出して次に $j$ を出したとき $x+1$ 回になるので、$X = \frac{1}{A_i+1} + \frac{2}{(A_i+1)^2} + \frac{3}{(A_i+1)^3} + \dots = \frac{A_i+1}{(A_i)^2}$ となる。
またマス $i+j$ から $ex[i+j]$ 回の期待値で $N$ に至る。
$j=1$ から $j = A_i$ は均等に等確率 $\frac{1}{A_i}$ で発生する。
なので、それぞれの $j$ の場合の期待値に確率を掛けて足し合わせて、マス $i$ の期待値が定まる。
$\displaystyle ex[i] = \sum_{j=1}^{A_i} \left (X + \frac{ex[i+j]}{A_i} \right ) = \frac{1}{A_i} \left ( A_i+1 + \sum_{j=1}^{A_i} ex[i+j] \right )$
（ここで $X$ は $A_i$ で割らなくてよい理由が説明できない。確率難しい。）
$\sum$ をそのままループで実装せず、累積和でやるように気をつけて、配列による〈集めるDP〉で実現すると以下のようになる。
分数は Data.Ratio の Ratio Int で扱うことにする。
import Data.Array
import Data.Ratio
-- loop
abc263e n as = ans
where
zero = 0 % 1
-- exAの累積和
exSA = listArray (0,n) $ scanl (+) zero $ elems exA
-- exのDP配列
exA = listArray (1,n) $ zipWith exF as [1..] ++ [zero]
-- exのDP関数
exF ai i = (succ ai % 1 + exSA ! (i + ai) - exSA ! i) * (1 % ai)
-- 答え
ans = exA ! 1
問題点がふたつある。まず、これでは最終結果が整数でなく Ratio Int で返されてしまう。問題文が要求している整数 $R$ とは、$P/Q$ の $Q$ のモジュラ逆数 $Q^{-1}$ を求めて $P$ に掛けた $P Q^{-1}$ のことなので、そのように作る。
abc263e n as = r ((r $ numerator ans) * modRecip (r $ denominator ans))
where
...
modBase = 998244353
r x = mod x modBase
-- 拡張ユークリッドの互除法によるモジュラ逆数
-- @gotoki_no_joe
modRecip a = u
where
(_,_,u,_) = until stop step (a, modBase, 1, 0)
step (a,b,u,v) = let t = div a b in (b, a - t * b, v, u - t * v)
stop (_,b,_,_) = b == 0
もう一つの問題として、exA 配列は添え字の大きな方から小さな方に値が確定していくのに対して、その計算の過程で利用する累積和 exSA が添え字の小さい方から足し合わせているため、データの依存関係がループしてしまう。
これは、累積和も添え字の大きな方から足し合わせることで解決できる。
exSA = listArray (1,succ n) $ scanr (+) zero $ elems exA
exF ai i = (succ ai % 1 + exSA ! (i + 1) - exSA ! (succ i + ai)) * (1 % ai)
しかしまだWAになる。
おそらく計算途中で Ratio Int がオーバーフローを起こしている。正確さのために Rational = Ratio Integer を使うには、ai を Integer にするなどの型変換が多く入りすぎてつらいし、今度は Integer の演算で TLE しそうな気もする。
ここで、計算過程でも Ratio ではなく、モジュラ逆数を用いた分数表現を使うことを考える。そんなことして大丈夫かとも思うが、ACしたので大丈夫のようだ。（いい加減）
結果
import Data.Array
abc263e :: Int -> [Int] -> Int
abc263e n as = exA ! 1
where
exSA = listArray (1,succ n) $ scanr add 0 $ elems exA
exA = listArray (1,n) $ zipWith exF as [1..] ++ [0]
exF ai i = r $ (succ ai + exSA ! (i + 1) - exSA ! (succ i + ai)) * modRecip ai
modBase = 998244353
r x = mod x modBase
add x y = r $ x + y
-- @gotoki_no_joe
modRecip a = u
where
(_,_,u,_) = until stop step (a, modBase, 1, 0)
step (a,b,u,v) = let t = div a b in (b, a - t * b, v, u - t * v)
stop (_,b,_,_) = b == 0