A - Buying Sweets
シグネチャを決める。横着する。
abc087a :: [Int] -- X,A,B
-> Int -- 答え
abc087a [x,a,b] = mod (x - a) b
B - Coins
シグネチャを決める。横着する。
abc087b :: [Int] -- A,B,C,X
-> Int -- 答え
公式解説では3重ループで各硬貨の枚数を総当たりしろと言っているけど、一番内側は回す必要がない。
結果
abc087b [a,b,c,x] = length
[ ()
| i <- [0 .. a], let x1 = x - 500 * i, x1 >= 0
, j <- [0 .. b], let x2 = x1 - 100 * j, x2 >= 0
, let k = div x2 50, k <= c]
C - Candies
シグネチャを決める。
abc087c :: Int -- N
-> [Int] -- A1,*
-> [Int] -- A2,*
-> Int -- 答え
右か下にしか行けないので、右に $k-1$ 回移動して $A_{1,1}$ から $A_{1,k}$ を得て、
下に1回、右に $N-1-k$ 回移動して $A_{2,k}$ から $A_{2,N}$ を得る、という値の最大値を探す。
結果
abc087c _n as bs = maximum $ zipWith (+) (scanl1 (+) as) (scanr1 (+) bs)
D - People on a Line
シグネチャを決める。横着する。
abc087d :: Int -- N
-> Int -- M
-> [[Int]] -- Li,Ri,Di
-> Bool -- 答え
知っていれば、頂点の高低差を同時に管理する Union-Find の変種を導入する練習問題とわかる。
Union-Findの配列は、同じ分割に所属する親ノードへのリンクを保持する。
もう一つ配列を用意して、親ノードとの高低差を記録する。
二つの頂点を統合しようとするとき、
- 既に同じ分割に属しているとき、両者の高低差が指定と一致するなら成功、食い違うとき失敗となる
- 統合するとき、根どうしを統合する。このとき高低差を正しく設定する。
代表元を辿る際に経路圧縮を行う。このときも高低差を維持する必要がある。
結果
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
abc087d :: Int -> Int -> [[Int]] -> Bool
abc087d n _m lrds0 = runST $
do
uf <- newUF (1,n)
loop uf lrds0
where
loop _ [] = return True
loop uf ((l:r:d:_):lrds) = do
x <- uniteUF uf l r d
if x then loop uf lrds else return False
-- 高さ維持 Union-Find ふたつめの配列に、直接の親との高低差を保持
-- データ表現
-- 自分の番号を指しているとき、自分が代表元
type UnionFind s = (STUArray s Int Int, STUArray s Int Int)
-- Union-Find構造体を作る
newUF :: (Int,Int) -> ST s (UnionFind s)
newUF bnds = do
tr <- newListArray bnds $ range bnds
ht <- newArray bnds 0
return (tr, ht)
-- 代表元と、代表元との高低差を得る
-- 経路圧縮も行う
getRoot :: UnionFind s -> Int -> ST s (Int, Int)
getRoot uf@(tr, ht) j = do
k <- readArray tr j
d <- readArray ht j
if k == j then return (j, d) else do -- このとき d == 0
(r, b) <- getRoot uf k
writeArray tr j r
let h = b + d
writeArray ht j h
return (r, h)
-- 統合を試みる
-- 既に根が同じとき、指定の高低差が正しければよし、さもなくば失敗。
-- 根が異なるとき、接ぎ木を行う。
uniteUF :: UnionFind s -> Int -> Int -> Int -> ST s Bool
uniteUF uf@(tr,ht) i j d = do
(a, hi) <- getRoot uf i
(b, hj) <- getRoot uf j
if a == b then return (hi + d == hj) else do
writeArray tr b a
writeArray ht b (d + hi - hj)
return True
グラフを辿る方法
公式解説のやり方。N頂点のグラフを考える。
$(L_i, R_i, D_i)$ を、順方向の重み $D_i$ 逆方向の重み $-D_i$ の辺とする。
到達可能な範囲の頂点について、高低差が矛盾無く割り付けられるかを確認する。
頂点番号と、高さの指定があるならそれを Maybe で持つスタックを自前で管理するDFSで実装した。
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array
import Data.Maybe
abc087d :: Int -> Int -> [[Int]] -> Bool
abc087d n _m lrds = runST $
do
v <- newArray (1,n) False :: ST s (STUArray s Int Bool) -- 高さ設定済みフラグ
h <- newArray_ (1,n) :: ST s (STUArray s Int Int) -- 高さ
loop v h [(i, Nothing) | i <- [1 .. n]]
where
g = accumArray (flip (:)) [] (1,n) $
[(l,(r, d)) | l:r:d:_ <- lrds] ++
[(r,(l,-d)) | l:r:d:_ <- lrds]
loop _v _h [] = return True
loop v h ((i, mh):imhs) = do
vi <- readArray v i
hi <- readArray h i
if vi then do
let a = fromMaybe hi mh
if hi == a then loop v h imhs else return False
else do
let a = fromMaybe 0 mh
writeArray v i True
writeArray h i a
loop v h $ [(j, Just $ a + d) | (j,d) <- g ! i] ++ imhs
ところで
$(1,2,10^4),(2,3,10^4),\cdots,(10^5-1,10^5,10^4)$ とひたすら積み上げるようにしたとき、$x_1 = 0, x_{10^5} = (10^5 - 1) \times 10^4 < 10^9$ なので、高低差が限度を超える心配は不要だった。