https://torus711.hatenablog.com/entry/2026/01/14/232034

はじめに

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

A

　問題文 : https://atcoder.jp/contests/abc440/tasks/abc440_a
　言われた通りと言えば言われた通りですが，$x \times 2^y$ が答えになります．

main = do
	[ x, y ] <- readInts
	print $ x * 2^y

　これもいつも通りの手口で簡単にワンライナー風にできるのでやってみます．入力を [Int] として読み込んで Control.Arrow にある演算子たちを使って ( head &&& last ) で $2$ 要素リストをペアに変換できて，更に ( id *** (2^) ) でかけ合わせたい値のペアになります．あとは uncurry (*) に渡せば答えになります．

main = readInts >>= print . uncurry (*) . ( id *** ( 2^ ) ) . ( head &&& last )

B

　問題文 : https://atcoder.jp/contests/abc440/tasks/abc440_b
　入力される列を $\langle T_1, T_2, \dots, T_n \rangle$ として，各 $i$ ($i \in \{ 1, 2, \dots, n \}$) について $( T_i, i )$ というタプルを集めてきてソートし，第 $2$ 要素を取り出して先頭 $3$ つを読みます．
　タプルに変換する部分は，[ 1 .. ] と zip すればよいです．
　全体的にデータの流れが一直線で，zip を flip すると，処理中に現れるすべての関数が手前から渡される値を最後の引数で受け取るようになるので一行にできます．

main = readInt >> readInts >>= printList . take 3 . map snd . sort . flip zip [ 1 .. ]

C

　問題文 : https://atcoder.jp/contests/abc440/tasks/abc440_c
　$w' = 2w$ とします．
　まず簡単なケースとして，$n = w'$ な場合を考えます．このときは，$C$ が円環状になっていると見做して，連続する $w$ 個の要素の和の最小値が答えになります．
　次に，$n$ が $w'$ の倍数である場合を考えます．この場合は $\frac n {w'}$ 個ある列のそれぞれについて上述の問題をそれぞれ解いて答えを組み合わせる……のではなく，よく考えると和を取る区間の開始位置はすべての列で一致していなければなりません．よって，添字が ${} \bmod {w'}$ で合同な要素同士を足し合わせて得られる列について $n = {w'}$ の場合の問題を解けばよいです．
　ということでオリジナルの問題から帰着したいですが，$C$ を Data.List.Extra にある chunksOf で幅 $w'$ で区切って（[[Int]] にして）から，zipWith (+) で foldl1 することでほぼ加工できます．実際には $n$ が $w'$ の倍数とは限らないので前処理が必要です．答えを変えずに長さが $\left\lceil \frac n { w' } \right\rceil w'$ になるように後ろに何かをくっつければよいわけですが，くっつけるのは repeat 0 でよいです．$\left\lceil \frac n { w' } \right\rceil = \left\lfloor \frac { n + w' - 1 } {w'} \right\rfloor$ という有名なイディオムがあるので，あとは適当に take するだけです．
　そうして得られた列を列 as として，これを円環状のものとして扱うには，新たな列 as' = as ++ as を作って長さを $2$ 倍にしておくと境界部分の処理をしなくて済むので便利です．なお，これは as を束縛しなくても，uncurry (++) . ( id &&& id ) で中間変数無しに実装できます．
　最後に答えを求める部分ですが，連続する $w$ 個の連続する要素の和の最小値ということで，先頭 $w$ 個の和は sum $ take w as' です．ここから着目範囲をひとつ後ろにズラすと，head as' が範囲から抜けて head $ drop w as' が範囲に入ってきます．和の変化量は head ( drop w as' ) - head as' なわけですが，ここから，ひとつずつズラしていったときの変化量からなるリストは zipWith (-) ( drop w as' ) as' ということが分かります．なので，先頭 $w$ 個の和を初期値として scanl (+) で畳み込めば，連続する $w$ 個の和たちからなるリストが得られ，minimum を取ることで答えが求まります．

