# ABC390 振り返り
- [AtCoder Beginner Contest 390 - AtCoder](https://atcoder.jp/contests/abc390)
- ABC 3完 (1133) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc390)
![[スクリーンショット 2025-01-27 9.39.06.png]]
ABC390 でした。
D を bit DP で頑張りましたが、答えはあうものの TLE がどうしても取れず負け。
D は青 diff だったので 3完でもパフォーマンスは横ばいに留まりました。が、灰色 diff を解くために精進しているわけではない! という気持ちで不完全燃焼です。
- A (灰, 43) ··· 実際に swap させてソート済みになるか調べる
- B (灰, 147) ··· Rational 型で比を比較する
- C (灰, 247) ··· 矩形の左上と右下を特定し、全探索
- D (青, 1607, upsolve) ··· グループ分けパターンを全列挙。Haskell だと Set や IntSet を使うと負け
- E (水, 1227, upsolve) ··· ビタミンごとに DP して、工夫して $O(X)$ で全探索
## [A - 12435](https://atcoder.jp/contests/abc390/tasks/abc390_a)
他に簡単な方法もあるかな? と思いつつ実際にスワップを全部試しました。
```haskell
main :: IO ()
main = do
as <- getIntArray (1, 5)
let res = [sorted (elems as') | i <- [1 .. 4], let as' = swapIArray as i (i + 1)]
printYn $ or res
```
## [B - Geometric Sequence](https://atcoder.jp/contests/abc390/tasks/abc390_b)
本番では他の方法で実装しましたが、Haskell なら Rational 型で $A_{i + 1} / A_i$ が一定かを調べるのが楽です。
```haskell
main :: IO ()
main = do
_ <- getInt
as <- getInts
let as' :: [Rational]
as' = map fromIntegral as
printYn $ allSame (zipWith (/) (tail as') as')
```
## [C - Paint to make a rectangle](https://atcoder.jp/contests/abc390/tasks/abc390_c)
盤面は $1000 \times 1000$ ということもあり、線形探索ならできそう。
矩形の左上と右下がわかれば全マス探索することができる。
$x$ 軸と $y$ 軸を別々に考えて `#` のマスが置かれている最小と最大をそれぞれ求めることで左上、右下がわかります。
それが分かったら、あとは全探索して `.` がないことを確認すれば OK
```haskell
main :: IO ()
main = do
[h, w] <- getInts
grid <- getCharGrid ((1, 1), (h, w))
let vs = findArrayIndices (== '#') grid
(xs, ys) = unzip vs
s = (minimum xs, minimum ys)
t = (maximum xs, maximum ys)
res = or [grid ! v == '.' | v <- range (s, t)]
printYn $ not res
```
## [D - Stone XOR](https://atcoder.jp/contests/abc390/tasks/abc390_d) (upsolve)
本番ではグルーピングの bit DP で頑張りましたが、最終的にできあがった $B_1 \oplus B_2 \oplus \ldots \oplus B_N$ の値をすべて保持するのに Set や IntSet を使わざるを得ず、そこの union 操作が重くて TLE を脱出できず。
この問題は bit DP ではなく、グループを全列挙するほうが定数倍が軽く済みます。
敗因は二つありました。
- ベル数 $B(N)$ と計算量の見積もり方がわかっていなかったこと
- Haskell の Set や IntSet が重く、$4 \times 10^6$ 個くらいになってくると時間がかかりすぎること
前者に関して。
今回の問題は $N \leq 12$ ですが、この場合のベル数 $B(N)$ は $4 \times 10^6$ 程度で、グループのパターンを全列挙することが可能です。
$N \leq 15$ とかになってくると全列挙が難しくなるため、必然的に bit DP など部分問題重複性を使う問題だとメタ読みすることができます。
が、$N \leq 12$ 程度ならむしろグループを全列挙する方がシンプルで、考察や実装も楽です。
グルーピング問題が $N$ 幾つまで全列挙でいけるのか整理できてなかったため、bit DP 回答にこだわってしまいました。
2点目、グループを全列挙して問題文の通りに部分和を $XOR$ で畳み込んだとして、その畳み込まれた値のユニークを取るために Set や IntSet を使うと TLE します。
てっきりグループ全列挙のほうが遅いのだと思い込んでいましたが、いろいろデバッグしてみたところ Set が遅かった。
Data.List.Extra の `nubOrd` も内部では Set を使っているので、やはりこの規模になると遅い。
`nubOrd'` として、Vector のイントロソートを使ってユニークを取る実装に差し換えたところボトルネックが解消されて AC できました。
値のユニークをとる実装でここまで差がつくと思っておらず、完全に盲点でした。
公式解説では DFS で、累積和や XOR を命令型データ構造 (短命データ構造) を書き換えながら計算していく実装が紹介されていますが、正直複雑だと思います。
以下のようにグループの全パターンをリストで全列挙してから、問題文の通り素直に部分和と XOR を取るほうが認知負荷はずっと下がると思いました。
Set が遅くて Haskell 最悪だなーと思いましたが、全列挙してから普通に計算すればいいのは Haskell 最高だなと思いました。
グルーピング関数はもともと持っていたので、高速なユニークをとる関数さえあれば瞬殺の問題でしたが、そこが原因だと気がつくことができず敗北しました。
```haskell
main :: IO ()
main = do
_ <- getInt
as <- getInts
let res = [foldl1' xor [sum' xs | xs <- gs] | gs <- groupPartitions as]
print $ length (nubOrd' res)
groupPartitions :: [a] -> [[[a]]]
groupPartitions [] = [[]]
groupPartitions (x : xs) =
concatMap f (groupPartitions xs)
where
f ps = ([x] : ps) : [let (front, g : back) = splitAt i ps in front ++ ((x : g) : back) | i <- [0 .. length ps - 1]]
nubOrd' :: (VUM.Unbox a, Ord a) => [a] -> [a]
nubOrd' xs = (VU.toList . VU.uniq . VU.modify (VAI.sortBy compare) . VU.fromList) xs
```
## [E - Vitamin Balance](https://atcoder.jp/contests/abc390/tasks/abc390_e) (upsolve)
D 問題にかかりきになって、 E は問題文をみることすらせず。
まず、この問題では各アイテムごとに特定のビタミンしか増加しない。どれか一つを選ぶと二つ同時に増加したりはしない。
なので、各ビタミンごとに、カロリーが $0 .. X$ まで「選ぶ・選ばない」で最大化するビタミン量を計算することができます。
各ビタミンごとのカロリー値を $(i, j, k)$ としたとき $i + j + k \leq X$ で $(dp1[i], dp2[j], dp3[k])$ を求めて、この三値の最小値を求める。それらの最大値が答えになる。
ただし $i + j + k \leq X$ をナイーブにやると $O(X^3)$ になってしまう。
が $X$ 回、3 つの値のうち最小だったやつのカウンタを $+1$ 進めるというやりかたで $O(X)$ で計算が可能。
二つ以上最小があるときは、最小のやつのどれでもいいからカウントアップ。ここがなかなか思いつかないですね。
(ただしその過程で minBound を踏むこともあるので必ずしも $i + j + k = X$ が正しいわけではなくて、その過程で見つけた値の中のどれかに答えがある。)
DP + 「工夫して全探索」の類なのかなあ、と思いました。
```haskell
main :: IO ()
main = do
[n, x] <- getInts
items <- replicateM n getTuple3
let dp i = accumDP @Array f max minBound (0, x) [(0, 0)] items
where
f (s, acc) (vi, ai, ci)
| acc == minBound = []
| otherwise = [(s + ci, if vi == i then acc + ai else acc)]
dp1 = dp 1
dp2 = dp 2
dp3 = dp 3
res = take (x + 1) $ iterate f (0, 0, 0)
where
f (i, j, k)
| a <= b && a <= c = (i + 1, j, k)
| b <= a && b <= c = (i, j + 1, k)
| otherwise = (i, j, k + 1)
where
a = dp1 ! i
b = dp2 ! j
c = dp3 ! k
res' = maximum [ans | (i, j, k) <- res, let ans = minimum [dp1 ! i, dp2 ! j, dp3 ! k]]
print res'
```