# ABC437
- [UNIQUE VISION Programming Contest 2025 Christmas (AtCoder Beginner Contest 437) - AtCoder](https://atcoder.jp/contests/abc437)
- ABCDF 5完 (1410) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc437)
![[スクリーンショット 2025-12-22 11.55.33.png]]
ABC437 でした。
- A (灰) ··· 素直に計算する
- B (灰) ··· ナイーブに実装して構わない
- C (茶) ··· 力 $P_i$ の総和をまず考えて、そこから貪欲にトナカイを一匹ずつソリに乗せるのに転換させることを考える
- D (茶) ··· $A_i$ を固定して二分探索、累積和。絶対値は正の場合と負の場合で場合分け
- E (水, upsolve) ··· グラフ (木) に見立てて DFS する。同じ階層のノードで遷移コストが同じ場合をグルーピングする DFS
- F (水) ··· 区間 max セグメント木を 4本用意して $X +Y, X - Y, - X + Y, - X- Y$ を管理する
E でトライ木を構築しようとして沼り、飛ばして F を解きました。
かろうじて F が解けてパフォーマンス 1410 。だんだん、青パフォ前後を出さないといけない領域になってきました。
## [A - Feet](https://atcoder.jp/contests/abc437/tasks/abc437_a)
素直に計算するだけで OK です。
```haskell
main :: IO ()
main = do
[a, b] <- getInts
print $ a * 12 + b
```
## [B - Tombola](https://atcoder.jp/contests/abc437/tasks/abc437_b)
制約がとても小さいのでナイーブに実装してよいでしょう。
```haskell
main :: IO ()
main = do
[h, w, n] <- getInts
rows <- replicateM h getInts
bs <- replicateM n getInt
let res = [countBy (`elem` bs) row | row <- rows]
print $ maximum res
```
## [C - Reindeer and Sleigh 2](https://atcoder.jp/contests/abc437/tasks/abc437_c)
一見すると、各アイテムごとに二つある行動のいずれかを取ったときの最適化なので DP のようにも見えます。
しかし制約的に DP を回せそうにありません。
発想を切り替え、貪欲法で考えます。
このとき余事象っぽく考えるとよいです。
全トナカイにソリを引かせた場合 $P_i$ の総和 $totalP$ だけの力が集まります。
そこから、一匹ずつ、ソリを引かせるのではなく乗せるほうに切り替えていったとします。
ある一匹が乗る方に切り替わった場合、$totalP$ から、その一匹分の力が引かれます。そしてその一匹分の重さが増えます。
そしてこの問題では、ソリを引く力 $P$ と、重さの $W$ は 1 : 1 の等価交換が成立しているので、トナカイ一匹を乗る方に転換させたときのコストは $P_i + W_i$ と計算できます。
というわけで各トナカイのコストを計算しそれを昇順にソートして、貪欲に先頭からコストの総和が $totalP$ を超えないところまで選べば OK です。
選ぶことができたトナカイの匹数が答えです。
「DP じゃ無理っぽいし、2値を一つの値に集約した値に比較の意味を持たせられるか?」と考えて、この解法に行き着きました。
```haskell
main :: IO ()
main = do
t <- getInt
replicateM_ t $ do
n <- getInt
vs <- replicateM n getTuple
let total = sum' (map snd vs)
costs = sort' $ map (uncurry (+)) vs
res = takeWhile (<= total) $ scanl1 (+) costs
print $ length res
```
## [D - Sum of Differences](https://atcoder.jp/contests/abc437/tasks/abc437_d)
ザ・茶diff 典型問題という感じですね。
まず $B$ を昇順にソートする。こういう、並び順に意味がない問題はまずソートしてしまえ、というのが定石。
その上で $A$ を固定し、各 $A_i$ の寄与数を考えていく。
ここで絶対値をどうにかしたいから、$B$ に $A_i$ の大小の境界線を引く。
すると境界の左側では $A_i \leq B$ となるから $|A_i - B_i|$ の絶対値は外れる。
境界の右側では $A_i > B$ となり $A_i - B < 0$ となるから、絶対値を外すのに $-1$ を掛ける。
これを利用する。
具体的には $A_i = 6$ で、 $B = (1, 3, 5, 7, 10)$ だとする
$|6 - 1| → 6 -1 = 5$
$|6 - 3| → 6 - 3 = 3$
$|6 -5| → 6 - 5 = 1$
(ここに境界)
$|6 - 7| → - (6 - 7)= 1$
$|6 - 10| → - (6 - 10) = 4$
となる。
前半は $6 \times 3 - (1 + 3 + 5)$
後半は $-6 \times 2 + (7 + 10)$
と整理できる。$6 \times 3$ や $-6 \times 2$ の $3$ や $2$ は二分探索によって境界前後に値が何個あるか数えることで求められる。
$(1 +3 + 5)$ や $(7 + 10)$ は区間和なので、累積和で求められる。
これを実装します。
$A_i$ を固定すると $A_i + B_1$ + $A_i + B_2 + \cdots + A_i + B_M$ となり、同じ $A_i$ が何度もでてくるし、式を整理すると $B_1 + B_2 + \cdots + B_M$ が出てくる。
このあたりから、累積和や二分探索での数え上げ、みたいな典型だと判断しました。あとは絶対値は、正の場合と負の場合で場合分けで外せる、という知識。
```haskell
main :: IO ()
main = do
[_, m] <- getInts
as <- getInts
bs <- getInts
let bs' = sort' bs
ba = listArray @UArray (0, m - 1) bs'
s = listArray @UArray (0, m) $ scanl' (+) 0 bs'
res =
[ a' * k' - a' * (m' - k') - l' + r'
| a <- as,
let k = countInRange (0, a) ba
l = s ! k
r = s ! m - s ! k
[a', k', m', l', r'] = map toIntMod [a, k, m, l, r]
]
IntMod ans = sum' res
print ans
```
## [E - Sort Arrays](https://atcoder.jp/contests/abc437/tasks/abc437_e) (upsolve)
静的にトライ木を構築するのではなくて、トライ木かのように DFS する、という実装にすればシンプルでした。
まず、グラフで考えます。ここを思いつけるかどうかが最初の関門だと思います。
ある $x_i$ の後ろにしか次の値をつけられない、というので「依存関係」の匂いがする。依存関係ときたら有向グラフ･･･という思考順序でグラフで考えることを思いつきました。
このとき、数列の番号が頂点番号になります。そして $y_i$ は辺の重みだと考えれば良いでしょう。
この発想でグラフを構築すると、以下のようなグラフができあがります。入力例1 のサンプルに二つほどノードを追加したグラフです。
さて、求められているのは辞書順。辞書順は前から貪欲に考えていけばいい、というのが良くしられた事実。
そこで頂点 $0$ から辺の重みが小さいものを優先する DFS をしてみます。
これでうまくいきそうですが、実際には木の同じ高さに同じ辺の重みの頂点がいた場合、それらは並行、つまり幅優先的に探索しないといけません。
![[スクリーンショット 2025-12-22 15.22.19.png|1024]]
つまり、同じ木の高さで重みが一緒のものはグルーピングする、ということになります。
これに従ってグルーピングすると以下のようなグラフの構造になります。
![[スクリーンショット 2025-12-22 15.22.25.png|400]]
これはトライ木っぽい木です。
というわけでトライ木を構築して、それを DFS するということを考えました。
しかしこの発想がだめで、静的にトライ木を構築しようとすると実装が沼ってしまい、またイミュータブルな実装では TLE しました。
そうではなく toyboot さんの提出を参考に、トライ木を事前に構築するのではなく DFS で木を辿りながら同じ階層で同じコストの頂点を都度グルーピングしつつ、そのグループ単位で再帰呼び出しをする DFS をすると、うまくいきました。
構造的にはトライ木だと思うんですが、明示的にはトライ木を実装しない。
「DFS しながら動的にグルーピングをして一部で幅優先的な探索を行う」という実装です。
トライ木、というのに頭を縛られるとこの発想にならないですね。典型に当てはめて解いてやろうというのが裏目に出ます。
そうはなく「再帰を調整して、DFS での訪問順をうまくコントロールする」というサボらない思考がむしろシンプルな実装に必要でした。
```haskell
dfs' acc g vs
| null vs = return ()
| otherwise = do
for_ (groupOn snd vs) $ \vs' -> do
modifyRef' acc (vs' :)
let us = sortOn swap $ concatMap (g !) (map fst vs')
dfs' acc g us
main :: IO ()
main = do
n <- getInt
xs <- replicateM n getTuple
let uvs = [((x, i), y) | (i, (x, y)) <- indexed 1 xs]
g = amap (sortOn swap) $ wGraph (0, n) uvs
acc <- newIORef []
dfs' acc g (g ! 0)
res <- map fst . concat . reverse <
gt; readIORef acc
printList res
```
## [F - Manhattan Christmas Tree 2](https://atcoder.jp/contests/abc437/tasks/abc437_f)
二つの座標 $(X, Y)$ と $(x, y)$ のマンハッタン距離は
$∣X−x∣+∣Y−y∣=max((X+Y)−(x+y),(X−Y)−(x−y),(−X+Y)−(−x+y),(−X−Y)−(−x−y))$
と表せることが良く知られています。
特に難しい理論が必要なわけではなく、絶対値が二つあるのでそれの正負の組みせで展開するとこうなります。
みやすくすると
$|X - x| + |Y - y|$ は
- $(X + Y) - (x + y)$
- $(X - Y) - (x - y)$
- $(-X + Y) - (-x + y)$
- $(- X - Y) - (-x - y)$
のいずれかの最大値になる、ということですね。
この問題で求められているのは座標番号の $L, R$ 間の区間和でにおける最大値。セグメント木の匂いがします。
上の式を考えると $X + Y, X - Y, -X + Y, -X - Y$ の4つの値に対応する区間 max セグメント木を 4本作って管理すれば、計算できることがわかります。
というわけでこれを実装。
マンハッタン距離の展開の方法さえわかっていれば、簡単な問題でした。
マンハッタン距離にはほかにも色々面白い性質がありますね。
```haskell
main :: IO ()
main = do
[n, q] <- getInts
vs <- replicateM n getTuple
qs <- replicateM q getInts
seg1 <- newST @IOUArray max (minBound :: Int) (1, n) -- X + Y
seg2 <- newST @IOUArray max (minBound :: Int) (1, n) -- X - Y
seg3 <- newST @IOUArray max (minBound :: Int) (1, n) -- -X + Y
seg4 <- newST @IOUArray max (minBound :: Int) (1, n) -- -X - Y
--
for_ (indexed 1 vs) $ \(i, (x, y)) -> do
updateST seg1 i (const (x + y))
updateST seg2 i (const (x - y))
updateST seg3 i (const (-x + y))
updateST seg4 i (const (-x - y))
for_ qs $ \case
[1, i, x, y] -> do
updateST seg1 i (const (x + y))
updateST seg2 i (const (x - y))
updateST seg3 i (const (-x + y))
updateST seg4 i (const (-x - y))
[2, l, r, x, y] -> do
v1 <- rangeQueryST seg1 l (r + 1)
v2 <- rangeQueryST seg2 l (r + 1)
v3 <- rangeQueryST seg3 l (r + 1)
v4 <- rangeQueryST seg4 l (r + 1)
let v1' = v1 - (x + y)
v2' = v2 - (x - y)
v3' = v3 - (-x + y)
v4' = v4 - (-x - y)
print $ maximum [v1', v2', v3', v4']
_ -> error "Invalid Query"
```