# ABC340 振り返り
- [鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340） - AtCoder](https://atcoder.jp/contests/abc340)
- ABCDE 5完 (バーチャル参加)
![[スクリーンショット 2024-02-11 11.11.50.png]]
ABC340 は私用のため本戦は不参加でした。開催翌朝にバーチャルで参加しました。
結果、ABCDE 5完でした。
- A (灰) ··· 等差数列を生成する。`[a, a + d .. b]`
- B (灰) ··· リストを使って末尾の操作をシミュレーションする
- C (茶) ··· メモ化再帰
- D (茶) ··· ダイクストラ法で最短距離を求める
- E (緑) ··· 区間更新を遅延評価セグメント木でやる
でした。
C のメモ化再帰のところで、やや慣れていないこともあり少し時間がかかりましたが、D は見てすぐに解法がわかったので取り戻した感じがあります。
E も遅延評価セグメント木を使えばいいのはすぐわかりましたが、更新区間を割り出すところをどう計算するかが、ややごちゃついて時間を要しました。
E は公式解説も遅延評価セグメント木でしたが、これが緑難易度とはなかなかのインフレ具合です。
なお、F は「拡張ユークリッドの互除法」らしいですが、まだ知識的に足りず、まったく解ける気がしませんでした。
----
## [A - Arithmetic Progression](https://atcoder.jp/contests/abc340/tasks/abc340_a)
$A \ldots B$ までの公差 $D$ の等差数列を生成します。
リストで素直に書きました。
```haskell
main :: IO ()
main = do
[a, b, d] <- getInts
printList [x | x <- [a, a + d .. b]]
```
···よくみたら、リスト内表表記いらないですね。まあ、よいです。
## [B - Append](https://atcoder.jp/contests/abc340/tasks/abc340_b)
B でクエリ問題というのは珍しいかもしれないですね。
系列の末尾に値を追加する、というのはリストの得意操作なのでこれまたリストを素直に使う。
`foldM_` で IO しながらリスト操作を行います。
```haskell
main :: IO ()
main = do
q <- getInt
qs <- replicateM q getInts
foldForM_ [] qs $ \xs query -> do
case query of
[1, x] -> return (x : xs)
[2, k] -> do
print $ xs !! (k - 1)
return xs
_ -> error "invalid"
```
## [C - Divide and Divide](https://atcoder.jp/contests/abc340/tasks/abc340_c)
$x$ が $\displaystyle\left\lfloor\frac{x}{2}\right\rfloor$ と$\displaystyle\left\lceil\frac{x}{2}\right\rceil$ の二方向に状態遷移する問題ですね。
状態遷移厨なので、まずは
```haskell
f x
| x <= 1 = []
| otherwise = [x `div` 2, x `ceildiv` 2]
```
という、頂点 $x$ を状態遷移させる関数 $f$ を定義してグラフで考え始めました。
この状態遷移を探索アルゴリズムに入れればそれだけでいけるかな? と思いグラフの DFS 関数を適用したところ、サンプル 1 やサンプル 2 が通りました。が、サンプル 3 の計算が終わらない。
なるほど、DFS の出力をみるに再帰的に何度も同じ計算が出てきて、計算量が嵩んでいるようです。
メモ化再帰の出番です。
グローバル変数が使えない Haskell ではメモ化にちょっと工夫が必要です。
再帰の関数呼び出しをまたいで計算結果を共有する... いろいろやり方はありそうですが State モナドを使いました。
この実装を面倒くさがって普段からメモ化を避けていることもあり、やや手こずりました。
```haskell
f 0 = return 0
f 1 = return 0
f k = do
memo <- gets (IM.lookup k)
case memo of
Just x -> return x
Nothing -> do
i <- f (k `div` 2)
j <- f (k `ceildiv` 2)
modify (IM.insert k (k + i + j))
return (k + i + j)
main :: IO ()
main = do
n <- readLn @Int
let (x, _) = runState (f n) IM.empty
print x
```
## [D - Super Takahashi Bros.](https://atcoder.jp/contests/abc340/tasks/abc340_d)
こちらの問題もやはり状態遷移の問題ですね。各ステージを状態とみなして、状態 $i$ から $i + 1$ に遷移するか $X_i$ に遷移するか。
この状態遷移をグラフの頂点の遷移だと見なします。
それぞれの遷移には、コストが $A_i$ もしくは $B_i$ かかる。$X$ を目指すときのコストの総和の最小を求める。
重み付きグラフにおける最短距離を求める問題となるので、ダイクストラ法で解けます。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- replicateM (n - 1) getInts
let uvs = [[((v, v + 1), a), ((v, x), b)] | (v, [a, b, x]) <- zip [1 :: Int ..] xs]
g = wGraph (1, n) $ concat uvs
dist = dijkstra (g !) (bounds g) [(1, 0)]
print $ dist ! n
```
## [E - Mancala 2](https://atcoder.jp/contests/abc340/tasks/abc340_e)
今回の山場です。
問題文で与えられている操作は、常に連続する区間の更新に相当します。
区間更新を効率的に行えるデータ構造といえば、遅延評価セグメント木 (Lazy Segment Tree) です。
[[ABC338 振り返り|ABC338]] の upsolve で遅延評価セグメント木を使ったこともあって、その後実装を整えて幾つかの問題を解いていました。おかげでメンタルモデルが出来上がっていて、この問題もみてすぐ、遅延評価セグメント木を使えばいいことに気づきました。
問題は、操作にあたり値を配る区間がどこからどこまでになるかをどう計算するかです。
$i + 1$ から、その時点の箱 $B_i$ の中のボールの個数分の区間に大してボールを配ります。
このときボールの数が十分に大きければすべての箱にボールを均等に配って、余ったものを $i + 1$ から順に $1$ つずつ配ってなくなったところで終了です。
この考え方でボールを配る区間を求める関数 $f$ を定義しましたが、この実装がちょっと面倒でした。
$i + 1$ からボールを配って行った結果、配り先が $N - 1$ を超えた場合 $0$ に戻ってそこから配っていく、つまり周期性を考える必要がありました。
なお遅延評価セグメント木を使いましたが、この問題においては区間更新はありますが、区間取得はなく単一取得です。
つまり「区間更新・区間取得」ではなく「区間更新・一点取得」ですね。本来は遅延評価セグメント木よりも、双対セグメント木の方がより最適なデータ構造だと思いますが、双対セグメント木は実装を作っていません。
```haskell
-- >>> f 5 2 3
-- [(3,4,1),(0,0,1)]
-- >>> f 5 4 6
-- [(0,4,1),(0,0,1)]
f n i ai = do
let i' = (i + 1) `mod` n
let (p, q) = ai `divMod` n
xs =
if i' + q - 1 <= n - 1
then [(i', i' + q - 1, 1)]
else [(i', n - 1, 1), (0, (i' + q - 1) `mod` n, 1)]
if p /= 0 then (0, n - 1, p) : xs else xs
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
bs <- getInts
dp <- newListLST @IOUArray n (+) 0 (+) 0 (+) as
for_ bs $ \i -> do
x <- rangeQueryLST dp i (i + 1)
rangeUpdateLST dp i (i + 1) (- x)
for_ (f n i x) $ \(l, r, k) -> do
rangeUpdateLST dp l (r + 1) k
printList =<< getElemsLST dp
```
更新区間を求める計算に四苦八苦して少し時間をかけてしまいましたが、セグメント木を円環 ··· つまり $2$ 倍のサイズにしてやると周期性を考える必要がなくなり実装が楽になると、じゅーすいそさんが投稿していました。
確かに、これならずっと楽です。バグらせにくい実装です。
```haskell
f n i ai =
let (p, q) = ai `divMod` n
in [(0, n - 1, p), (i + 1, i + q, 1)]
main :: IO ()
main = do
[n, _] <- getInts
as <- getInts
bs <- getInts
dp <- newListLST @IOUArray (2 * n) (+) 0 (+) 0 (+) as
for_ bs $ \i -> do
x <- rangeQueryLST dp i (i + 1)
y <- rangeQueryLST dp (i + n) (i + n + 1)
let z = x + y
rangeUpdateLST dp i (i + 1) (- z)
for_ (f n i z) $ \(l, r, k) -> do
rangeUpdateLST dp l (r + 1) k
as' <- getElemsLST dp
printList $ zipWith (+) (take n as') (drop n as')
```
より簡単な問題でデータ構造を円環にするというのをやったことは何度かあります。
私も E 問題のような山場でも、慌てず落ち着つき仏様のような俯瞰ビューでしなやかに円環にするメンタリティが欲しいです。
## 感想など
スタック、メモ化再帰、ダイクストラ法、遅延評価セグメント木 ··· と今回はアルゴリズム的な知識を要求される典型問題が多く、割と得意な問題セットだったと思います。
80分で5完は仮に本戦だったとすると水色パフォーマンスで、良い出来だと思います。
一方、やはりバーチャル参加では本番のような緊張感がないということもり、焦って真っ白になることがありません。
本番で同じように解けるかどうかは、怪しいですね。これぐらいの気持ちで本番でも臨めるとよいのですが😂
次回 2/17 (土) ABC341 はいつもどおり参加予定です。