# ABC361 振り返り
- [デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361） - AtCoder](https://atcoder.jp/contests/abc361)
- ABCD 4完 (バーチャル参加)
![[スクリーンショット 2024-07-08 17.18.44.png]]
ABC361 は私用のためコンテスト出場はせず、バーチャル参加で解きました。
結果は 4完、パフォーマンス的には可もなく不可もなく、でした。
- A (灰) ··· 整数列を $K$ の位置で分割して、$X$ を入れて、再度結合
- B (灰) ··· 区間の交差判定を $x, y, z$ 軸それぞれでやる
- C (灰) ··· 先頭 or 末尾から $K$ 個値を削除するパターンを全探索。Data.Sequence を使う
- D (水) ··· 操作を文字列の状態遷移と捉えて BFS
- E (水, upsolve) ··· 木の直径を求めて、全体から引く
でした。
本戦に出ずに後日バーチャル参加するのに X で解法に関する投稿を見てしまわないよう、X へのアクセスを控えるようにしていますが、地味にそれが大変です。つい普段の癖で開いてしまい、見覚えのある競プロerの人のアイコンをみては、危ない! と閉じるのを繰り返してました。
## [A - Insert](https://atcoder.jp/contests/abc361/tasks/abc361_a)
$K$ 要素目の直後に整数 $X$ を挿入する。
`splitAt` で整数列を分割して、$X$ を入れて、また結合としました。
```haskell
main :: IO ()
main = do
[n, k, x] <- getInts
as <- getInts
let (pre, post) = splitAt k as
printList $ pre ++ [x] ++ post
```
## [B - Intersection of Cuboids](https://atcoder.jp/contests/abc361/tasks/abc361_b)
B 問題にしては難しい。いつもと傾向が違います。
単純化するために一次元で考えると、ある二点がなす区間と別のある区間が交差しているかどうかは左端と右端を比較することで簡単に調べられます。
二次元の場合、同様に $x$ 軸と $y$ 軸を別々に調べて、いずれも交差していれば矩形自体が重なっていることになります。三次元に拡張するのも、同じ要領です。
というわけで交差判定する関数 `isIntersect` を使って三次元分、それぞれ判定してアンドを取る。
$(a, b, c, d, e, f)$ の対角線での表現がどことどこに対応してるかを考えるのに時間を要しました。
なお区間の交差判定は [ABC070 B - Two Switches](https://atcoder.jp/contests/abc070/tasks/abc070_b) なんかでも出てきます。
```haskell
isIntersect :: (Ord a) => (a, a) -> (a, a) -> Bool
isIntersect (l1, r1) (l2, r2) = max l1 l2 < min r1 r2
solve (a, b, c, d, e, f) (g, h, i, j, k, l) = do
let x = isIntersect (a, d) (g, j)
y = isIntersect (b, e) (h, k)
z = isIntersect (c, f) (i, l)
x && y && z
main :: IO ()
main = do
[a, b, c, d, e, f] <- getInts
[g, h, i, j, k, l] <- getInts
printYn $ solve (a, b, c, d, e, f) (g, h, i, j, k, l)
```
## [C - Make Them Narrow](https://atcoder.jp/contests/abc361/tasks/abc361_c)
これは結構はまりました。
数列の中から $K$ 個値を削除したときの「最大値と最小値の差」を最小化する。
公式解説では $N - K$ 個の固定幅のウィンドウを考えて、それを一つずつずらしながら全探索するといいとありました。消される数字ではなく、残る数字の方に着目した解法です。
自分はその固定幅ウィンドウが思いつかず、消される数字の方に着目して全探索しました。
先頭 / 末尾から $K$ 個値を削除するにあたり、その組み合わせは $(0, K), (1, K - 1), (2, K - 2) \ldots (K, 0)$ の合計 $K$ 種類なのでそれらのパターンを実際に全探索します。
Haskell の Data.Sequence なら先頭から $K$ 件削除する drop や $K$ 件残す take が $O(log(min(i, n -i)))$ で操作できて、高速です。ソート済みの整数列を Data.Sequence で管理して、$K$ 種類のパターンを全部試します。
Data.Sequence に限らず Haskell の基本データ構造はイミュータブルであり、削除操作しても操作前のオリジナルのデータ構造が残っています。「永続データ構造」ならではの実装かもしれません。
```haskell
main :: IO ()
main = do
[n, k] <- getInts
as <- getInts
let deq = Seq.fromList (sort' as)
res =
[ v
| l <- [0 .. k],
let r = k - l
deq' = Seq.take (n - l - r) $ Seq.drop l deq,
let v = do
x <- viewFrontSeq deq'
y <- viewBackSeq deq'
return (y - x)
]
print $ minimumWithDefault 0 (catMaybes res)
```
なお、最初は都度両端をみながら、その時点の総計をより大きく減らせる方を取り除く... という貪欲法で実装していましたが 2ペナもらったところで間違いに気がつきました。貪欲法では、どちらか一方を削りまくったときに最適解がある、というケースに対応出来ないのだと思います。
## [D - Go Stone Puzzle](https://atcoder.jp/contests/abc361/tasks/abc361_d)
長さが高々 $14$ 文字程度の文字列に対して決められた操作が与えられる。
その操作を何回繰り返せば $T$ と同じ文字列を作ることができるか。
$2 \leq N \leq 14$ と小さいので、操作によって作られる文字列の状態は、すべて列挙することが可能そうです。
ただし、ある状態から別の状態に遷移できるかどうかには依存がある、つまり状態遷移を伴います。
状態 $S$ から $T$ に遷移するのに、最小回数で遷移したい。
状態遷移の関数を記述することは比較的簡単で、状態空間もそれほど広くない。
BFS で全状態への遷移を探索するとよさそうです。
ただし、この問題の状態は整数などでなく文字列によって表現されています。
ビット列で状態を表現して整数に変換そのほかもよさそうですが、文字列をそのまま状態として扱うことができればもっと簡単でしょう。
HashMap を使って頂点 (状態) を管理する BFS を定義し、それで解きました。
Haskell の辞書は決して速くはないので速度がやや心配でしたが、杞憂でした。
状態が系列で表現されていて、それを BFS するという問題は [ABC224 D - 8 Puzzle on Graph](https://atcoder.jp/contests/abc224/tasks/abc224_d) が類題です。
朧気ながらそれを覚えていて、そこから解法が想起されました。
```haskell
f n s_ =
let s = listArray @UArray (1, n + 2) s_
in [ elems s2
| let [x, y] = findArrayIndices (== '.') s,
i <- [1 .. n + 1],
s ! i /= '.' && s ! (i + 1) /= '.',
let s1 = swapIArray s i x
s2 = swapIArray s1 (i + 1) y
]
bfs' nextStates v0s = do
let dist = HM.fromList v0s
aux (Seq.fromList [v0 | (v0, _) <- v0s]) dist
where
aux Empty dist = dist
aux (v :<| queue) dist = do
let d = dist HM.! v
us = [u | u <- nextStates v, not (HM.member u dist)]
let (queue', dist') = foldFor' (queue, dist) us $ \(q, dst) u -> do
(q |> u, HM.insert u (d + 1) dst)
aux queue' dist'
main :: IO ()
main = do
n <- getInt
s <- getLine
t <- getLine
let s' = s ++ ['.', '.']
t' = t ++ ['.', '.']
let dist = bfs' (f n) [(s', 0)]
print $ HM.findWithDefault (-1) t' dist
```
## [E - Tree and Hamilton Path 2](https://atcoder.jp/contests/abc361/tasks/abc361_e) (upsolve)
D を解いたところで残り 14分程度だったので、あまり集中できず解けませんでした。
終わってみれば、解法としてはとても簡単でした。
もし全ての頂点を $1$ 度巡った上で、開始点の頂点に戻ってくる場合は総コストは $\displaystyle 2 \times \sum_{i=1}^{k} C_i$ ですが、この問題では最後の頂点を訪れたところで、遷移は終了してよい。
入力例 $1$ のグラフを、根を頂点 $4$ にして書いてみるとよくわかりますが、最後の頂点を訪れたところで遷移を終了するということは、一番最後に訪問した頂点から開始点までの $1$ パスを取り除くことができます。
![[IMG_1249.jpeg|300]]
このパスがもっとも長くなるように開始点と終了点を選ぶと最適解になります。
木において二頂点の単純パスのうち距離最大のものは、木の直径です。
木の直径を求めるのは簡単で、(1) 適当な頂点を選ぶ (2) そこから最も遠い頂点をみつける (3) 2 でみつけた頂点から最も遠い頂点を見つける。2 と 3 で見つかった頂点を結ぶパスが、直径です。
ちなみにアルゴ式に [Q5. 木の直径 (2) | アルゴ式](https://algo-method.com/tasks/1064H4qG)を求める問題があります。
というわけでやることとしては、ダイクストラ法で木の直径を求めて、総コストから引く。これだけでした。木の直径を求めるのに帰着する問題だと気づくことができれば、解ける問題でした。
```haskell
main :: IO ()
main = do
n <- getInt
uvs <- replicateM (n - 1) getWeightedEdge
let g = wGraph2 (1, n) uvs
dist1 = dijkstra (g !) (+) Minimize maxBound (bounds g) (2 * (n - 1)) [(1, 0)]
(s, _) = maximumOn snd (assocs dist1)
dist2 = dijkstra (g !) (+) Minimize maxBound (bounds g) (2 * (n - 1)) [(s, 0)]
(_, d) = maximumOn snd (assocs dist2)
total = 2 * sum (map snd uvs)
print $ total - d
```
## 感想など
バーチャル参加でやると、やはり本番相当の緊張感は全くありません。
以前は本番で緊張しすぎてパフォーマンスが落ちていたのですが、最近はむしろ本番の緊張感がないと集中力が 100% にならないためか、物足りないと感じるようになりました。
今回のバチャも、もしかすれば本番なら5完できていたかもしれないなと思う内容でした。
が、本番では緊張して B や C でより沼っていた可能性もなきにしもあらず。神のみぞ知る、です。
以前も同じようなこと書いてました。
次回 ABC362 は、いつもどおり参加予定です。がんばるぞ。