https://torus711.hatenablog.com/entry/2026/02/01/185359

はじめに

　実装メイン．テンプレは別記事．

A

　問題文 : https://atcoder.jp/contests/abc443/tasks/abc443_a
　言われた通りに実装するします．入力に ( ++ "s" ) してから出力します．

main = getLine >>= putStrLn . ( ++ "s" )

　ちょっと盲点でしたが，入出力とデータの加工が混ざることを許容するなら，入力をそのまま putStr で改行無しで出力してから putStrLn "s" する方法もあります．

main = getLine >>= putStr >> putStrLn "s"

B

　問題文 : https://atcoder.jp/contests/abc443/tasks/abc443_b
　$1$ 以上 $x$ 以下の整数の和は $\sum_{ k = 1 }^x k = \frac{ x ( x + 1 ) }{ 2 }$ であるので，食べた豆の累計個数は日数に対して $2$ 乗オーダで増えます．$k$ を起点に考えると $O( \sqrt k )$ 日で達成できることになります．よって，$\langle n, n + 1, n + 2, \ldots \rangle$ という無限列の累積和を考えて，初めて $k$ 以上となる要素の添字を求めればそれが答えです．
　累積和の計算は scanl1 (+) でできて，条件を満たす要素が最初に出現する要素の添字は findIndex で求めることができます．

main = do
	[ n, k ] <- readInts
	print $ fromJust $ findIndex ( k <= ) $ scanl1 (+) [ n .. ]

C

　問題文 : https://atcoder.jp/contests/abc443/tasks/abc443_c
　次に SNS を開く時刻を $t'$ とし，次に青木くんが通りかかる時刻を $a$ とします．このときに起こることは $t'$ と $a$ の大小関係によって場合分けできて，

$a \leq t'$ のとき → 何も起こらない．$a$ を破棄して次の青木くんタイムへ．
$t' < a$ のとき → 時刻 $t'$ から $a$ までの $a - t'$ 単位時間 SNS を見る．その次に SNS を開くのは時刻 $a + 100$ で，次の青木くんタイムへ．

となります．この計算は $t'$ を状態として畳み込むことができて，mapAccumL で畳み込めば答えへの寄与をリストに書き出すことができます．また，終業時刻に起きることは，時刻 $t$ を青木くんの通過と見做して上記の条件分岐をすることと同じなので，$A$ の末尾に $t$ をくっつけてから畳み込めば問題を解けます．

main = do
	[ n, t ] <- readInts
	as <- readInts
	print $ sum $ snd $ mapAccumL solve 0 ( as ++ [t] )

solve t a
	| a <= t = ( t, 0 )
	| otherwise = ( a + 100, a - t )

D

　問題文 : https://atcoder.jp/contests/abc443/tasks/abc443_d
　駒を上にしか動かせないことから，各 $i$ について，$A_{ i - 1 }$ と $A_{ i + 1 }$ は（そこが範囲外でないとき）$A_i + 1$ 以下でなければなりません．位置 $i$ ($i < n$) から $i + 1$ への制約だけを考えたとき，各 $i$ について $A'_i = \min( A_{ i - 1 } + 1, A_i )$ で置き換えた列と元々の列を zipWith min すれば，左側から制約される分を反映できます．右側からの制約も同様にして，$A''_i = \min( A_{ i + 1 } + 1, A_i )$ で置き換えた列と先程の結果を zipWith min すれば反映できます．こうして得られた列と一致するまで入力の列に操作をすればそれが最適で，そのコストは zipWith (-) してから sum すれば計算できます．
　列
\[
A'_i = \begin{cases}
A_i & \text{($i = 1$)} \\
\min( A_{ i - 1 } + 1, A_i ) & \text{(otherwise)}
\end{cases}
\]
の計算は scanl1 で計算できます．渡す関数はちょっとテクくて，min . succ で畳み込みます．min が $2$ 引数関数なのでこの合成は一見奇妙ですが，Curry 化されることを思い出すと理解できます．$( \min \circ \mathrm{ succ } )( A_{ i - 1 } )( A_i )$ の簡約を Curry 化を念頭に追うと，
\begin{align*}
( \min \circ \mathrm{ succ } )( A_{ i - 1 } )( A_i )
&= ( x \mapsto \min( \mathrm{ succ }( x ) ) )( A_{ i - 1 } )( A_i ) \\
&= ( \min ( \mathrm{ succ }( A_{ i - 1 } ) ) )( A_i ) \\
&= ( \min ( A_{ i - 1 } + 1 ) )( A_i ) \\
&= \min( A_{ i - 1 } + 1 )( A_i )
\end{align*}
のようになり，実装したい関数であることが確認できます．ただし，この関数は可換ではないので，左向きに畳み込むときには使えません．なので，入力全体を反転してから畳み込み，また反転して返すという風に使うことにします．前後で行う加工を g という関数で一般化すると

