はじめに
実装メイン．テンプレは別記事．
A
問題文 : https://atcoder.jp/contests/abc445/tasks/abc445_a
言われた通り，入力文字列の head と tail を比較します．どう実装してもよい気がしますが，Control.Arrow にある演算子を head &&& last のように使うと先頭と末尾からなるタプルに分解できて，uncurry (==) につなげることで，既存関数の合成で表現できます．
main = getLine >>= putStrLn . yesno . uncurry (==) . ( head &&& last )
B
問題文 : https://atcoder.jp/contests/abc445/tasks/abc445_b
こちらも言われた通りに実装します．文字列たちの最大長は maximum . map length で求められ，くっつけるべき . の個数は算数できます．
. を指定の個数並べたリストは replicate で作ることができて，後は適当に連結するだけです．リストの連結は ++ ですが，リストの連結が半群を成すことから Semigroup という型クラスに入っているようで，Semigroup の演算 <> で連結しているヒトをよく見かける今日此頃です．なお，モノイドでもあるので Monoid 型クラスにも入っていて mappend でも連結できますが，今のケースだと長いからという理由で使われていない気がします．（ところで，明らかにリストしか扱わない場面で代数に抽象化した方がよいのかはちょっと疑問が無いでもないです．）
main = do n <- readInt ss <- replicateM n readStr let m = maximum $ map length ss mapM_ putStrLn do s <- ss let k = ( m - length s ) `div` 2 ds = replicate k '.' return $ ds <> s <> ds
C
問題文 : https://atcoder.jp/contests/abc445/tasks/abc445_c
問題文をよく読むと駒は右にしか動きません．よって，右のセルから順に遷移を逆順に反映することで問題を解けます．もし遷移たちを反映するべき順序通りにリストにできているとすれば，それを舐めながらミュータブル配列を操作すれば問題を解けます．遷移を並べる操作は，zip as [ 1 .. ] してから accumArray ( flip (:) ) [] を経由してリストに戻すなどすることで線形時間で処理できます．遷移を ST の外側の純粋なところで作っておくと runSTUArray の中はかなりすっきりします．
main = do n <- readInt as <- readInts let rs = reverse $ assocs $ accumArray @Array ( flip (:) ) [] ( 1, n ) $ zip as [ 1 .. ] printList $ elems $ solve n $ concat do ( u, vs ) <- rs return $ zip ( repeat u ) vs solve n es = runSTUArray do dp <- newListArray ( 1, n ) [ 1 .. n ] :: ST s ( STUArray s Int Int ) forM_ es $ \( u, v ) -> do modifyArray dp v =<< max <$> readArray dp u return dp
別解として，遷移をダブリングすることでも解くことができます．ダブリングしたい対象が関数 f だとすると，一段階のダブリングは f . f で，ポイントフリースタイルにするなら uncurry (.) . ( id &&& id ) です．入力列 $A$ をイミュータブル配列 as として読み込んだとすれば，( as ! ) を適当な段数ダブリングすれば初期位置から最終位置への対応を表す配列が得られます．ダブリングを繰り返す部分は iterate してから適当な位置の要素をとってくればよいです．
main = do n <- readInt as <- listArray @UArray ( 1, n ) <$> readInts let double = uncurry (.) . ( id &&& id ) as' = ( !! 20 ) $ flip iterate as \as -> array ( 1, n ) $ zip [ 1 .. n ] $ map ( double ( as ! ) ) [ 1 .. ] printList $ map ( as' ! ) [ 1 .. n ]
D
問題文 : https://atcoder.jp/contests/abc445/tasks/abc445_d
設定から，生成するカケラの内，手に持っているものと縦または横の片方が一致するものが必ず存在するので，それを切り出して作業台の左上に置くことができます．その後，作業台上でカケラに占有された部分を見ないことにつつ残りのカケラに着目すると同じ構造の問題が出てくるので，再帰的に問題を解くことができます．
ある状態から次に切り出されるカケラは縦幅が最大のものか横幅が最大のもののいずれかです．よって，カケラ（の番号）を縦幅の降順と横幅の降順についてソートしたものをそれぞれもっておけば，使用済みのものを読み飛ばしてから手持ちの縦幅・横幅と比較することで次に切り出されるカケラを高速に特定できます．ということで，
- 次にカケラを置く位置
- カケラ番号を縦幅降順でソートしたキュー（を模倣するリスト）
- カケラ番号を横幅降順でソートしたキュー（を模倣するリスト）
- 切り出し済みカケラの番号からなる
Data.IntSet
を管理すれば結果の書き出しと次の状態の計算および再帰ができます．
カケラ番号のソートは sortOn で簡単に実装できます．再帰本体ですが，今回は（今回も？）unfoldr を使ってみます．今回は「畳み込みの逆」っぽい感じはやや薄い気もしますが，より一般に，ある状態が終端状態なら終了，そうでなければ再帰というスキームを実装するのに使えます．
unfoldr に渡す関数の中身としては，それぞれのキュー（を模倣するリスト）の先頭から使用済みを取り除いてからそれぞれの先頭を見て縦に割るのか横に割るのかを判定します．使用済みを取り除く部分は dropWhile です．答えとして書き出す値や次の状態はちょっとした条件分岐で実装でき，unfoldr のインターフェースに従って Maybe を返せば unfoldr できます．
出力を作る部分ですが，カケラ番号と答えのタプルリストを返すことにしておいて array で配列にすると順序を整えられます．
main = do [ h, w, n ] <- readInts [ hs, ws ] <- map ( listArray @UArray ( 1, n ) ) . transpose <$> replicateM n readInts let queH = reverse $ sortOn ( hs ! ) [ 1 .. n ] queW = reverse $ sortOn ( ws ! ) [ 1 .. n ] mapM_ printList $ array @Array ( 1, n ) $ unfoldr ( solve n h w hs ws ) ( 1, 1, queH, queW, ISet.empty ) solve n h w hs ws ( y, x, queH, queW, s ) | null queH' = Nothing | otherwise = Just ( ( k, [ y, x ] ), ( y', x', queH', queW', ISet.insert k s ) ) where queH' = dropWhile ( flip ISet.member s ) queH queW' = dropWhile ( flip ISet.member s ) queW ( k, y', x' ) = if hs ! head queH' == h - y + 1 then ( head queH', y, x + ws ! k ) else ( head queW', y + hs ! k, x )
