# ABC376 振り返り
- [AtCoder Beginner Contest 376（Promotion of AtCoder Career Design DAY） - AtCoder](https://atcoder.jp/contests/abc376) (バーチャル参加)
- ABCDE 5完 (1299)
![[スクリーンショット 2024-10-22 18.45.45.png]]
ABC376 本戦は欠席。バーチャル参加でやりました。
5完でした。
- A (灰) ··· 前回飴をもらった時刻を状態として持って、前回からの差が $C$ 以上になった回数を数える
- B (灰) ··· 実装問題。右周り、左回りの二通り $\times$ `L` を動かす `R` を動かす $\times$ 間に一方の手がないかどうか、の $8$ 分岐を丁寧にやる
- C (灰) ··· 大きいおもちゃから貪欲に、十分な大きさの箱を当てていく。multiset 相当使って実装
- D (茶) ··· 頂点 $1$ の隣接頂点から BFS して頂点 $1$ までの最短距離を求める
- E (緑) ··· $(A_i, B_i)$ を $A_i$ の昇順にソートし、$A_i$ を固定してその $A_i$ を最大値とみなし $B_i$ の top K (最小 K 個) を保持しながら計算していく
実装的には 5問中 4問で `mapAccumL` を使いました。
以下、軽く振り返ります。
## [A - Candy Button](https://atcoder.jp/contests/abc376/tasks/abc376_a)
前回飴をもらってから $C$ 秒経過すると飴が貰える。
前回もらったときを状態として、差が $C$ 以上開いた回数を数える。
```haskell
main :: IO ()
main = do
[n, c] <- getInts
ts <- getInts
let (_, res) = mapAccumL f (-10 ^ 18) ts
where
f prev t
| t - prev >= c = (t, 1)
| otherwise = (prev, 0)
print $ sum' res
```
## [B - Hands on Ring (Easy)](https://atcoder.jp/contests/abc376/tasks/abc376_b)
考察は容易いが、実装がややこしい。分岐を丁寧にやる。
`L` と `R` の位置を状態として保持しながら
- `L` と `R` どちらを動かすのか
- 左回りに動かすか、右回りに動かすか
- 道中に反対の手があるか、ないか
をうまく分岐する。
```haskell
main :: IO ()
main = do
[n, q] <- getInts
qs <- replicateM q $ auto @(Char, Int)
let res = mapAccumL f (1, 2) qs
where
f (l, r) ('L', ti)
| ti > l = ((ti, r), bool d (n - d) (inRange (l, ti) r))
| otherwise = ((ti, r), bool d (n - d) (inRange (ti, l) r))
where
d = abs (ti - l)
f (l, r) ('R', ti)
| ti > r = ((l, ti), bool d (n - d) (inRange (r, ti) l))
| otherwise = ((l, ti), bool d (n - d) (inRange (ti, r) l))
where
d = abs (ti - r)
f _ _ = error "Invalid"
print $ sum' $ snd res
```
### 追記
[ABC338 D - Island Tour](https://atcoder.jp/contests/abc338/tasks/abc338_d) などでもやったように、進行方向を常に一方向にする、ということをすれば、もう少し簡単になった。
```haskell
main :: IO ()
main = do
[n, q] <- getInts
qs <- replicateM q $ auto @(Char, Int)
let res = mapAccumL f (1, 2) qs
where
f (l, r) ('L', ti) = ((ti, r), bool d (n - d) (inRange (from, to) r))
where
d = abs (ti - l)
(from, to) = if l < ti then (l, ti) else (ti, l)
f (l, r) ('R', ti)= ((l, ti), bool d (n - d) (inRange (from, to) l))
where
d = abs (ti - r)
(from, to) = if r < ti then (r, ti) else (ti, r)
f _ _ = error "Invalid"
print $ sum' $ snd res
```
## [C - Prepare Another Box](https://atcoder.jp/contests/abc376/tasks/abc376_c)
最後に残したいのはなるべく小さなおもちゃ。
なので、大きなものから貪欲に片付けていく。このとき、必要以上に大きな箱は使わないようにしたい。
$A_i$ を降順にみていき、各 $A_i$ にその時点で残っているベストマッチな $B_i$ を探して当てていく
IntMultiSet を使って実装すると、ベストマッチを探したり、すでに使った $B_i$ 取り除くのも含めて操作が楽。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
bs <- getInts
let (_, res) = mapAccumL f (fromListMS bs) (sortOn' Down as)
where
f s ai = case lookupGEMS ai s of
Just bi -> (deleteMS bi s, Nothing)
Nothing -> (s, Just ai)
res' = catMaybes res
if length res' == 1
then print $ head res'
else print (-1 :: Int)
```
## [D - Cycle](https://atcoder.jp/contests/abc376/tasks/abc376_d)
強連結成分分解··· といきたいところだがそんなもので殴る必要もなく、頂点 $1$ の隣接頂点から一斉に出発して BFS し、$1$ に辿り着くまでの最短経路を割り出せばよい。
閉路になっていなければ $1$ には辿り着けない。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getTuple
let g = graph (1, n) uvs
dist = bfs (g !) (-1) (bounds g) [(x, 1) | x <- g ! 1]
print $ dist ! 1
```
## [E - Max × Sum](https://atcoder.jp/contests/abc376/tasks/abc376_e)
説明するとややこしいのでコードをみるほうがはやそう。
$A_i$ の小さなものから固定していきたい。$(A_i, B_i)$ を $A_i$ の昇順にソートする。
この整列済みの数列を、$A_i$ の小さな方から、$A_i$ を固定していみていく。
固定された $A_i$ が $max \space A_i$ だとすると、数列 $B = (B_1,B_2, \ldots, B_i)$ までの中から $K$ 個が、その $A_i$ にとってベストな部分集合ということになる。
ここに気がつけるかどうかが問われる問題。
あとは実装。最小値 top K 個を管理しながら、集合にどんどん値を追加していくような操作ができれば数列 $B$ の表現が簡単。
これは [ABC281 E - Least Elements](https://atcoder.jp/contests/abc281/tasks/abc281_e) や [ABC306 E - Best Performances](https://atcoder.jp/contests/abc306/tasks/abc306_e) でも題材になった、top K の値とその top K の総和を動的に管理できる集合データ構造を使うと良い。
自分は BalancedMultiSet という名前でライブラリ化している。
これを使えば実装は瞬殺である。
```haskell
main :: IO ()
main = do
t <- getInt
replicateM_ t $ do
[_, k] <- getInts
as <- getInts
bs <- getInts
let (_, res) = mapAccumL f (emptyBMS k LT) $ sortOn fst $ zip as bs
where
f s (a, b) =
let s' = insertBMS b s
in (s', a * leftSum s')
print $ minimum $ drop (k - 1) res
{-- BalancedMultiSet --}
data BalancedMultiSet = BalancedMultiSet
{ topKValue :: Int,
topKOrder :: Ordering,
left :: IntMultiSet,
right :: IntMultiSet,
leftSum :: Int
}
deriving (Show)
emptyBMS :: Int -> Ordering -> BalancedMultiSet
emptyBMS k order =
BalancedMultiSet
{ topKValue = k,
topKOrder = order,
left = emptyMS,
right = emptyMS,
leftSum = 0
}
nullBMS :: BalancedMultiSet -> Bool
nullBMS BalancedMultiSet {..} = nullMS left
singletonBMS :: Int -> Ordering -> Int -> BalancedMultiSet
singletonBMS k order x = insertBMS x (emptyBMS k order)
fromListBMS :: Int -> Ordering -> [Int] -> BalancedMultiSet
fromListBMS k order = foldl' (flip insertBMS) (emptyBMS k order)
insertBMS :: Int -> BalancedMultiSet -> BalancedMultiSet
insertBMS x s@BalancedMultiSet {..}
| sizeMS left < topKValue = balanceBMS (s {left = insertMS x left, leftSum = leftSum + x})
| otherwise = balanceBMS (s {right = insertMS x right})
deleteBMS :: Int -> BalancedMultiSet -> BalancedMultiSet
deleteBMS x s@BalancedMultiSet {left, right, leftSum}
| memberMS x left = balanceBMS (s {left = deleteMS x left, leftSum = leftSum - x})
| otherwise = balanceBMS (s {right = deleteMS x right})
balanceBMS :: BalancedMultiSet -> BalancedMultiSet
balanceBMS s@BalancedMultiSet {..}
| (not . nullMS) right && sizeMS left < topKValue =
balanceBMS
( s
{ left = insertMS q left,
right = deleteMS q right,
leftSum = leftSum + q
}
)
| p `cmp` q = s
| otherwise =
balanceBMS
( s
{ left = insertMS q (deleteMS p left),
right = insertMS p (deleteMS q right),
leftSum = leftSum + q - p
}
)
where
cmp = case topKOrder of
LT -> (<=)
GT -> (>=)
EQ -> error ""
(p, q) = case topKOrder of
LT ->
( bool maxBound (findMaxMS left) (not . nullMS $ left),
bool maxBound (findMinMS right) (not . nullMS $ right)
)
GT ->
( bool minBound (findMinMS left) (not . nullMS $ left),
bool minBound (findMaxMS right) (not . nullMS $ right)
)
EQ -> error "Unsupported ordering"
```