# ABC431 振り返り
- [TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431) - AtCoder](https://atcoder.jp/contests/abc431)
- ABCDE 5完 (1556) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc431)
![[スクリーンショット 2025-11-09 10.18.48.png]]
ABC431 でした。
DIfficulty 1424 の問題を 60分程度で解いて 5完、パフォーマンスは 1556 と上出来でした。
- A (灰, 10) ··· `max 0 (h - b)`
- B (灰, 36) ··· その時点でどの部品が使われてるか集合管理しながら、都度重さに写像して総和をとる
- C (灰, 172) ··· 貪欲。$H_i$ を昇順にみていき、$H_i$ にぎりぎり適合する $B_i$ を探す。$B_i$ を MultiSet で管理した
- D (茶, 693) ··· 頭に使った重さ、体使った重さの差を状態にして DP
- E (水, 1424) ··· 01-BFS
E は実装が大変だった、という話を方々で見かけましたが Haskell で実装する場合それほどでもなかったです。
D の DP や E の 01-BFS ともに、いずれも自分が盆栽していた抽象がうまく問題を吸収してくれた感じです。Haskell の力を活かせて、とても満足度が高いです。
## [A - Robot Balance](https://atcoder.jp/contests/abc431/tasks/abc431_a)
これはやるだけです。
```haskell
main :: IO ()
main = do
[h, b] <- getInts
print $ max 0 (h - b)
```
## [B - Robot Weight](https://atcoder.jp/contests/abc431/tasks/abc431_b)
IntSet でその時点で装着している部品番号を集合管理。
その上で毎回、部品番号を重さに写像して総和を得る。制約的に計算量には気を遣う必要はないです。
```haskell
main :: IO ()
main = do
x <- getInt
n <- getInt
ws <- getIntArray (1, n)
q <- getInt
qs <- replicateM q getInt
foldForM_ IS.empty qs $ \s qi -> do
let s'
| IS.member qi s = IS.delete qi s
| otherwise = IS.insert qi s
total = sum' [ws ! i | i <- IS.toList s']
print $ x + total
return s'
```
## [C - Robot Factory](https://atcoder.jp/contests/abc431/tasks/abc431_c)
同じような問題を良く見ます。貪欲法で OK
小さな頭のパーツに、条件を満たすうちなるべく小さな体のパーツをペアにしていくと最適になる。
というわけで体のパーツ $B_i$ を多重集合で管理して、$H_i$ を昇順にみていきつつ、各 $H_i$ に最も最適なパーツを `lookupGE` で探す。
これを繰り返して、ペアを作れた数を数えれば答えになる。
```haskell
main :: IO ()
main = do
[_, _, k] <- getInts
hs <- getInts
bs <- getInts
let b0 = fromListMS bs
(_, res) = mapAccumL f b0 $ sort' hs
where
f s h = case lookupGEMS h s of
Just x -> (deleteMS x s, Just x)
Nothing -> (s, Nothing)
ans = length (catMaybes res)
printYn $ ans >= k
```
## [D - Robot Customize](https://atcoder.jp/contests/abc431/tasks/abc431_d)
各部品を頭に使うか、体に使うかを全部試す･･･となると DP です。
DP の状態をどう取るか。ナイーブに考えると (頭の重さの総和, 体の重さの操作) という二つのパラメータを状態するのがすぐ思いつきます。
が、それだと最大で (25000, 25000) が上界になって状態空間が大きくなりすぎる。
(実際、それで送信したら MLE になりました 😅)
頭の重さの総和と、体の重さの総和の差が管理できればいいというところに着目すると、状態空間をもう少し狭くすることができます。
具体的には、頭に部品を使ったときは $-W_i$ を加算し、体に部品を使ったときは $+W_i$ を加算する。その総和を状態とする。
こうすることで、最終的に総和が $0$ 以上であれば頭の方が軽い状態であると言える。
というわけで、状態空間を入力の $W_i$ の総和 $\sum{W_i}$ を用いて $(-\sum{W_i}, \sum{W_i})$ として、先の要領で DP すれば OK です。
DP の実装はいつもの `accumArrayDP` で。状態空間を `(-wMax, wMax)` 宣言してあとは状態遷移を記述するのみ。
どうやらこの問題は制約がきつく命令型言語ではいわゆる NDP と呼ばれるテクニックが必要だったようですが、 `accumArrayDP` は前回の状態空間から次の状態空間への畳み込みとして実装しており、NDP 相当の空間効率でであるため問題なしでした。
```haskell
main :: IO ()
main = do
n <- getInt
items <- replicateM n getTuple3
let wMax = sum' (map fst3 items)
let dp = accumArrayDP @UArray f max minBound (-wMax, wMax) [(0, 0 :: Int)] items
where
f (w, acc) (wi, hi, bi)
| acc == minBound = []
| otherwise = [(w - wi, acc + hi), (w + wi, acc + bi)]
print $ maximum [acc | (w, acc) <- assocs dp, w >= 0]
```
## [E - Reflection on Grid](https://atcoder.jp/contests/abc431/tasks/abc431_e)
結論、01-BFS で解きます。
$(1, 1)$ から $(H, W)$ までの経路に着目する問題で、一見 BFS で探索問題のようにも見えますが、問題になっているのは経路数ではなく途中の経路で鏡の置き方を変更した回数です。
グリッドなどを探索しながら途中で何かしら特殊行動を取った回数を求める、というのは 01-BFS の典型なので、そのあたりからピンときました。
問題は 01-BFS で答えが最適になるかどうか?
一度通ったマスに再度戻ってきて経路を変更する、というような行動を取った方が最適になる場合があるとしたら 01-BFS では駄目です。
が、軽くシミュレーションしてみてもそのようなケースはすぐに思いつかなかったので、01-BFS で実装してみてサンプルが合うならそれで行ってみようという方針で進めました。
この問題は光の進む方向を扱うので、BFS の状態空間として (マスの座標, 方向) を定義します。
その上で状態遷移時に方向を考慮します。マス $v$ 置かれた鏡に従って進入方向から進行方向が変わる場合はコスト $0$ 、鏡を置き換える即ち任意の方向に進めるならコスト $1$ がかかるよう実装します。
Haskell なら 01-BFS の抽象も、状態空間に任意の構造を取ることができます。
方向は `data LRUD` と型として宣言し、扱います。
あとは素直に実装するだけ。
なお、この問題ではゴールが $(H, W)$ に到達すればそれでよし、ではなく $(H, W)$ に到達したあと右を向いている必要があります。
ので、 01-BFS が終わったあと $(H, W)$ マスから右を向くために追加の操作が 1 回必要になるかどうかを最後に計算して、辻褄を合わせています。
実装が大変だった、という声が散見されましたが Haskell の抽象度なら割と楽に実装することができて、実装が楽しい問題でした。
```haskell
data LRUD = L | R | U | D deriving (Show, Eq, Ord, Ix, Enum)
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)]
fromLRUD d = case d of
L -> left
R -> right
U -> up
D -> down
move c d = case c of
'A' -> d
'B' -> case d of
L -> U
U -> L
R -> D
D -> R
'C' -> case d of
L -> D
D -> L
R -> U
U -> R
_ -> error "!?"
main :: IO ()
main = do
t <- getInt
replicateM_ t $ do
[h, w] <- getInts
grid <- getCharGrid ((1, 1), (h, w))
let dist = bfs01 f (((1, 1), L), ((h, w), D)) [(((1, 1), R), 0)]
where
f (v, d) =
[ ((u, d'), 0)
| let d' = move (grid ! v) d
u = v + fromLRUD d',
inRange (bounds grid) u
]
++ [ ((u, d'), 1)
| d' <- [L .. D],
let u = v + fromLRUD d',
inRange (bounds grid) u
]
ans =
minimum
[ dist ! ((h, w), d) + bool 1 0 (move (grid ! (h, w)) d == R)
| d <- [L, R, U, D]
]
print ans
```
## [F - Almost Sorted 2](https://atcoder.jp/contests/abc431/tasks/abc431_f) (🍊未完)
挿入DP ? なんですかそれ