# ABC388 振り返り
- [HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388) - AtCoder](https://atcoder.jp/contests/abc388)
- ABCDE 5完 (1333) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc388)
![[スクリーンショット 2025-01-12 13.49.45.png]]
ABC388 でした。
- A (灰, 8) ··· 先頭一文字に `UPC` をくっつける
- B (灰, 30) ··· ナイーブに $O(ND)$ の実装をして問題ない
- C (灰, 211) ··· $A_i$ を固定して二分探索で半分以下の値が何個あるか数える
- D (茶, 659) ··· ある $i$ からどこまで配れるか? という問題に言い換える。遅延伝搬セグメント木での実装が楽
- E (緑, 1068) ··· 下位半分、上位半分に分けて考える。Two Pointers アルゴリズムで比較
D に少し時間が掛かってしまい解いた時点で推定パフォーマンスが 1000 を切っていました。みんな早い...。
E は気づけば実装は簡単、という問題でなんとか解いて水色パフォーマンス。連敗分を少し戻しました。
## [A - ?UPC](https://atcoder.jp/contests/abc388/tasks/abc388_a)
素直にやる。入力先頭一文字に `UPC` を結合して出力します。
```haskell
main :: IO ()
main = do
s <- getLine
putStrLn $ head s : "UPC"
```
## [B - Heavy Snake](https://atcoder.jp/contests/abc388/tasks/abc388_b)
$N, D \leq 100$ と小さいので $O(ND)$ でも余裕。ナイーブに計算します。
```haskell
main :: IO ()
main = do
[n, d] <- getInts
xs <- replicateM n getTuple
for_ [1 .. d] $ \k -> do
let res = [ti * (li + k) | (ti, li) <- xs]
print $ maximum res
```
## [C - Various Kagamimochi](https://atcoder.jp/contests/abc388/tasks/abc388_c)
各 $A_i$ からみたときに、自分より半分以下の重量のものが何個あるか?
$A_i$ を固定して二分探索し、それぞれの $A_i$ に対する半分以下の重量の個数を求めれば OK
```haskell
main :: IO ()
main = do
n <- getInt
as_ <- getInts
let as = listArray @UArray (1, n) as_
print $ sum' [boundLE (ai `div` 2) as | ai <- as_]
```
## [D - Coming of Age Celebration](https://atcoder.jp/contests/abc388/tasks/abc388_d)
茶 diff ですが、結構難しいと感じました。
本番ではいもす法っぽくやりましたが、遅延伝搬セグメント木を使う方が考察もふくめ簡単で良いと思いました。
この問題のポイントは、ある $i$ の人からみたとき後ろの ${i + 1}$ 以降に対し $1$ 回ずつ $1$ 配る構造になっていることです。
そして、配るタイミングでの $i$ の値によっては、右端までは配れないこともあるわけです。
![[IMG_2643.jpeg]]
$i$ からみて $1$ を配れる区間長は、その時点の $i$ の値が $x_i$ だとすると $min(x_i, N - i)$ になります。
途中まで配って $x_i = 0$ になるか、右端まで配りきることができるか、どちらかです。
遅延伝搬セグメント木なら
- $i$ の値 $x_i$ を一点取得で読み取る
- 配る長さ $give = min(x_i, N - i)$ を求める
- $i$ の値を $give$ だけ減らして、$[i + 1, i + give)$ に $1$ を配る
という動きをわりと素直にシミュレーションできます。
セグメント木の要素数を少し多めにして 1-based index で考えつつ右端にも番兵を置くと、実装がシンプルになります。
なお、この問題では取得は一点取得になるので二項演算は割と何でも良いです。
```haskell
main :: IO ()
main = do
n <- readLn
as <- getInts
seg <- newListLST (n + 2) (+) 0 (+) 0 (+) $ 0 : as
for_ [1 .. n] $ \i -> do
x <- readLST seg i
let give = min x (n - i)
updateLST seg i (negate give)
rangeUpdateLST seg (i + 1) (i + give + 1) 1
printList =<< init . tail <
gt; getElemsLST seg
```
セグメント木を使わなくても、同じ考え方をいもす法のような実装で実現することができます。
ただし通常のいもす法の計算とは違って、いもす法を計算する過程である $i$ からどこまで配れるかの区間長 $give$ を求める必要があるところが難しいです。よくあるいもす法の場合 $+1$ と $-1$ する区間は予めわかっている前提で累積和を取りますが、この問題では累積和を取りながら $i + 1$ からの区間長を求めていく必要があります。
```haskell
main :: IO ()
main = do
n <- readLn
as <- getInts
g <- newArray @IOUArray (1, n + 1) (0 :: Int)
(_, xs) <- mapAccumMFor 0 (indexed 1 as) $ \acc (i, ai) -> do
let x = ai + acc
give = min x (n - i)
modifyArray g (i + 1) (+ 1)
modifyArray g (i + give + 1) (+ negate 1)
s <- readArray g (i + 1)
return (acc + s, x)
printList [x - min x (n - i) | (i, x) <- indexed 1 xs]
```
## [E - Simultaneous Kagamimochi](https://atcoder.jp/contests/abc388/tasks/abc388_e)
「E にしては簡単だな! 大きな餅からみていって、半分以下の大きさのうち一番大きい奴を組み合わせるを貪欲に繰り返していけばいいじゃん!」と実装すると WA になります。
まあ、そんな気はしたんですが、その通りにやったら 1 WA もらいました。
順位表をみてもそんなにたくさんの人が解けてなかった時点で、察するべきです。
```
2 2 4 8
```
みたいなケースだと、`8` に対して `4` を組み合わせられますがそうすると 1 ペアしか作れない。
`8` に対して `2` を組み合わせると、残った `4` と `2` も組み合わせられて 2 ペアにできます。
というわけで、そんな簡単な貪欲ではうまくいきません。
ここで、「理想的にペアが組めたときの最大数」、つまり上界について考えてみます。いちばんペアが作れるケースというのは、$N$ 個の餅を余すことなく全部 2 ペアにできたとき。
つまり $N$ 個の餅を大きさの下位半分と上位半分に分け、それらの間に一対一対応が完全に作れたときです。
ここがポイントです。
下位半分と上位半分にわけてペアリングすることを検討します。
よく考えると、下位半分に属するある小さな餅が、また別の下位半分に属する餅と組み合せになることは考える必要がないことに気がつきます。
一対一対応が上界だとすると「下位半分に属する餅どうし(小さい餅同士)」を組み合わせるよりも、「下位半分の餅を上位半分の餅と組み合わせる」ほうが、ペアを作れる可能性が高そう。上位半分に続している餅は、下位の餅からみたら、ほかの下位に属している餅の上位互換と考えることができます。よって「下位同士でペアを組ませないと数が増えるケース」というのは起き得ず、組む相手がみつかるなら必ず上位のどれかと結びつけるでよさそう。
結論、下位のリストを小さいものから見ていき、上位のリストに残っているなるべく小さいものと貪欲に結びつけていけばよいです。
実装としてはリストを半分の所で下位 $xs$ と上位 $ys$ に分割し、Two Pointers アルゴリズム··· しゃくとり法のような要領で $xs$ と $ys$ の先頭 $x$ と $y$ を比較していきます。
このとき $xs$ と $ys$ は、引き続きそれぞれソートされています。
$y$ が $x$ の $2$ 倍以上なら、その二つはペアリングできる。ので $x$ と $y$ をそれぞれ取り除いて残った $xs'$ と $ys'$ で引き続き比較。
そうでないなら、その $y$ はどの下位の要素ともペアリングできないので、$y$ だけ捨てる。$xs$ と $ys'$ を比較。
これを繰り返してどちらかのリストが空になるまで続ける。
これで AC です。
```haskell
loop acc [] _ = acc
loop acc _ [] = acc
loop acc (x : xs) (y : ys)
| x <= y `div` 2 = loop (acc + 1) xs ys
| otherwise = loop acc (x : xs) ys
main :: IO ()
main = do
n <- getInt
as <- getInts
let (xs, ys) = splitAt (n `div` 2) as
print $ loop 0 xs ys
```
## 感想など
ABC とスムーズに解けて、D も少し時間がかかりましたが 45 分以内には解けたのでそこそこパフォーマンス出てるのでは? と思って順位表をみたら 1000 を切っていたときの「え?」という感じはプライスレスでした。
みなさん D はやいですね···
遅延伝搬セグメント木を持ち出せばすぐ解ける、という上位勢が多かったのでしょうか
ここ最近、イベントソートや桁DP など、まだ自分の中で解像度の低いアルゴリズムが出たときにうまく立ち振る舞えないのがよくわかったので、この2週間は 桁DP、イベントソート、平面走査、しゃくとり法など特定のアルゴリズムに絞った精進をしていました。
おかげで今回の D は区間の問題に見えたし、E も Two Pointers アルゴリズムに思考が至りました。
以前にも少し書きましたが、スポーツの練習時に特定のスキルを集中的に練習する「ブロック練習」と、似たような複数のタスクを混ぜて練習する「ランダム練習」では、後者の方が学習効果が高いということらしいです。
ここ数ヶ月はランダム練習、とくに分野は決めずに問題を解くことを続けていました。
が、ある特定のアルゴリズムに対しより本質的なメンタルモデルを獲得するには、ブロック学習で集中にやって、そのアルゴリズムについて考え続けて深く掘り下げることも有効なのかも、と思いました。
他にもいくつか心当たりのあるアルゴリズムがあるので、もう少しブロック学習法でやってみます。