https://torus711.hatenablog.com/entry/2025/05/07/202245

はじめに

　テンプレは別記事．

A

　問題文 : https://atcoder.jp/contests/abc404/tasks/abc404_a
　英小文字であって，入力文字列 $S$ に含まれないものをひとつ出力する問題です．
　リスト [ 'a' .. 'z' ] から条件を満たすものを filter して，そこから適当なものをひとつ（例えば先頭）を出力すればよいです．「$S$ に含まれない」は ( `notElem` s ) です．
　ワンライナー風にするなら，notElem と filter の引数の順序が都合悪いので，それぞれ flip するとスムーズに繋がります．
　一文字を出力ということで putChar してから putChar '\n' で改行を出力していますが，take 1 して文字列として出力してしまえば余計な手間はかからないので，悩みどころです（意味的にちょっと気になる）．

main = getLine >>= putChar . head . flip filter [ 'a' .. 'z' ] . flip notElem >> putChar '\n'

B

　問題文 : https://atcoder.jp/contests/abc404/tasks/abc404_b
　$2$ 色からなる模様を表現するグリッド $S, T$ が与えられます．$S$ に対して，

全体を右に $\frac \pi 2$ ラジアン回転させる．
セルを一つ選び．色を他方の色に変更する．

の操作ができるとき，$S$ を $T$ に一致させるのに必要な操作回数の最小値を求める問題です．
　回転させる回数が固定ならば，$S$ と $T$ で色が異なるセル全てのみの色を変更するのが最適なので，（高々 $3$ しかない）回転回数を全て試して色変更の回数を数えればコストがそれぞれ求まり，あとは最小値を出力すればよいです．
　右回転を実装するのが面倒に思えてしまいますが，実は transpose . reverse が右回転になっています．これは，

回転によって行と列が入れ替わる．
元々上にあった行は回転後は右の列になる．

という風に分解して考えると理解できます．ある初期値からある関数を繰り返し適用して現れる値を並べた（無限）リストを得る関数 iterate があるので，iterate ( transpose . reverse ) して take 4 すれば回転によって得られる模様が全て得られます．
　色（というか一般に「値」）が異なる部分を数えるのは length . filter id . zipWith (/=) でできますが，今回は二次元リストなのでリストをそれぞれ concat する必要があります．
　本問では回転の回数も加味しなければならないので，iterate した後に [ 1 .. ] と zip するなどして回転回数の情報を取り出せるようにしておく必要があります．

