# ABC410 振り返り
- [AtCoder Beginner Contest 410 - AtCoder](https://atcoder.jp/contests/abc410)
ABC410 は不参加だったので、後日解きました。D が解けず、upsolve しました。
- A (灰) ··· $K$ 以上の値の数を数える
- B (灰) ··· 制約的に、最小の値が入っているインデックスを線形探索してよい
- C (灰) ··· $((P - 1) + offset) \bmod N$ で狙いのインデックス位置を特定する。この $offset$ を状態にしてシミュレーション。
- D (緑, upsolve) ··· 制約から重みの値の下界、上界は $(0, 1023)$ になる。ので状態空間を、例えば頂点 $1$ に対して $(1, 0), (1, 1) \cdots (1, 1023)$ のように二次元に拡張し BFS する
- E (緑) ··· DP。$(H, M) → (0, 0)$ へ向かう DAG になるはずなので、蛙跳び DP で解ける。C++ 変換が必要だった
## [A - G1](https://atcoder.jp/contests/abc410/tasks/abc410_a)
やる
```haskell
main :: IO ()
main = do
_ <- getInt
as <- getInts
k <- getInt
print $ countBy (>= k) as
```
## [B - Reverse Proxy](https://atcoder.jp/contests/abc410/tasks/abc410_b)
最小値のインデックスをみつける、というのをどうしようかと思いましたが、制約的に線形探索で問題なし
```haskell
main :: IO ()
main = do
[n, q] <- getInts
xs <- getInts
as <- newArray @IOUArray (1, n) (0 :: Int)
res <- for xs $ \x -> do
case x of
0 -> do
as' <- getElems as
let (i, _) = minimumOn snd (indexed 1 as')
modifyArray as i succ
return i
xi -> do
modifyArray as xi succ
return xi
printList res
```
## [C - Rotatable Array](https://atcoder.jp/contests/abc410/tasks/abc410_c)
操作は回転操作なので、周期性があります。
$\bmod N$ でインデックス位置を特定するのを前提に、操作回数をオフセットとみたてて、それを状態にシミュレーションすれば OK です。
```haskell
main :: IO ()
main = do
[n, q] <- getInts
qs <- replicateM q getInts
as <- newListArray @IOUArray (0, n - 1) [1 .. n]
foldForM_ (0 :: Int) qs $ \acc query -> do
case query of
[1, p, x] -> do
writeArray as (((p - 1) + acc) `mod` n) x
return acc
[2, p] -> do
print =<< readArray as (((p - 1) + acc) `mod` n)
return acc
[3, k] -> return $ (acc + k) `mod` n
_ -> undefined
```
## [D - XOR Shortest Walk](https://atcoder.jp/contests/abc410/tasks/abc410_d) (upsolve)
制約から重みの値の下界、上界は $(0, 1023)$ になる。
ので状態空間を、例えば頂点 $1$ に対して $(1, 0), (1, 1) \cdots (1, 1023)$ のように二次元に拡張して辺を張り、BFS します。
頂点倍化までは思いついたものの、各頂点を $0$ の世界の頂点と $1$ の世界に頂点分けて遷移を辺で表す、とかやったのですがうまくいかず、断念。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getWeightedEdge
let uvs' = [((u, s), (v, s `xor` w)) | ((u, v), w) <- uvs, s <- [0 .. 1023]]
g = wGraph ((1, 0), (n, 1023)) $ map (,1 :: Int) uvs'
dist = bfs' (g !) (+) (-1) (bounds g) [((1, 0), 0)]
print $ minimumDef (-1) [s | s <- [0 .. 1023], dist ! (n, s) /= -1]
```
## [E - Battles in a Row](https://atcoder.jp/contests/abc410/tasks/abc410_e)
$(H, M)$ という二次元の状態を考えればよいのはすぐに思いつきます。
最初はダイクストラ法を使いましたが、TLE が取れず。
遷移は $(H, M) → (0, 0)$ に必ず向かっているので、いわゆる蛙跳び DP の計算構造で解けます。
少し変わっているのは、DP の値に「何体倒したかの最大値」を入れているわけですが、その値から次に倒すモンスターのインデックス $i$ を定めているところ。
この問題はモンスターは順番にしか倒せないのと、倒す以外に選択肢がないので、これでいけます。
Haskell で、自分の拙作ライブラリ linearDP だと TLE、linearDP' だと MLE したので C++ に変換して AC しました。
空間が $3000 \times 3000 = 9,000,000$ と大きいので、ちょっとサンクが溜まるだけで MLE してしまうようです。
```haskell
main :: IO ()
main = do
[n, h, m] <- getInts
xs <- replicateM n getTuple
let xa = listArray @Array (0, n - 1) xs
let dp = linearDP' f max (minBound :: Int) ((0, 0), (h, m)) [((h, m), 0)] $ reverse (range ((0, 0), (h, m)))
where
f (hi, mi) i
| i == minBound = []
| i == n = []
| otherwise =
let (ai, bi) = xa ! i
in case (hi >= ai, mi >= bi) of
(True, True) -> [((hi - ai, mi), i + 1), ((hi, mi - bi), i + 1)]
(True, False) -> [((hi - ai, mi), i + 1)]
(False, True) -> [((hi, mi - bi), i + 1)]
(False, False) -> []
print $ maximum (elems dp)
```
公式解説の通りに解くならこうですかね。
こちらなら畳み込み DP で解けるし、空間も $(0, 3000)$ 程度の空間しか確保せずに済むため、効率も良いです。
```haskell
main :: IO ()
main = do
[n, h, m] <- getInts
xs <- replicateM n getTuple
let dps = accumArrayDP' @UArray f max minBound (0, m) [(m, h)] xs
where
f (mi, acc) (ai, bi)
| acc == minBound = []
| otherwise = [(mi - bi, acc), (mi, acc - ai)]
ans = pred . length $ takeWhile (any (>= 0) . elems) dps
print ans
-- 畳み込みDP の scanl' バージョン
accumArrayDP' ::
( IArray a e,
Ix v,
Eq e,
Show v,
Show e
) =>
((v, e) -> t -> [(v, e')]) -> -- 状態遷移関数 f v / x をみて v の次の遷移可能性を返す
(e -> e' -> e) -> -- 緩和の二項演算
e -> -- 初期値 (0, minBound, maxBound, False など)
(v, v) -> -- 状態空間の下界、上界
[(v, e')] -> -- 開始時点の状態
[t] -> -- 入力 (時間遷移)
[a v e] -- [Array] or [UArray]
accumArrayDP' f op initial (l, u) v0s xs = do
let dp = accumArray op initial (l, u) v0s
scanl' transition dp xs
where
transition dp x =
accumArray op initial (l, u)
$ filter (inRange (bounds dp) . fst)
$ concatMap (`f` x) (assocs dp)
where
!_ = dbg ("dp", filter ((/= initial) . snd) $ assocs dp)
```