以下の内容はhttps://torus711.hatenablog.com/entry/2025/11/09/182344より取得しました。


Haskell で AtCoder ABC 431 A-C

はじめに

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

A

 問題文 : https://atcoder.jp/contests/abc431/tasks/abc431_a
 $h \geq b$ のとき $h - b$ が答えで,そうでないとき $0$ が答えです.条件分岐でもよいのですが,$h - b < 0$ なら $0$ に揃える,と思って読み替えると $\max( 0, h - b )$ にまとめられます.

main = do
	[ h, b ] <- readInts
	print $ max 0 ( h - b )

 これはこれでよいのですが,単純なので今回も一行にしていきます.
 readInts から $h - b$ をどうにか作ることができれば,readInts >>= print . max 0 にくっつけることで実装できます.ポイントフリースタイルで (-) を適用する常套手段だと思いますが,uncurry (-) の形で使うことで一引数関数として繋げられます.後はリストから順序対 $( h, b )$ を作る部分ですが,$h, b$ はそれぞれリストの先頭と末尾だと思えば,Control.Arrow にある (&&&) を使って ( head &&& last ) と書けます.
 ということで,こうなります.

main = readInts >>= print . max 0 . uncurry (-) . ( head &&& last )

B

 問題文 : https://atcoder.jp/contests/abc431/tasks/abc431_b
 答えの求め方の構造は,$i$ の昇順に $W_{ P_i }$ を足したり引いたりする形になります.$W$ は入力に listArrayfmap ((<$>)) してイミュータブル配列にしておくとして,足し引きする値の絶対値からなるリストなら map ( ws ! ) ps で作れます.このリストの各要素に足すときは id,引くときは negate を適用してあげれば,scanl (+) x に渡して畳み込めます.id, negate からなる関数のリスト ([ Int -> Int ]) が作れれば,($)zipWith することで対応する要素ごとに関数を適用できます.
 関数のリストは $P$ を走査しながら作ります.走査中の各 $P_i$ について id を返すか negate を返すかはその $P_i$ の出現回数の奇偶によって決まります.(気にしなくても通せる制約ですが,)計算量もちょっと気にすると Bool を要素とするミュータブル配列が欲しい気持ちになり,この部分の実装が一番面倒という感想です.とりあえず,配列の名前は mounted としておきます.
 $P$ を走査して値ごとに何か処理をする部分は forM を使います(「何かするだけ」ならよく forM_ を使いますが,今回は結果を取り出したいので forM).実行するアクションは以下の $2$ 工程です:

  • mounted の $P_i$ 番目の要素を反転する.
  • mounted の $P_i$ 番目の真偽によって idnegate を返す.

前者は,当該要素に not を適用してあげればよいので,(昔は無かった気がするのですがいつの間にか生えている)Data.Array.MArray にある modifyArraymodifyArray mounted p not とすればよいです.後者は,readArray mounted p の値によって結果を分けたいですが,$2$ つの値を Bool を受け取って真偽によってどちらかの値を返す関数としては bool があるのでこれが使えます.readArray はアクションなのでそのまま bool に渡せませんが,fmap すると一時変数を作らずに済みます.

main = do
	x <- readInt
	n <- readInt
	ws <- listArray ( 1, n ) <$> readInts
	q <- readInt
	ps <- replicateM q readInt
	mapM_ print $ tail $ scanl (+) x $ zipWith ( flip ($) ) ( map ( ws ! ) ps ) $ runST do
		mounted <- newArray ( 1, n ) False :: ST s ( STUArray s Int Bool )
		forM ps $ \p -> do
			modifyArray mounted p not
			bool negate id <$> readArray mounted p

C

 問題文 : https://atcoder.jp/contests/abc431/tasks/abc431_c
 実装メインのシリーズなので証明はしませんが,$H, B$ をそれぞれソートすると,$H$ の先頭 $k$ 要素と $B$ の末尾 $k$ 要素を(元々の順序のまま)マッチさせるのが最適で,この方法でできないなら不可能です.
 ということで,入力をそれぞれソートしてから take k, takeEnd k したものを and . zipWith (<=) すればほぼ答えです.実装だけなら B よりずっと楽ですね.

main = do
	k <- last <$> readInts
	hs <- sort <$> readInts
	bs <- sort <$> readInts
	putStrLn $ yesno $ and $ zipWith (<=) ( take k hs ) ( takeEnd k bs )



以上の内容はhttps://torus711.hatenablog.com/entry/2025/11/09/182344より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14