main = do
	n <- readInt
	ss <- replicateM n getLine
	ts <- replicateM n getLine
	print $ minimum do
		( i, ss' ) <- take 4 $ zip [ 0 .. ] $ iterate ( transpose . reverse ) ss
		return $ ( i + ) $ length $ filter id $ zipWith (/=) ( concat ss' ) ( concat ts )

C

　問題文 : https://atcoder.jp/contests/abc404/tasks/abc404_c
　与えられる $n$ 頂点 $m $ 辺のグラフが chordless-cycle であるかを判定する問題です．
　まず入力からの無向グラフの受け取りですが，各辺の情報は片方向しか与えられないのでこちらで双方向化する必要があります．前回までは無名関数を書いていましたが，Control.Arrow にある (&&&) で id したものと map reverse したものを作ってからくっつけた方が「ありもの」で書けてよいかもしれません．
　さて本題ですが，同値な条件は，

全ての頂点の次数が $2$．かつ，
グラフが連結．

なので，それぞれ調べます．
　次数については（双方向化済みの）辺リストの fst 側にある要素を数えればよいです．map length . group . sort すればできますが，時間計算量が $O( m \log m )$ 時間で余計な $\log$ がついてしまいます．線形時間にするには，accumArray (+) 0 で配列を使って数えてから elems でリストに戻す方法があって，この場合は $O( n + m )$ 時間になります．
　連結性については，適当な頂点から DFS をして全ての頂点を訪問できるかどうかを調べます．DFS の中身をどう実装するにせよ，グラフは隣接リストの形になっていると扱いやすいので，まずは辺リストから隣接リストを作ります．これは度々登場していますが，辺リストから accumArray ( flip (:) ) [] で作れます．
　DFS の実装として楽なものとしては，訪問済み頂点の集合を Data.IntSet などとして引数で引き回す方法があります．この場合，（DFS する関数の引数順序を適切に設計すれば）ある頂点から隣接頂点への訪問を foldl による畳み込みで処理できますが，データ構造の操作に余計な時間がかかります．

main = do
	[ n, m ] <- readInts
	es <- map mp . uncurry (++) . ( id &&& map reverse ) <$> replicateM m readInts
	let
		degrees = elems $ accumArray (+) 0 ( 1, n ) $ zip ( map fst es ) ( repeat 1 )
		graph = accumArray ( flip (:) ) [] ( 1, n ) es
	putStrLn $ yesno $ all ( == 2 ) degrees && ISet.size ( dfs graph [] 1 ) == n 

dfs graph visited u
	| ISet.member u visited = visited
	| otherwise = foldl ( dfs graph ) ( ISet.insert u visited ) $ graph ! u

　$O( n + m )$ 時間で処理するには，ST モナドの各頂点が訪問済みか否かを STUArray などで管理します．

main = do
	[ n, m ] <- readInts
	es <- map mp . uncurry (++) . ( id &&& map reverse ) <$> replicateM m readInts
	let
		degrees = elems $ accumArray (+) 0 ( 1, n ) $ zip ( map fst es ) ( repeat 1 )
		graph = accumArray ( flip (:) ) [] ( 1, n ) es
	putStrLn $ yesno $ all ( == 2 ) degrees && connected graph

connected graph = runST do
	visited <- newArray ( 1, n ) False :: ST s ( STUArray s Int Bool )
	let
		dfs u = do
			whenM ( not <$> readArray visited u ) do
				writeArray visited u True
				forM_ ( graph ! u ) \v -> do
					dfs v
	dfs 1
	and <$> getElems visited
	where
	n = snd $ bounds graph

D

　問題文 : https://atcoder.jp/contests/abc404/tasks/abc404_d
　各動物園を訪問する回数は $0, 1, 2$ の $3$ 通りで，動物園の数は高々 $10$ と少ないので，$3^n$ 通りある組合せを全て試します．長さが $n$ で各要素が $0, 1, 2$ のいずれかであるようなリスト全てを作れれば，各動物を見る回数やコストはリスト処理と accumArray で実装できるので，この部分がキモになります．
　やや唐突ですが，リストモナドの do による次のコードを考えてみます：

do
	a <- [ 0, 1, 2 ]
	b <- [ 0, 1, 2 ]
	return $ [ a, b ]

このコードでは，長さが $2$ で各要素が $0, 1, 2$ のいずれかであるようなリストが作れます．なので，[ 0, 1, 2 ] から値を取り出す回数を一般化できれば目的のものが手に入ることになります．[ 0, 1, 2 ] を $n$ 個並べるのは replicate でできて．それを sequence することで上記コードのように値の取り出し方全通りを網羅するリストを構成できます．

main = do
	[ n, m ] <- readInts
	cs <- readInts
	ass <- map tail <$> replicateM m readInts
	let
		animalsAt = elems $ accumArray ( flip (:) ) [] ( 1, n ) $ concat do
			( i, as ) <- zip [ 1 .. ] ass
			return $ zip as ( repeat i )
	print $ minimum do
		ts <- sequence $ replicate n [ 0, 1, 2 ]
		guard $ all ( 2 <= ) $ elems $ accumArray (+) 0 ( 1, m ) $ concat $ zipWith zip animalsAt ( map repeat ts )
		return $ sum $ zipWith (*) cs ts

E

　問題文 : https://atcoder.jp/contests/abc404/tasks/abc404_e
　ボールが入っている各箱から，その左の箱か箱 $0$ の内で最も右にあるものに移動させるまでの操作回数の最小値を順に求めます．基本的には箱 $0$ までの操作回数を求める DP をしますが，ボールが入っている箱を見つける度に，そこまでのコストを $0$ に書き換えることでうまいことやります．

main = do
	readStr
	cs <- ( 0 : ) <$> readInts
	as <- ( 0 : ) <$> readInts
	print $ solve cs as

solve cs as = runST do
	dp <- newArray ( 1, n ) ( maxBound `div` 2 ) :: ST s ( STUArray s Int Int )
	writeArray dp 1 0
	res <- newSTRef 0
	forM_ ( zip3 [ 1 .. ] cs as ) \( i, c, a ) -> do
		forM_ [ i - c .. i ] \j -> do
			modifyArray dp i =<< min . succ <$> readArray dp j
		when ( 0 < a ) do
			modifySTRef res =<< (+) <$> readArray dp i
			writeArray dp i 0
	readSTRef res
	where
	n = length cs