# ABC371 振り返り
- [AtCoder Beginner Contest 371 - AtCoder](https://atcoder.jp/contests/abc371)
- ABCDE 5完 (1243) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc371)
![[スクリーンショット 2024-09-15 8.22.05.png]]
ABC371 でした
- A (灰) ··· がんばって場合分けでもよいですが、順列全探索しました
- B (灰) ··· 各 $A_i$ ごとにフラグ管理して初回にフラグが `True` になるとき `Yes`
- C (緑) ··· 順列全探索。問題文にある同型の定義どおりに実装すればよい
- D (茶) ··· 座標圧縮してセグメント木などで区間和をとる
- E (緑) ··· 主客転倒。各 $A_i$ の出現位置に着目し、余事象で $A_i$ が含まれない区間の数を取り除く
## [A - Jiro](https://atcoder.jp/contests/abc371/tasks/abc371_a)
A 問題にしては難しい。はじめは分岐を全部列挙していたのですが、どうも細かいところで間違えて3ペナもらってしまいました。
仕方がないので permutations で $A, B, C$ の並び方を順列全探索し、問題文で与えられた大小関係と矛盾してないものを残す、とやって解きました。
A なのにここまでさせるとは憎い問題です。
```haskell
validate order (x, y, s) = do
i <- elemIndex x order
j <- elemIndex y order
return $ if s == '<' then i > j else i < j
main :: IO ()
main = do
(ab, ac, bc) <- auto @(Char, Char, Char)
let res =
[ order
| order <- permutations ['A', 'B', 'C'],
all (fromMaybe False . validate order) [('A', 'B', ab), ('A', 'C', ac), ('B', 'C', bc)]
]
putChar $ head res !! 1
```
## [B - Taro](https://atcoder.jp/contests/abc371/tasks/abc371_b)
各 $A_i$ ごとに初めて $B_i$ が `M` となったタイミングで `Yes` を出力すればよいです。
ので $A_i$ ごとに初期値 `False` のフラグを管理し、それが初めて `True` になるタイミングで `Yes` を出力する。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
xs <- replicateM m $ auto @(Int, Char)
as <- newArray @IOUArray (1, n) False
for_ xs $ \(i, c) -> do
if c == 'M'
then do
res <- readArray as i
writeArray as i True
printYn $ not res
else do
printYn False
```
## [C - Make Isomorphic](https://atcoder.jp/contests/abc371/tasks/abc371_c)
グラフ $G$ と $H$ と二つのグラフを同型にするために、何本辺をいじれば良いか。
最初「同型」の意味がわからなかったのですが、定義には以下のようにありました。
> $N$ 頂点のグラフ $G$ と $H$ が**同型**であるとは、ある $(1,2,…,N)$ の並べ替え $(P_1,P_2,\ldots,P_N)$ が存在して、どの $1 \leq i < j \leq N$ に対しても
>
>- $G$ に頂点 $i$, 頂点 $j$ を結ぶ辺が存在するとき、かつそのときに限り $H$に頂点 $P_i$, 頂点 $P_j$ を結ぶ辺が存在する
>
> が成り立つことをいいます。
そしてこの定義文が重要で、定義文そのままに実装すると答えになります。
つまり、頂点 $(1, 2, \ldots, N)$ の並び順すべてを順列で全列挙し、 $G$ に $(i, j)$ を結ぶ辺があって $H$ に $(P_i, P_j)$ を結ぶ辺がないならコスト $A_{i, j}$ をかけて辺を作る、逆に $G$ に辺がなくて $H$ に辺がある場合はコスト $A_{i,j}$ をかけてそれを削除する。
これを順列で列挙した全ての頂点の並び順に対して計算して、最小コストを出力すれば OK です。
```haskell
main :: IO ()
main = do
n <- getInt
mg <- getInt
uvs1 <- replicateM mg getTuple
mh <- getInt
uvs2 <- replicateM mh getTuple
rows <- replicateM (n - 1) getInts
let as = toMatrixGraph ((1, 1), (n, n)) 0 rows
g = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[(e, True), (swap e, True)] | e <- uvs1]
h = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[(e, True), (swap e, True)] | e <- uvs2]
let ans =
minimum
[ cost
| ps <- listArray @UArray (1, n) <
gt; permutations [1 .. n],
let cost =
sum'
[ as ! (v, u)
| (i, j) <- comb2 [1 .. n],
let (v, u) = (ps ! i, ps ! j),
g ! (i, j) /= h ! (v, u)
]
]
print ans
```
## [D - 1D Country](https://atcoder.jp/contests/abc371/tasks/abc371_d)
A, C と厄介な問題のあとオアシスのような問題。
座標の整数サイズが $-10^9 \ldots 10^9$ と大きいことを除けば、ただの区間和クエリ問題です。
累積和や BIT、セグメント木あたりで瞬殺できそうな問題です。
が、座標が大きいのが難点。こういうときは座標圧縮です。座標圧縮すれば、$X_1 \ldots X_N$ とクエリに出てくる座標の個数分だけに、インデックスサイズが収まります。
というわけで座標圧縮して区間和のセグ木で殴りました。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- getInts
ps <- getInts
q <- getInt
qs <- replicateM q getTuple
let (ls, rs) = unzip qs
let xs' = xs ++ ls ++ rs
(rank, ix) = zaatsuRank @UArray 1 xs'
seg <- newST @IOUArray (+) (0 :: Int) (1, numElements rank)
for_ (zip xs ps) $ \(x, p) -> do
updateST seg (ix x) (const p)
for_ qs $ \(l, r) -> do
ans <- rangeQueryST seg (ix l) (ix r + 1)
print ans
```
## [E - I Hate Sigma Problems](https://atcoder.jp/contests/abc371/tasks/abc371_e)
$\sum\sum$ をみたら主客転倒です。
各整数 $A_i$ ごとの寄与数を考えます。
仮に $(2 ,2 ,2)$ と数列に同じ数字しか出現しない場合、どの $f(i, j)$ も $f(i, j) = 1$ になるので答えは $6$ になります。
これは全ての区間に $2$ が含まれるということを言っていて、その場合、累積的に $1$ ずつ区間が伸びていってその全てに $2$ が含まれていることを意味するので、数字 $2$ の寄与数は等差数列の和 ··· 初項 $1$ 項数 $3$ 、公差 $1$ の等差数列の和で計算できます。$\frac{N \times (N + 1)}{2} = 6$ になります。
仮に $(2, ○, 2)$ のように真ん中の整数が $2$ でなかった場合を考えたい。
$(2, 2, 2)$ だった場合は全体の総和がわかっています。ここから余事象を使って、この総和から $2$ が含まれない区間の数を引きます。
$2$ の出現位置を $[1, 3]$ とすると、$1$ と $3$ の間に距離 $1$ が空いていてそこには $2$ が含まれていません。この長さ $1$ の区間が別の数字だったと考えて、その分を総計から引きます。引く区間の数は距離が $d$ のとき初項 $1$ 項数 $d$ 公差 $1$ の等差数列の和と考えればよい。余事象を考えるにあたり $○$ の箇所はどんな数字であれ全部同一視して構わないというところがポイントです。
この考え方が基本になります。
つまり
- 各 $A_i$ の出現位置に着目し、$A_i$ ごとに出現位置をまとめる
- 出現位置間のギャップ距離 $d$ を計算し、そこに大きさ $d$ の $\ne A_i$ で構成された数列があるとみなし、項数 $d$ の等差数列の和でその区間数を求める。それを総和から引く
- 位置 $0$ と $N + 1$ にもその数が出現しているとみなし番兵を置くと計算が楽
ということをやって、$A_i$ ごとの寄与数をもとめて合計すれば答えになります。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let ix = amap sort' $ graph (1, n) $ zip as [1 .. n]
ans = sum' [resolve xs | xs <- elems ix]
where
resolve xs = sumFromTo 1 n - k
where
p = 0 : xs ++ [n + 1]
k = sum [sumFromTo 1 d | d <- zipWith (\a b -> b - 1 - a) p (tail p)]
print ans
```
## 感想など
A を分岐で書いて 3ペナもらい、C にも時間がかかり今回もレートの大幅減少を覚悟しましたが、なんとか持ちこたえて
結果は水色パフォーマンスのレート +22 で悪くなかったです。
D, E あたりが比較的典型というか、問題文に漂う雰囲気から手法自体が簡単に想像できるもので助かりました。
D は区間和ですし、E は主客転倒。この初見の方針が外れていなければ、その手法に当てにいくように考察していけばいいので、考えやすかったです。
次回の ABC372 は私用で休みです。