f g = g . scanl1 ( min . succ ) . g

という風に実装できて，外から id か reverse を渡すことでそれぞれ右向き・左向きの畳み込みになります．

main = readInt >>= flip replicateM do
	n <- readInt
	as <- readInts
	let
		f g = g . scanl1 ( min . succ ) . g
		res' = zipWith min as $ f id as
		res = zipWith min res' $ f reverse as
	print $ sum $ zipWith (-) as res

E

　問題文 : https://atcoder.jp/contests/abc443/tasks/abc443_e
　マス $( r, c )$ に侵入できる条件は，

マス $( r, c )$ が空マスである．
列 $c$ にある最も下（行番号が大きい）壁の左下・直下・右下に到達可能．

のいずれかを満たす場合です．よって，各列についてその列の最も下にある壁に触れるルートが存在するか否かをもちながら，各セルへの到達可能性を DP することで問題を解けます．
　より具体的には，まず各列について最も下にある壁の $y$ 座標を列
\[
L_j = \max( \{ i \mid i \in \{ 1, 2, \dots, n \}, \text{${ S_i }_j$ が壁} \} \cup \{ 0 \} )
\]
で表します．列に壁が存在しないときは $0$ としています．これを使って，以下のように状態をとる $2$ の DP を同時に回します：
\begin{align*}
\mathit{ dp }_b[j] &= \text{列 $j$ の一番下の壁を破壊可能か？($\mathrm{True}$/$\mathrm{False}$)} \\
\mathit{ dp }_r[i][j] &= \text{マス $( i, j )$ に到達可能か？($\mathrm{True}$/$\mathrm{False}$})
\end{align*}
更新は，配る DP ベースで考えると $i$ ($1 < i \leq n$) の降順に，

到達可能なマスの左上・直上・右上にある，その列で一番したの壁は破壊可能．
到達可能なマスの左上・直上・右上は，そこが空マスであるか，その列一番下の壁を破壊可能なら到達可能．

という条件分岐で，これをコード上の言葉に翻訳すればよいです．
　あとは実装です．まず $L$ の計算は，リストの do の中で入力の [String] と添字を zip しながら（ネストで）束縛して guard で篩うと壁セルの座標からなるリストを作れます．ここから accumArray max 0 で配列にすると $L$ を表す配列になります．
　DP 部分については，いつもの STUArray で手続き型的な DP をしてもよいのですが，今回はよりスマートっぽい方法でやってみます．DP のループで一番外側の添え字が $1$ ずつ進んで，その添え字の変化が常に $1$ であるような DP はよくあるかと思いますが，この手の DP は DP 配列を一段ずつ畳み込むことができたりします．今回であれば，例えば $\mathit{ dp }_r$ について，$\mathit{ dp }_r[i]$ から $\mathit{ dp }_r[ i - 1 ]$ を作る関数があれば，foldl で畳み込めます．そして，そういう関数は accumArray で実装できます．$\mathit{ dp }_b$ の方は現在の状態に論理 OR して更新する形になるので，accum で配列を作るようにすると実装できます．あとは，$2$ つの DP 配列を受け取ってそれぞれ一段進めたものを返す関数を書けば畳み込みによる DP が実装できます．

main = readInt >>= flip replicateM do
	[ n, c ] <- readInts
	ss <- replicateM n readStr
	let
		ls = accumArray @UArray @Int max 0 ( 1, n ) $ concat do
			( s, i ) <- zip ss [ 1 .. ]
			return do
				( c, j ) <- zip s [ 1 .. ]
				guard $ c == '#'
				return ( j, i )
		breakLowest =  listArray @UArray ( 1, n ) ( replicate n False )
		reachable = ( // [ ( c, True ) ] ) breakLowest
		stepDP ( reachable, breakLowest ) ( i, s ) = ( reachable', breakLowest' )
			where
			breakLowest' = accum @UArray (||) breakLowest do
				c <- [ 1 .. n ]
				c' <- [ c - 1 .. c + 1 ]
				guard $ reachable ! c && 1 <= c' && c' <= n
				return ( c', ls ! c' == i )
			reachable' = accumArray @UArray (||) False ( 1, n ) do
				c <- [ 1 .. n ]
				c' <- [ c - 1 .. c + 1 ]
				guard $ reachable ! c && 1 <= c' && c' <= n
				return ( c', s ! c' == '.' || breakLowest' ! c' )
		res = elems $ fst $ foldl stepDP ( reachable, breakLowest ) $ tail $ reverse $ zip [ 1 .. ] $ map ( listArray @UArray ( 1, n ) ) ss
	putStrLn $ map ( bool '0' '1' ) res