A - Glutton Takahashi
シグネチャを決める。
abc364a :: Int -- N
-> [String] -- Si
-> Bool -- 答え
sweet と salty では1文字目では区別が付かないので、2文字目を見比べる。
w が連続しなければ問題ない。
例2のように、連続していても、それが末尾ならセーフなのがちょっと意地悪。
結果
import Data.List
abc364a :: Int -> [String] -> Bool
abc364a _n ss =
case dropWhile (('w','w') /=) $ zip was $ tail was of
[_] -> True
[] -> True
_ -> False
where
was = map (!! 1) ss
B - Grid Walk
シグネチャを決める。
abc364b :: [Int] -- H,W
-> [Int] -- Si,Sj
-> [String] -- Cij
-> String -- X
-> [Int] -- 答え
地図を作って忠実にシミュレーションする。
結果
import Data.Array.Unboxed
abc364b :: [Int] -> [Int] -> [String] -> String -> [Int]
abc364b [h,w] [si,sj] ss x = [gi,gj]
where
bnds = ((1,1),(h,w))
arr :: UArray (Int,Int) Bool
arr = listArray bnds [c == '.' | s <- ss, c <- s]
(gi,gj) = foldl step (si,sj) x
step ij d
| inRange bnds ij1, arr ! ij1 = ij1
| otherwise = ij
where
ij1 = move ij d
move (i,j) 'L' = (i, pred j)
move (i,j) 'R' = (i, succ j)
move (i,j) 'U' = (pred i, j)
move (i,j) 'D' = (succ i, j)
C - Minimum Glutton
シグネチャを決める。
abc364c :: [Int] -- N,X,Y
-> [Int] -- Ai
-> [Int] -- Bi
-> Int -- 答え
コストを大きい順に整列し、前から足し合わせると、食べる個数を極力少なくして稼げるコスト合計が個数ごとにわかる。
達成目標のXまたはYを越えたら止めるまでの個数は、累積和が目標以下である個数+1であるが、例2のように全部食べても足らない場合がありうるのでNを上限にする。
結果
import Data.List
abc364c :: [Int] -> [Int] -> [Int] -> Int
abc364c [n,x,y] as bs = min (f x as) (f y bs)
where
f u = min n . length . takeWhile (u >=) . scanl (+) 0 . sortBy (flip compare)
D - K-th Nearest
シグネチャを決める。
abc364d :: Int -- N
-> Int -- Q
-> [Int] -- Ai
-> [[Int]] -- Bi,Ki
-> [Int] -- 答え
差 $R$ について、$[B_i - R, B_i + R]$ の範囲に入る $A_j$ の個数が $K_i$ である（以上である最小の）$R$ を二分探索で探す。
結果
import qualified Data.IntMap as IM
abc364d :: Int -> Int -> [Int] -> [[Int]] -> [Int]
abc364d _n _q as bks = map f bks
where
cnt = IM.fromListWith (+) [(a, 1) | a <- minBound : maxBound : as] -- 各Aiの個数
(_,acc) = IM.mapAccum (\a b -> let c = a + b in (c,c)) 0 cnt -- Ai以下の値の個数
-- BiからKi番目の値との差
f (b:k:_) = snd $ binarySearch (prop b k) (-1) (succ $ 2 * 10^8)
-- Bi±R の範囲にあるAiはK個以上
prop b k r = k <= c4 - c1
where
Just (_, c1) = IM.lookupLT (b - r) acc
Just (_, c4) = IM.lookupLE (b + r) acc
binarySearch :: (Int -> Bool) -> Int -> Int -> (Int, Int) -- 定義略
E - Maximum Glutton
シグネチャを決める。
abc364e :: [Int] -- N,X,Y
-> [[Int]] -- Ai,Bi
-> Int -- 答え
甘さと塩辛さの二つのコスト軸を持つナップザック問題と捉えられる。
合計 $X, Y$ 以下で選べる最大の料理数を求める。次にもう一つ何か選ぶと制限を超えるので最後に+1する。ただし $N$ を越えない範囲で。
選んだ料理の個数 $0 \leq i \leq N$
甘さの総和 $0 \leq p \leq X$
に対して、その状態になる塩辛さの総和の最小値 $0 \leq q \leq Y$ を表 $T$ にする。
次の料理 $(A_i, B_i)$ に対して $T[j + 1, p + A_i]$ を $T[j, p] + B_i$ と小さい方で更新する。$T$ は広範囲が更新されるのでimmutable arrayでよい。
全ての料理を検討した後、料理の個数添え字の最大値を探す。
結果
import Data.List
import Data.Array.Unboxed
abc364e :: [Int] -> [[Int]] -> Int
abc364e [n,x,y] abs = min n $ succ $ maximum [j | ((j, _p), q) <- assocs arrN, q < tooBig]
where
tooBig = succ y
arr0 = accumArray min tooBig ((0,0),(n,x)) [((0,0),0)] :: UArray (Int,Int) Int
arrN = foldl' step arr0 abs
step arr (a:b:_) =
accum min arr
[ ((succ j, pa), q1)
| ((j, p), q) <- takeWhile ((n >) . fst . fst) $ assocs arr
, let pa = p + a, pa <= x
, let q1 = q + b ]
メモリ消費を抑えてキャッシュに入りやすくするために arr の要素を Word16 にしてみたが Int のままと結果は変わらなかった。
一方、Array を UArray にすると劇的に高速化した。
F - Range Connect MST
シグネチャを決める。
abc364f :: Int -- N
-> Int -- Q
-> [[Int]] -- Li,Ri,Ci
-> Int -- 答え
公式解説ベースの解き方
公式解説、別解 by evima と本質的に同じ考え方。区間の管理の仕方が違うだけ。
1～Nの範囲の頂点について、普通は「辺を張り終わったもの」を記録していくと発想するが、逆に「まだ辺が張っていない範囲」を記録する。
クルスカル法の発想で、$C_i$ の小さいクエリから処理し、指定の範囲 $[L_i,R_i]$ の中で、まだ辺が張ってないもの全てを取り除く。このとき、その個数分だけ辺が必要になる。しかしこれだと、相互に接続されたのか、$R_j + 1 = R_k$ のようにぴったり並んだ区間があるだけで接続されていないのか判別できない。
$[L_i,R_i]$ を「辺の張っていない範囲」から取り除くことで、これを含む空白の範囲 $[\ell \leq L_i, R_i \leq r]$ （$l-1,r+1$ は残っている）ができる。この区間のうち一箇所、代表として $\ell$ は取り除かずに残しておく。この配慮をすることで、互いに接続になるために必要な辺の最安コストも同時に算出できる。
最終的に「辺の張っていない範囲」が $[1]$ になれば成功となる。
import qualified Data.IntSet as IS
abc364f :: Int -> Int -> [[Int]] -> Int
abc364f n _q lrcs
| isOK = sum ss
| otherwise = -1
where
isOK = [1] == IS.elems isN
(isN, ss) = mapAccumL step is0 $ sortOn (!! 2) lrcs
is0 = IS.fromDistinctAscList [1 .. n]
step is (l:r:c:_) = (is123, c * c2)
where
Just l1 = IS.lookupLE l is -- \ell
c2 = IS.size $ fst $ IS.split (succ r) $ snd $ IS.split (pred l1) is -- [L1,R]にある要素数
is1 = fst $ IS.split (succ l1) is
is3 = snd $ IS.split r is
is123 = IS.union is1 is3
IS.size は $O(n)$ だが、一度数えたものは（$\ell$以外）消されるため、全体で$O(N+Q)$で済む。
イベントソートによる方法
別解 by nyoguta で説明されているもの。
時系列の情報は配列で、現在使える重みは多重集合で表現した。
import Data.Array
import qualified Data.IntMap as IM
abc364f :: Int -> Int -> [[Int]] -> Int
abc364f n _q lrcs = loop c0 1 emptyMIS
where
c0 = sum [c | _:_:c:_ <- lrcs]
events = accumArray (flip (:)) [] (1, n) $
concat [[(l, c), (r, - c)] | l:r:c:_ <- lrcs, l /= r]
loop !acc i ws
| i == n = acc -- Nまでたどり着いたら成功
| otherwise =
case lookupminMIS ws1 of
Nothing -> -1 -- 次に張る辺がないならアウト
Just w -> loop (acc + w) (succ i) ws1
where
ws1 = foldl' step ws (events ! i)
step s c
| c < 0 = deleteMIS (- c) s
| otherwise = insertMIS c s
type MultiIntSet = IM.IntMap Int
-- 多重集合の実装略
提出したもの
時刻の幅が広いときは Array でなく IntMap を使うべき。そうした版
区間で使える辺の最安コストを[Maybe Int] で求めておいて、sequence で Maybe [Int] にひっくり返すところが気に入っている。
フレンズさんのヒントの「クリーク」は筆が滑ってしまっているような。
G - Last Major City
シグネチャを決める。
abc364g :: [Int] -- N,M,K
-> [[Int]] -- Ai,Bi,Ci
-> [Int] -- 答え
ABC395Gから
https://x.com/climpet/status/1895832199934722384
G、ABC364GをN回繰り返すだけで間に合う
で流れてきた。
フレンズさんいわく
このスライドが詳しいのだ！
https://www.slideshare.net/wata_orz/ss-12131479
p.50～53で言及されてはいるけど、これだけでは何とも。
https://x.com/terry_u16/status/1817194293725188325
とりあえずwataさんの爆速最小シュタイナー木ライブラリを見に行って
→
https://x.com/wata_orz/status/1667842772861333504
シュタイナー木の厳密最適解を爆速で求めるライブラリです
https://github.com/wata-orz/steiner_tree
どれを読んでもなかなか理解し難い話だったけれど、ABC395GのPythonコード例で何となく理解した。
グラフ中の特定のノード群（これをターミナルと呼ぶ）を連結にする最も安い辺のコスト合計を求めたい。
動的計画法で、ターミナルのノード集合を特定の頂点 $v$ とそれ以外の集合 $X$ に分けて $\textit{Cost}[X][v]$ の形で求める。
（なのでこの問題では $X = {1,\dots,K-1}, v = i$ とできて座りがよい。）
$K \leq 10$ と小さいので、$X$ は集合のビット表現を用いて表せるので、$\textit{Cost}[X][v]$ は整数添え字の配列で表現する。
- $|X| = 0$ の場合、$\textit{Cost}[\emptyset][v] = 0$ である。
- $|X| > 0$ の場合、2段階の計算を行う。
- 分割ステップ：$X$ を真に2分割するあらゆるやり方 $(Z,W)$ s.t. $X = Z \cup W, Z \cap W = \emptyset$ について
$C_1[v] = \min_{Z,W} (\textit{Cost}[Z][v] + \textit{Cost}[W][v])$ - 分配ステップ：グラフにノード0を追加し、$C_{0,v} = C_1[v]$ という辺を追加したグラフにおける、ノード0から各ノード$v$への距離 $d[v]$ をダイクストラ法で求める。
- $\textit{Cost}[X][v] = d[v]$ となる。
- 分割ステップ：$X$ を真に2分割するあらゆるやり方 $(Z,W)$ s.t. $X = Z \cup W, Z \cap W = \emptyset$ について
- $|X| = 1$ のとき、真の二分割は存在しないので分割ステップが行えないが、代わりに、
- $\textit{Cost}[{u}][u] = 0, \textit{Cost}[{u}][v \neq u] = \infty$ とする。
- 分配ステップは同様に行う。
実装
import Data.Array.UArray
abc364g :: [Int] -> [[Int]] -> [Int]
abc364g [n, _m, k] abcs = ...
where
k1 = pred k
tooBig = div maxBound 4 :: Int
-- グラフ
g :: Array Int [(Int,Int)]
g = accumArray (flip (:)) [] (1,n) $
[(a,(b,c)) | a:b:c:_ <- abcs] ++
[(b,(a,c)) | a:b:c:_ <- abcs]
ノード1～$K-1$にビット0～$K-2$を対応させる。
import Data.Bits
type BitSet = Int
それら全て
core :: BitSet
core = bit k1 - 1
要素数を数える
bsSize :: BitSet -> Int
bsSize bs = popCount bs
最小の番号のノード番号（1始まりに戻る）
theBit :: BitSet ->Int
theBit bs = popCount $ bs .^. pred bs
分割を全て列挙する
先頭は必ず $(X,\emptyset)$
powerIntSet :: BitSet -> [(BitSet,BitSet)]
powerIntSet bs = takeWhile (uncurry (>)) $ loop bs
where
loop x = (x, bs .^. x) : loop (bs .&. pred x)
0からカウントアップすると、$X$に含まれない要素の処理に手間取るが、
カウントダウンと (.&.) によるマスクを使うと、不要な部分を飛ばして効率的に全列挙できる。
$\textit{Cost}[X][v]$ 配列は、二次元配列ではなく、$X$ に関して $v$ が一斉に計算されるため入れ子で作る。
cost :: Array BitSet (UArray Int Int)
cost = listArray (0, core) $ map build [0 .. core]
各要素を求める関数 build
$X$ の要素数が0,1,2以上、により動作が切り替わる。
build :: BitSet -> UArray Int Int
build is =
case bsSize is of
0 -> listArray (1, n) $ repeat 0
1 -> sending $ accumArray (flip const) tooBig (1, n) [(theBit is, 0)]
_ -> sending $ splitting is
分割ステップは、powerIntSet で得られる分割のうち、先頭以外について自己参照した結果を足し合わせる。
splitting :: BitSet -> UArray Int Int
splitting bs = accumArray min tooBig (1, n)
[ (v, c1 + c2)
| (bs1, bs2) <- tail $ powerIntSet bs
, ((v, c1), c2) <- zip (assocs $ cost ! bs1) (elems $ cost ! bs2)]
分配ステップでは、ダイクストラ法を用いて距離を更新する。
sending :: UArray Int Int -> UArray Int Int
sending costbs = runST $ do
arr <- dijkstra (0, n) ef 0
listArray (1, n) . map (min tooBig) . tail <$> getElems arr
where
ef 0 = filter ((tooBig >) . snd) $ assocs costbs
ef a = g ! a
$\textit{Cost}[\{1,\dots,K-1\}][v]$ が求まれば、その $v = K,\dots,N$ の値が答えである。
abc364g [n, _m, k] abcs = drop k1 $ elems $ cost ! core
where
...
なお、Haskellでも551msで終わらせることも可能なようだ。
wata_orz氏の示している枝刈りとか入っているのだろうか…