# ABC369 振り返り
- [AtCoder Beginner Contest 369 - AtCoder](https://atcoder.jp/contests/abc369)
- ABCD 4完 (952) [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc369)
![[スクリーンショット 2024-09-02 14.26.04.png]]
ABC369 でした。
E が水色 diff で ABCD が比較的簡単。D まで早解き 4完できれば少なくともレートが下がることなはかったのですが、A と D でミスをして 2ペナ。
この 2ペナが響いてレート -15 です。順位表がダンゴになるときはペナルティが痛いです。
- A (灰) ··· $(x, A, B)$ と $(A, x, B)$ と $(A, B, x)$ のうち成立するものを数える。全探索でもよい
- B (灰) ··· 左手と右手のケースは独立
- C (灰) ··· 差分列にして連長圧縮で等差部分列の最大長を求める。あとは長さ $n$ に対して $n + _nC2$
- D (茶) ··· DP
- E (水, upsolve) ··· ワーシャルフロイド + 順列全探索 (辺をどっちの方向から辿るのかも含めて $2 \times 5$ 通り)
## [A - 369](https://atcoder.jp/contests/abc369/tasks/abc369_a)
入力で与えられた $A, B$ に対して $x$ 等差数列になる $x$ は幾つあるか?
$A$ と $B$ の公差は決まるので、$x, A, B$ と $A, x, B$ と $A, B, x$ の場合の $3$ つのうちどれが成立し得るかを考えます。
が、場合分けを考えるのが面倒。制約が小さいので全探索しました。
そして探索範囲の上界と下界を間違えて 1ペナもらってしまいました。
```haskell
main :: IO ()
main = do
[a, b] <- getInts
let res = [1 :: Int | i <- [-200 .. 200], let [p, q, r] = sort' [i, a, b], q - p == r - q]
print $ sum' res
```
## [B - Piano 3](https://atcoder.jp/contests/abc369/tasks/abc369_b)
一見すると複雑な問題に見えますが、問題文をよく見ると左手と右手のコストは独立であることがわかります。
左手と右手の系列をそれぞれ作って、コスト計算をする。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- replicateM n $ auto @(Int, Char)
let (as, bs) = bimap (map fst) (map fst) $ partition (\(_, s) -> s == 'L') xs
costL = sum' $ zipWith (\a b -> abs $ b - a) as (tail as)
costR = sum' $ zipWith (\a b -> abs $ b - a) bs (tail bs)
print $ costL + costR
```
## [C - Count Arithmetic Subarrays](https://atcoder.jp/contests/abc369/tasks/abc369_c)
例えば $(3, 6, 9, 12)$ という等差数列がある場合、$(3, 6, 9, 12)$ そのもの以外にも任意の二箇所を選んだ部分列が等差数列になります。
つまり、長さ $n$ の等差数列があった場合、寄与数は $n + _nC_2$ になります。
これを利用します。
先に、入力の製数列 $A$ を差分列にします。
その上で、連長圧縮を行って等差数列になっている部分列の最大長を割り出し、先の式を適用します。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let ds = zipWith (-) (tail as) as
k = sum [x + nc2 x | (_, x) <- rle ds]
print $ n + k
```
## [D - Bonus EXP](https://atcoder.jp/contests/abc369/tasks/abc369_d)
DP です。
先頭から順に $A$ をみていって、どのモンスターを倒し、どのモンスターを倒さなかったときにスコアが最大化するか?
「選ぶ・選ばない」の分岐を全探索すればよいので、ナップザック問題の匂いがします。
ただし、制約が $N \leq 2 \times 10^5$ あるので「何体のモンスターを倒したか」を状態にもってナップザック問題をやると $O(N^2)$ で TLE します。
しかし、この問題はモンスターを倒した数の偶奇性にしか実は興味がありません。
よって状態空間は $(0, 1)$ の二値で管理できて計算量は $O(N)$ に抑えられます。
と書いてますが最初、真面目に計算量を考えてなくて $O(N^2)$ の実装のまま送信して TLE してしまいました。
もったいない。
```haskell
main :: IO ()
main = do
_ <- getInt
as <- getInts
let dp = accumArrayDP @UArray f max (minBound :: Int) (0, 1) [(0, 0)] as
where
f (i, acc) ai
| acc == minBound = []
| otherwise = [(i, acc), (i', acc + bool ai (2 * ai) (even i'))]
where
i' = (i + 1) `mod` 2
print $ maximum (elems dp)
```
## [E - Sightseeing Tour](https://atcoder.jp/contests/abc369/tasks/abc369_e) (upsolve)
このグラフ問題の特徴的なところは、$N < 400$ と $Q < 3000$ 、それから $K_i < 5$ という制約です。
基本的には最短経路問題ですが $N < 400$ あたりから二頂点対間距離を計算することができそうですし、$K_i < 5$ あたりから全列挙が匂います。
結論、先にワーシャルフロイドで二頂点対間距離を求めておき、各クエリに対して、$B_1 \ldots B_k$ をどういう順で訪問するか順列全探索 (permutations) すればよいです。
さらに、辺 $B_i$ を $u → v$ と移動するのか $v → u$ と移動するかの 2 パターンあるのでそれも全探索します。
なお、グラフ構築の際、多重辺はコストの小さいもののみ採用するよう前処理を加えておくとよいです。
わかってしまえば簡単なのですが、本番中はダイクストラ法を改造してどの $B_i$ を訪問したかビットフラグ管理するみたいなことをやりはじめて、実装で沼って終わってしまいました。時間は十分にあったのに解法を固めすぎて柔軟性を欠きました、反省が残ります。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getWeightedEdge
q <- getInt
qs <- replicateM q $ do
_ <- getInt
getInts
let es = listArray @Array (1, m) uvs
uvs' = Map.assocs $ accumMap min maxBound uvs
g = wGraph2 (1, n) uvs'
dist = warshallFloyd (g !) (+) inf (bounds g) [(v, 0) | v <- [1 .. n]]
for_ qs $ \bs -> do
let costs = sum [w | b <- bs, let (_, w) = es ! b]
res =
[ foldl' (\(v, acc) (a, b) -> (b, acc + dist ! (v, a))) (1, 0) path
| bs' <- permutations bs,
path <- sequence [[(u, v), (v, u)] | b <- bs', let ((u, v), _) = es ! b]
]
print $ costs + minimum [cost + dist ! (v, n) | (v, cost) <- res]
```
## 感想など
A と D のケアレスミスは、ミスなので仕方がないとして E 問題を早々に方針を固めすぎたのは良くなかったです。
もうすこしじっくり解法を考えて、複数の候補の中から方針を選択するべきでした。反省。
レートは下がって 1100 を割ってしまいました。水色が遠のきました。
また3歩すすんで2歩下がる。匍匐前進です。