# ABC379 振り返り
- [トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379) - AtCoder](https://atcoder.jp/contests/abc379)
- ABDE 4完 (1231) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc379)
![[スクリーンショット 2024-11-10 10.56.59.png]]
ABC379 でした。
- A (灰) ··· $N$ を桁ごとに分解して変数 $a, b, c$ に束縛し、$b, c, a$ と $c, a, b$ を出力
- B (灰) ··· 連長圧縮で虫歯のない歯の連続する長さを調べて、それを $K$ で割る
- C (緑, upsolve) ··· $N \leq 2 \times 10^9$ あるのでシミュレーションできない。繰り越し分の石の数、隣のマスまでの距離を考慮に入れて畳み込む
- D (茶) ··· オフセットを状態で持ちながら、multiset 相当で植物を管理
- E (水) ··· 主客転倒。各桁の数字の寄与の係数は位置 $i$ に依存。$10$ 進数みたいな計算をする。オーバーフローは Haskell は多倍長整数使えば問題なし
C が一見簡単そうにみえて落とし穴の多い問題で、躓きました。
沼ってしまったので C を飛ばして D を解いた時点で 60分以上経過、焦りましたが E が比較的簡単だったのでなんとかなりました。
C にこういうややムズ問題が出ると、ハードな回になりがちです。
## [A - Cyclic](https://atcoder.jp/contests/abc379/tasks/abc379_a)
問題文通りに、桁ごとに $a, b, c$ という変数に束縛する。
Haskell にはパターンマッチがあるので楽です。
```haskell
main :: IO ()
main = do
n <- getInt
let [a, b, c] = toDigits 10 n
printList $ [fromDigits 10 [b, c, a], fromDigits 10 [c, a, b]]
```
## [B - Strawberries](https://atcoder.jp/contests/abc379/tasks/abc379_b)
連続した $K$ 本の虫歯のない歯があるとイチゴを一個食べられる、というので連長圧縮ですね。
連長圧縮して連続した虫歯のない歯の本数を割り出し、それを $K$ で割ると各区間で何個イチゴを食べられるかわかります。
```haskell
main :: IO ()
main = do
[n, k] <- getInts
s <- getLine
let res = [x `div` k | (c, x) <- rle s, c == 'O']
print $ sum' res
```
## [C - Sowing Stones](https://atcoder.jp/contests/abc379/tasks/abc379_c) (upsolve)
シミュレーションできれば比較的簡単な問題ですが、 $N \leq 10^9$ あるのでそれは難しい。
というか最初制約をちゃんとみておらずシミュレーションして 1 ペナもらいました。
というわけで、$X_i$ と $X_{i + 1}$ の距離を使って、がんばって計算します。
![[IMG_2041.jpeg|600]]
例として、この図の $X_i = 1$ と $X_{i + 1} = 6$ のケースを考えます。
- $X_6$ と $X_1$ の間には、石が入ってない空のマスが $4$ 個ある。これを $d$ とすると $d = X_{i + 1} - X_i - 1$
- $X_1$ に予め $10$ 個石が入っていたとして、$X_1$ で $1$ 個消費。残り $9$ 個を右に順番に移していく。$X_6$ に移すまでに $9, 8, 7, 6, 5$ 回ずつ操作が必要。ところで $X_i$ には、それ以前のマスからの繰り越し分も入って来る。これを $acc$ とすると先の $9, 8, 7, 6, 5$ と言う系列は $acc + A_i - 1$ から $acc + A_i - 1 - d$ まで $-1$ ずつ減る等差数列だということになる
この考え方を使います。
つまり、繰り越し分を状態にもちながら現在のマスと隣のマスまでの距離を使って、等差数列の和で各区間で必要な操作の回数を都度 $O(1)$ で計算します。
実装上はいくつか気をつける必要があります
- $X_i = 0$ と $X_{N + 1}$ に番兵置くとよい
- $X_i$ がソートされてないのに注意
- $A_i$ の合計が $N$ じゃないケースを潰しておく
- 繰り越し分が負になるケースは、$-1$ になるケース
C 問題にしては細かいところまでじっくり考える必要のある問題です。
当の自分は、早解きマインドで前のめってしまいゲームオーバーでした 😓
```haskell
main :: IO ()
main = do
[n, m] <- getInts
xs <- getInts
as <- getInts
let vs = sort' $ (0, 1) : (n + 1, 1) : zip xs as
let res = scanl' f (0, 0) $ zip vs (tail vs)
where
f (acc, _) ((x1, a1), (x2, _)) = do
let d = x2 - x1 - 1
remain = acc + a1 - 1
(remain - d, remain)
if
| sum' as /= n -> print (-1)
| any (< 0) (map fst res) -> print (-1)
| otherwise -> print $ sum' [sumFromTo s t | (s, t) <- res]
```
## [D - Home Garden](https://atcoder.jp/contests/abc379/tasks/abc379_d)
こちらは比較的、典型問題という感じでした。
例によってシミュレーションは難しいので、工夫します。
クエリ問題で、場にある要素すべてにクエリ毎に足し算するとみたいなときは、それまでの増加分をオフセットとして状態にもち、全要素に作用するのではなく、操作を遅延させて、出力時など、全体に作用させずに済むタイミングで辻褄を合わせるとうまくいくことが多いです。
- 経過日数をオフセット $d$ と考えて、$T$ 日待つたび、$d$ に $+ T$ されると考える
- 植物を植えたタイミングを $- d$ と考え、収穫時は $H - d$ 以上経過している植物を刈り取ると考える
これで辻褄が合います。
この管理に必要になるデータ構造は、集合として同じ値を持つことが出来て、集合に含まれる特定の値以上の検索が用意なもの。
というわけで multiset 相当のデータ構造が適しています。
それを使って、上記の方針に従って実装。
集合に含まれる $H - d$ 以上の要素を全部取得しつつ残りの集合を得る、という関数を作ってなかったので急遽 `deleteGEViewMS` を実装して AC しました。
```haskell
deleteGEViewMS :: Int -> IntMultiSet -> ([(Int, Int)], IntMultiSet)
deleteGEViewMS x s0 = loop s0 []
where
loop s acc = case lookupGEMS x s of
Just v -> do
let cnt = countMS v s
s' = deleteNMS cnt v s
loop s' ((v, cnt) : acc)
Nothing -> (acc, s)
main :: IO ()
main = do
q <- getInt
qs <- replicateM q getInts
let s0 = emptyMS
foldForM_ (s0, 0) qs $ \(s, d) query -> do
case query of
[1] -> return (insertMS (-d) s, d)
[2, t] -> do
return (s, d + t)
[3, h] -> do
let (xs, s') = deleteGEViewMS (h - d) s
print $ sum' [cnt | (_, cnt) <- xs]
return (s', d)
_ -> error "Invalid Query"
```
## [E - Sum of All Substrings](https://atcoder.jp/contests/abc379/tasks/abc379_e)
またしても $\sum\sum$ です。
主客転倒します。
例えば $379$ に対しては
$f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=3+37+379+7+79+9=514$
となりますが、$3$ や $7$ や $9$ がそれぞれ答えにどう寄与しているかよくみてみると
- $3$ は 1の桁で $1$ 回、$10$ の桁で $1$ 回、$100$ の桁で $1$ 回ずつ寄与
- $7$ は $1$ の桁で $2$ 回、$10$ の桁で $2$ 回
- $9$ は $1$ の桁で $3$ 回
寄与していることがわかります。$3, 7, 9 \ldots$ と数字を左からみていったとき、その数字が何度目にでてくるかで各桁での寄与回数が決まる。
これは整数の系列を $10$ 進数に直していくときの計算に、構造がよく似ています。
$10$ 進に直す関数は
```haskell
fromDigits n = foldl' (\acc b -> acc * n + b) 0
```
と実装できますが、この $+b$ のところに桁の位置 $i$ が係数として掛けるとよさそう。
かつそれを、$3 + 37 + 379 + \ldots$ と、計算途中で出てきた数字を残していって全部加算する。つまり累積的に加算していけばよいです。
言葉で説明すると難しそうですが
「$10$ 進数みたいな感じだけど、各桁の寄与は位置 $i$ が関係しているな」
「途中作った数字は全部答えに加算していくので、累積演算ぽいな」
という思考で構造をみつけられたので、比較的スムーズでした。
なお、答えはかなり大きな整数になるので多倍長整数を使いました。Haskell ならそれ以上の工夫は必要なく、1.7 sec で AC です。
```haskell
main :: IO ()
main = do
n <- getInt
s <- getLine
let digits = map digitToInt s
res = scanl' f 0 $ indexed 1 digits
where
f acc (i, di) = acc * 10 + fromIntegral di * fromIntegral i
print $ sum' res
```
## 感想
C に時間を費やしたのに解けず飛ばしたときは、今回は大敗を覚悟しましたが C で詰まっていた人たちが多かったようで、
D, E と解いてなんとか水色パフォーマンスが取れました。
E の構造が、Haskell をやっていると見抜きやすかったというのはありそう。多倍長整数でも特に苦労しなかったですし、運が味方しました。
3連続で水色パフォーマンスでレートは 1148 となり、ようやく Highest を更新しました。
あと 50 ちょっとで目標の入水ですが、1200 ちょっとぐらいのパフォーマンスではレートがなかなか上がらないですね。
到達にはまだ少し、時間はかかりそうです。