はじめに
テンプレは別記事．
A
問題文 : https://atcoder.jp/contests/abc411/tasks/abc411_a
言われた通り，length p と l を大小比較して判定します．
main = do p <- getLine l <- readInt putStrLn $ yesno $ l <= length p
これはこれでよいのですが，ワンライナー（風？）にしてみます．
出力部分に近いところから考えると putStrLn . bool "No" "Yes" という形になります．関数合成を右に伸ばしていくと考えるとこの右には (>=)（のようなもの）が来ることになりますが，全体として一つの入力から一つの出力への関数でなければならないので uncurry (>=) して $2$ 引数ではなく $2$ 要素タプルを受け取るようにします．あとは，入力をうまい感じに受け取って，putStrLn . bool "No" "Yes" . uncurry (>=) に渡せるタプルに変換する部分を書けばよいです．
入力の受け取りは，一行を一つの要素とするリストにするのがよさそうなので replicateM 2 getLine になります．リストのままだと具合が悪いのでタプルに変換したいですが，これには Control.Arrow にある (&&&) が使えて，( head &&& last ) を適用してあげると，$2$ 要素リストから $2$ 要素タプルに変換できます．最後に，$1$ 行目は長さに，$2$ 行目はその文字列が表す整数に変換するために ( length *** read ) を適用してあげれば，上述で書きかけだった部分に合成できます．
main = replicateM 2 getLine >>= putStrLn . bool "No" "Yes" . uncurry (>=) . ( length *** read ) . ( head &&& last )
B
問題文 : https://atcoder.jp/contests/abc411/tasks/abc411_b
（手続き型的には）各 $i, j$ について二重ループを回して，更に何らかの方法でその部分の区間和を求めます．三重ループにしてしまってもよいですが，Haskell では scanl で簡単に累積和をとれるので，そのようにしてみます．この問題ではやらなくてもよいですが，応用可能性のために累積和をリストではなく配列にします．入力の $2$ 行目の整数を並べたリストを ds とすると，累積和は scanl (+) 0 ds で作れます*1．これに listArray ( 1, n ) を適用してあげることでイミュータブル配列に変換できます．
あとは二重ループを回してあげて答えを計算すればよいですが，Haskell ではループという概念そのものを書く記法があるかというと微妙です．ここでは，リストモナドの do 記法を使います．
i <- [ 1 .. n - 1 ] return do j <- [ i + 1 .. n ]
のようにすることで二重リストを作れるので，あとは各 $i, j$ に対応する値を適切に計算して return してあげれば出力するべき二重リストを構成できます．
main = do n <- readInt ds <- readInts let ss = listArray ( 1, n ) $ scanl (+) 0 ds mapM_ printList do i <- [ 1 .. n - 1 ] return do j <- [ i + 1 .. n ] return $ ss ! j - ss ! i
C
問題文 : https://atcoder.jp/contests/abc411/tasks/abc411_c
ケースアナリシスをすると，黒の塊の個数の変化は
- 白から黒になるとき，
- 両隣が黒なら塊がくっついて $1$ 減る．
- 両隣が白なら新たな塊が出現して $1$ 増える．
- 黒から白になるとき，
- 両隣が黒なら塊が分裂して $1$ 増える．
- 両隣が白なら塊が消滅して $1$ 減る．
というようになります．よって，各マスの色と塊の個数を更新しながらシミュレートすることで問題を解くことができます．
普通に（とは？）考えると配列や再代入可能な変数が欲しくなりますが，Haskell でミュータブル配列や変数の再代入をするのは若干面倒で，ここでは ST モナドの中で STUArray と STRef を使います．堅牢性とのトレードオフということは分かっていますが，やはり C++ の変数・配列と比べて読み書きが面倒という気持ちを抱えつつ，上記のように値を読み書きします．
リストの各要素に対して順にアクションを実行する場合，よく forM_ を使ってアクションの結果を捨てる気がしますが，今回出力したいのは各操作後の塊の個数を並べたものなので，forM の中で操作後の塊の個数を return して直接リストを構築します．
main = do [ n, q ] <- readInts as <- readInts mapM_ print $ solve n as solve n as = runST do cs <- newArray ( 0, n + 1 ) False :: ST s ( STUArray s Int Bool ) res <- newSTRef 0 forM as $ \a -> do b1 <- readArray cs ( a - 1 ) b2 <- readArray cs ( a + 1 ) let d1 = bool 0 -1 $ b1 && b2 d2 = bool 0 1 $ not b1 && not b2 sgn <- bool 1 -1 <$> readArray cs a modifySTRef res $ ( + sgn * ( d1 + d2 ) ) modifyArray cs a not readSTRef res
D
問題文 : https://atcoder.jp/contests/abc411/tasks/abc411_d
Patricia 木を考えると，文字列末尾への連結は Patricia 木で辺を生やすことに対応します．また，Patricia 木のノードは根からそこに至るパス上にある文字列と $1$:$1$ 対応します．なので，各機器で文字列をもつ代わりに Patricia 木のノードへのポインタをもつことにすれば素直に実装できます．
C++ などで実装する場合は各ノードを表すために親ノードへのポインタと親への辺に割り当てられた文字列をもつ構造体を作る必要がある気がしますが，都合のよいことに Haskell では組み込みのリストがそういう構造になっています．
従って，（サーバを PC $0$ と見做した上で）各機器がもつ文字列に対応する Patricia 木のノードを [String] で保存するミュータブル配列を用意してクエリを愚直に処理することで問題を解くことができます．
実装面では，forM などで回すのではなく，クエリを処理する関数をクエリ列に map してアクションのリストを作って sequence で実行するのがスマートそうです．
また，リストに対する $O( 1 )$ 時間の追加操作は先頭に対するいわゆる cons なので，本来の向きとは逆になります．なので，[String] から出力を構成するときに reverse . concatMap reverse して逆順にします．
main = do [ n, q ] <- readInts queries <- replicateM q readStrs putStrLn $ solve n queries solve n queries = runST do pcs <- newArray ( 0, n ) [] :: ST s ( STArray s Int [String] ) let solve' [ "1", p ] = writeArray pcs ( read p ) =<< readArray pcs 0 solve' [ "2", p, s ] = modifyArray pcs ( read p ) ( s : ) solve' [ "3", p ] = writeArray pcs 0 =<< readArray pcs ( read p ) sequence $ map solve' queries reverse . concatMap reverse <$> readArray pcs 0
*1:累積和リストの先頭に $0$ を入れるかは派閥がある気もしますが，わたしは入れる派です