main = readInt >>= flip replicateM do
	[ n, w ] <- readInts
	let
		w' = 2 * w
	cs <- take ( ( n + w' - 1 ) `div` w' * w' ) . ( ++ repeat 0 ) <$> readInts
	let
		as = uncurry (++) $ ( id &&& id ) $ foldl1 ( zipWith (+) ) $ chunksOf w' cs
	print $ minimum $ scanl (+) ( sum $ take w as ) $ zipWith (-) ( drop w as ) as

D

　問題文 : https://atcoder.jp/contests/abc440/tasks/abc440_d
　解に関する二分法をします．ある整数 $t$ を固定したときに $A$ に含まれない $X_q$ 以上 $t$ 以下の整数の個数を求めたいです．$A$ を予めソートしておけば，

$X_q \leq A_i$ となる最小の $i$
$t < A_j$ となる最小の $j$

を二分探索によって計算できます．このとき，$X_q$ 以上 $t$ 以下で $A$ に含まれる整数の個数は $j - i$ であり，$X_q$ 以上 $t$ 以下の整数全体の個数である $t - X_q + 1$ から引けば $X_q$ 以上 $t$ 以下で $A$ に含まれないものの個数が分かります．この個数が $Y_q$ 以上になるような最小の $t$ を二分法することで答えが求まります．
　ということで，ソートした $A$ に対する二分探索と解に関する二分法をそれぞれ実装します．$A$ の二分探索は ac-library-hs の AtCoder.Extra.Bisect に実装があるのでこれを利用します．型クラス制約として Data.Vector を受け取ることになっているのでリストから変換してから渡すのですが，このとき Data.Vector.Unboxed の方を使わないと TLE したりします（STArray vs STUArray でも同じでしょという話ではあるのですが，基本的にリストを使っているせいか意識から抜けていました）．ということで $A$ に対する二分探索は実装できました．
　解に関する二分法ですが，こちらは自前で実装します．とはいえ，判定関数と区間の端点を受け取って適当に再帰するだけで実装できます．

import qualified Data.Vector as V
import AtCoder.Extra.Bisect

-- テンプレ略

main = do
	[ n, q ] <- readInts
	as <- V.fromList . sort <$> readInts
	xys <- replicateM q readInts
	mapM_ print do
		[ x, y ] <- xys
		let
			i = lowerBound as x
		return $ binaryMethod ( maxBound `div` 2 ) ( x - 1 ) $ \t -> 
			let j = upperBound as t in
				y <= ( t - x + 1 ) - ( j - i )

binaryMethod ok ng f
	| abs ( ok - ng ) <= 1 = ok
	| otherwise = let mid = ( ok + ng ) `div` 2 in
		if f mid
			then binaryMethod mid ng f
			else binaryMethod ok mid f

E

　問題文 : https://atcoder.jp/contests/abc440/tasks/abc440_e
　美味しさの和が最大の状態からスタートして，クッキーを一枚入れ替えることで微妙に不味くするという遷移で最良優先探索のようなことをします．分かりやすさのために $A$ は降順ソート済みとして，$n$ 要素の列で状態を表現します．具体的には，列の $i$ 番目の値が $i$ 番のクッキーの個数です．従って初期状態は $\langle k, \underbrace{ 0, 0, \dots, 0 }_{ \text{$n - 1$ 個} } \rangle$ で，美味しさの和は $k A_1$ です．遷移は，$A_i \neq 0$ であるような $i$ ($1 \leq i < n$) について $A_i$ を $1$ 減らして $A_{ i + 1 }$ を $1$ 増やします．こうして生成される状態たちを未訪問状態として管理し，美味しさの和が大きい順に訪問していきます．
　$A$ のもち方については，添字アクセスを行うので listArray でイミュータブル配列にしておきます．状態の方は，添字アクセスに加えて定数個の要素を変更したものを楽に得られるものがよいです．この条件に当て嵌まるならなんでもよい気がしますが，ここでは Data.Vector.Unboxed を使ってみます．(//) によって代入先と値のリストを受け取ってまとめて変更した結果を得られるのでよさげです．
　訪問済みの状態の近傍を保持し評価値最大のものを取り出す部分には Data.Set を使います．最大値をある程度高速に取り出せる必要があるのに加え，ある状態に複数の手順で到達できる場合はその内ひとつのみを採用しなければならないので重複排除もできる Data.Set は都合がよいです．
　ということでまとめると，

答えに追加するべき残り要素数
次に訪問する近傍をもつ Data.Set

を受け取って，問題の答えとなるリストを返す関数を実装することで問題を解けます．内部では，Data.Set の先頭を取り出してからリストの do などで変更後の Data.Vector のリストを作って Set.insert で foldl することで近傍集合を更新します．

import qualified Data.Vector.Unboxed as VU

-- テンプレ略

main = do
	[ n, k, x ] <- readInts
	as <- listArray ( 0, n - 1 ) . reverse . sort <$> readInts
	mapM_ print $ solve k x as

solve k x as = solve' x ( Set.singleton $ ( k * as ! 0, ) $ VU.fromList $ k : replicate ( n - 1 ) 0 )
	where
	n = length as
	solve' 0 s = []
	solve' x s = c : ( solve' ( x - 1 ) $ foldl ( flip Set.insert ) s' do
		i <- [ 0 .. n - 2 ]
		let
			vi = v VU.! i
			j = i + 1
			vj = v VU.! j
			c' = c - as ! i + as ! j
		guard $ vi /= 0
		return ( c', v VU.// [ ( i, vi - 1 ), ( j, vj + 1 ) ] ) )
		where
		sz = Set.size s
		( c, v ) = Set.elemAt ( sz - 1 ) s
		s' = Set.take ( sz - 1 ) s