# ABC353 振り返り
- [AtCoder Beginner Contest 353 - AtCoder](https://atcoder.jp/contests/abc353)
- ABD 3完 (923) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc353)
![[スクリーンショット 2024-05-12 16.34.14.png]]
![[スクリーンショット 2024-05-12 16.34.49.png]]
ABC353 でした。
$\sum\sum$ 式の問題が C, D, E で3題出るなど特徴のある回でした。
結果はいまいち奮わず。C が難しかったです。D を通してなんとか首の皮一枚といったところ。
- A (灰) ··· 先頭要素よりも大きな要素を前からみつける
- B (灰) ··· シミュレーション。収容人数を超えたら新しいグループを用意するを繰り返す
- C (茶, upsolve) ··· 余事象で考える。先に $10^8$ 云々を無視して総計を計算し、その後、足して $10^8$ 以上になるペアの個数分 $10^8$ を引く
- D (緑) ··· $A_i$ を固定して累積和で $\sum{A_j}$ を計算するのを基本にしつつ、それを桁ごとにやるとうまくいく
- E (水, upsolve) ··· 最長共通接頭辞といえばトライ木。トライ木で考察しつつ、実装はハッシュ化でやると楽
でした。
C でしばらく粘りましたが解けず、飛ばして D に行ってなんとか AC。
E にいくか C に戻るか迷いましたがその時点では E を解いている人は多くなかったので C に戻りました、が、進展なくゲームーバーでした。
## [A - Buildings](https://atcoder.jp/contests/abc353/tasks/abc353_a)
先頭要素とそれ以外をパターンマッチで分解し、先頭要素より大きい要素を見つけます。
```haskell
main :: IO ()
main = do
n <- getInts
hs <- getInts
let (h : hs') = hs
case findIndex (> h) hs' of
Nothing -> print (-1)
Just i -> print $ i + 2
```
## [B - AtCoder Amusement Park](https://atcoder.jp/contests/abc353/tasks/abc353_b)
一つのグループに収容できる人数の上限が $K$ と決まっているので、貪欲に $K$ 以内に収まるならそのグループに $A_i$ を加えていきます。
グルーピングの関数を作って計算しました。
途中 `sum` するところを `length` に間違えていて、5分ほど悩みました 😅
こういうミスは良くないですね。
```haskell
main :: IO ()
main = do
[n, k] <- getInts
as <- getInts
let res = foldl' f [[]] as
where
f (vs : vss) a
| sum vs + a <= k = (a : vs) : vss
| otherwise = [a] : vs : vss
print $ length res
```
## [C - Sigma Problem](https://atcoder.jp/contests/abc353/tasks/abc353_c) (upsolve)
今回の山場です。終わってみれば、D や E よりもこれが一番難しかったです。
一見すると、単に $\sum\sum(A_i + A_j)$ を $\mod 10^8$ でやれば良い問題に見えるのですが、最終的な総和は $\mod 10^8$ はしないので
計算対象の空間全体を $\mod 10^8$ に写像してしまうと答えが合いません。
というわけで、ペアにすると $10^8$ を超えてしまうものとそうでないものを選り分けて考える必要があります。
まず、先に $10^8$ のことを忘れて $\sum\sum{(A_i + A_j)}$ を計算することを考えます。
これは割と典型で、続くD 問題でも同様の考え方が必要になります。
例えば $(3, 1, 4 ,5 ,9)$ という数列があったとき、
- $3$ とペアになるのは$(3, 1), (3, 4),(3, 5), (3, 9)$
- $1$ とペアになるのは $(1, 4), (1, 5), (1, 9)$ です
- $4$ 以降も同様に考える
となります。
このペアの総和を計算するわけですが、例えば $i = 1$ の $A_i = 3$ のケースを考えると
$3 + 1 + 3 + 4 + 3 + 5 + 3 + 9 = 31$
となります。これは
$3 \times 4 + (1 + 4 + 5 + 9) = 31$
と式変形できて、結果 $(1 + 4 + 5 + 9)$ が出てきます。
これは数列 $A$ の累積和として表現できるので $O(1)$ で計算可能です。
これがペアの総和を求める計算の基本になります。
問題は $10^8$ の方です。
結論、ペアにすると $10^8$ 以上になる組み合わせの個数を数えて、その個数分 $10^8$ を引くという考え方を使います。
この問題の制約上、$\mod 10^8$ をとったときに、mod を周期と考えたとき $2$ 周以上するペアはありません。
$A_i$ が $10^8$ 未満なので、二つ足して $10^8$ を超えることはあっても、$2 \times 10^8$ を超えることはないです。
よって、$A_i + A_j$ が $10^8$ 未満の場合は、$A_i + A_j$ そのままでよく、$A_i + A_j$ が $10^8$ を超える場合は mod の1周期分つまり $10^8$ を引いてやればよいことになります。
ここに気づくことができるかが、問われる問題でした。
というわけで、二つ足したら $10^8$ になるペアの数を数えたい。
ところで、この問題の式は単に二つの値の組み合わせを計算することになり、問題で与えられている数列の並び順には意味がありません。
並び順に意味がないときは、ソートするとかバケットを取るなどすると、道が拓けることは多いです。
ソートすることで単調性が生まれるので、$A_i$ を固定して二分探索してやると、足して $10^8$ を超える相手がどこからなのか境界を引くことができます。
これで全て道具がすべて揃いました。
ソートする、累積和とる、$A_i$ を固定して計算する、二分探索で足すと $10^8$ を超えるペアの個数を数えて最後に引く。
```haskell
prefixSum :: (IArray a e, Ix i, Num e) => (i, i) -> [e] -> a i e
prefixSum b = listArray b . scanl' (+) 0
main :: IO ()
main = do
n <- getInt
as_ <- getInts
let as = listArray @UArray (1, n) $ sort' as_
s = prefixSum @UArray (1, n + 1) $ elems as
xs = [a * (n - i) + s ! (n + 1) - s ! (i + 1) | (i, a) <- assocs as]
ys = [n - ok | (i, a) <- assocs as, let (ok, _) = bisect2 (i, n + 1) (\j -> a + as ! j < 10 ^ 8)]
print $ sum xs - (sum ys * 10 ^ 8)
```
二分探索で $10^8$ 以上のペアを選り分けて、というところまでは考察できたのですが、 mod は周期ということにとらわれて「$10^8$ をその個数分引けば良い」というところになかなか気がつくことができず、時間内に解くことができませんでした、無念 😖
## [D - Another Sigma Problem](https://atcoder.jp/contests/abc353/tasks/abc353_d)
こちらの問題も C 問題同様 $A_i$ を固定して考えてみると、例えば入力例 $1$ において $i = 1$ のとき
$f(3, 14) + f(3, 15) = 314 + 315$
となっていますが、これを
$300 \times 2 + (14 + 15)$ と考えると、やはり累積和が出てきます。
ここで $f(x, y)$ についてもう少し具体例をみていくと
$f(3, 14) = 314 = 300 + 14 = 3 \times 10^2 + 14$
$f(14, 15) = 1415 = 1400 + 15 = 14 \times 10^2 + 15$
$f(14,300) = 14300 = 14000 + 300 = 14 \times 10^3 + 300$
となって、$y$ の桁数によって $x$ にかかる $10^k$ の $k$ の値が決まることがわかります。
$y$ の桁数ごとに $10^k$ が変わってしまうので、単純には先に見た累積和を括り出す考え方にもっていくのは難しい。
しかし見方を変えると、たとえば数列 $A$ に含まれる数字の桁数がすべて $2$ 桁などに揃っていたら、それができるわけです。
$A_i$ は $10^9$ までなので、$A_i$ の桁数は $1 \ldots 10$ 桁までしかありません 💡
$k = 1 \ldots 10$ まで $A_i$ を桁数ごとに分離して計算してやれば、累積和を使って計算していくことができます。
```haskell
prefixSum :: (IArray a e, Ix i, Num e) => (i, i) -> [e] -> a i e
prefixSum b = listArray b . scanl' (+) 0
main :: IO ()
main = do
n <- getInt
as <- getInts
let xs = [(a, length digits) | a <- as, let digits = toDigits 10 a]
ss = listArray @Array (1, 10 :: Int) [prefixSum @Array (1, n + 1) [bool 0 (toIntMod a) (k == d) | (a, k) <- xs] | d <- [1 .. 10]]
ks = listArray @Array (1, 10) [prefixSum @UArray (1, n + 1) [bool 0 1 (k == d) | (_, k) <- xs] | d <- [1 .. 10]]
res =
[ (toIntMod a * 10 ^ d) * toIntMod (k ! (n + 1) - k ! (i + 1)) + s ! (n + 1) - s ! (i + 1)
| (i, a) <- indexed 1 as,
d <- [1 .. 10],
let s = ss ! d
k = ks ! d
]
IntMod ans = sum res
print ans
```
当初 $10^9$ ということが頭にあって桁数を $1 \ldots 9$ までと考えてしまい、サンプル $2$ の答えが合わずに頭を抱えました。
が、一度落ち着いてナイーブに入力例 $2$ を計算し $\mod 998244353$ を外した総計を見てみたところ原因がわかって修正できました。
ここで落ち着いて処理できたのはよかったです。
1ペナは、IntMod を当てる対象を間違えていたのが原因です。これはすぐに対応出来ました。
## [E - Yet Another Sigma Problem](https://atcoder.jp/contests/abc353/tasks/abc353_e) (upsolve)
改めて翌日に取り組みました。
最長共通接頭辞 (Longest Common Prefix) の問題ですが、文字列の共通接頭辞に関しては (競技プログラミングに限らず) まずトライ木を考えてみるというのが定石としてあると思います。
情報検索やかな漢字変換などの自然言語処理、あるいは Wiki のキーワードリンクなどのアプリケーションで、辞書にある巨大な文字列集合から効率的に入力文字列とのマッチングを行いたいという問題がテーマになることがあります。Common Prefix Search (共通接頭辞検索) と言われますが、Common Prefix Search はトライ木を考えるのが出発点です。だいぶ昔のことですが、過去に勉強したことがあります ([Aho Corasick 法 - naoyaのはてなダイアリー](https://naoya-2.hatenadiary.org/entry/20090405/aho_corasick) )
というわけで、この問題もトライ木で考察すると良いです。
入力例 $1$ の `ab abc arc` は接頭辞を書き出すと以下となり、これをトライ木にしたのが図です。
```
ab -> a, ab
abc -> a, ab, abc
arc -> a, ar, arc
```
![[IMG_0990.jpeg|600]]
共通接頭辞の特徴として、例えば $S_i$ と $S_j$ において `ab` が共通接頭辞になっている場合、当然 $S_i$ と $S_j$ の `a` も共通接頭辞になります。
よって各接頭辞の寄与数を考える際、長さ $1$ の `a` の寄与数を考えたら、長さ $2$ の `ab` における長さ $1 + 1 = 2$ のうちの $1$ の分の寄与数はもう計算済みと考えて、$1 → 2$ に長さが増えたことによる寄与数だけを考えてもよいことになります。
···ここの説明がなかなか難しいのですが、長さのことを忘れて各接頭辞が何回出現するかを独立に考えていくだけで総計したときに辻褄が合うということ言っています。
長さ $1$ の接頭辞として `a` が $3$ 個あるとき、そこから $2$ つ選ぶときの寄与数は $_3C_2 = 3$ です。
長さ $2$ の接頭辞として `ab` が $2$ 個あるとき、そこから $2$ つ選ぶときの寄与数は $_2C_2 = 1$ です。
...
という風に考えてよく、結局、全文字列から一つのトライ木を作って各接頭辞の出現回数 $n$ を調べて $_nC_2$ をとって全部足せば答えになります。
### ハッシュによる実装
やりたいことは接頭辞の出現回数を数えるという単純なことなので、トライ木を作るとか面倒なことをせずに済む方法がないか考えてみます。
```
abcde -> a, ab, abc, abcd, abcde
```
と、各文字から接頭辞を全部抽出してバケットを作ればよいわけです。
これは例えば Haskell なら `tails . reverse` で簡単に作ることができます。
しかし `tails` 関数はリストを作る計算量だけなら $O(n)$ ですが生成された接頭辞の長さは元になる文字列 $S_i$ の長さ $n$ の2乗に比例してしまい、入力が大きいと、生成された接頭辞すべてを走査するところで TLE してしまいます。
裏を返せば、各接頭辞をより短く表現することができれば TLE を避けられます。というわけでハッシュ化です。
文字列のハッシュといえばローリングハッシュ、通称ロリハですね。これを使いましょう。
ロリハで全接頭辞のハッシュを生成してバケットを作り $_nC_2$ を求めて総和をとると答えになります。
```haskell
main :: IO ()
main = do
n <- getInt
ss <- BS.words <
gt; BS.getLine
let res =
[ [getRH2 h (1, i + 1) | i <- [1 .. l]]
| s <- ss,
let l = BS.length s
h = rollingHash2' (1, l) s
]
bucket = HM.fromListWith (+) $ map (,1 :: Int) (concat res)
print $ sum (HM.map nc2 bucket)
```
[提出 #53400035 - AtCoder Beginner Contest 353](https://atcoder.jp/contests/abc353/submissions/53400035)
あっさり解けてしまいました 😉
### トライ木による実装
この問題の場合ハッシュを使うと簡単ですが、真面目にトライ木を作ってももちろん AC できます。
```haskell
data Trie v e = Trie
{ children :: Map.Map v (Trie v e),
count :: e
}
deriving (Show, Eq, Ord)
emptyTrie :: (Num e) => Trie v e
emptyTrie = Trie {children = Map.empty, count = 0}
insertTrie :: (Ord v, Num e) => [v] -> Trie v e -> Trie v e
insertTrie [] trie = trie
insertTrie (x : xs) trie = trie {children = Map.alter f x (children trie)}
where
f Nothing = Just (insertTrie xs emptyTrie {count = 1})
f (Just subTrie@Trie {count}) = Just (insertTrie xs (subTrie {count = count + 1}))
dfs' Trie {children, count} = do
modify' (+ nc2 count)
for_ (Map.elems children) $ \subTrie ->
dfs' subTrie
main :: IO ()
main = do
n <- getInt
ss <- words <gt; getLine
let trie = foldr insertTrie emptyTrie ss
k = execState (dfs' trie) 0
print k
```
構築したトライ木が保持している各接頭辞の出現回数をトラバースするところは State モナド + 手続き DFS でやりました。
`Trie` 型を Foldable にして fold で畳み込むとかできるとかっこよさげですが、ここまでの実装で疲れて力尽きました。
再帰的な木構造の実装は認知負荷が高く、短時間で実装するのが難しいですね。
### 追記 Foldable にました
```haskell
data Trie v e = Trie
{ children :: Map.Map v (Trie v e),
count :: e
}
deriving (Show, Eq, Ord)
emptyTrie :: (Num e) => Trie v e
emptyTrie = Trie {children = Map.empty, count = 0}
insertTrie :: (Ord v, Num e) => [v] -> Trie v e -> Trie v e
insertTrie [] trie = trie
insertTrie (x : xs) trie = trie {children = Map.alter f x (children trie)}
where
f Nothing = Just (insertTrie xs emptyTrie {count = 1})
f (Just subTrie@Trie {count}) = Just (insertTrie xs (subTrie {count = count + 1}))
instance Foldable (Trie v) where
foldMap f Trie {children, count} = f count `mappend` foldMap (foldMap f) children
main :: IO ()
main = do
n <- getInt
ss <- words <gt; getLine
let trie = foldr insertTrie emptyTrie ss
print $ foldl' (\acc count -> acc + nc2 count) 0 trie
```
木が保持している接頭辞の出現回数を `foldl'` で畳み込むことができてよいです。
## 追記2 トライ木を Functor にする
更に Functor にして `fromListTrie` でリストからトライ木を生成できるようにしました。
結果、
```haskell
main :: IO ()
main = do
n <- getInt
ss <- words <gt; getLine
print $ sum (nc2 <gt; fromListTrie ss)
```
これだけで実装完了です。
```haskell
data Trie v e = Trie
{ children :: Map.Map v (Trie v e),
count :: e
}
deriving (Show, Eq, Ord, Functor)
instance Foldable (Trie v) where
foldMap f Trie {children, count} = f count `mappend` foldMap (foldMap f) children
emptyTrie :: (Num e) => Trie v e
emptyTrie = Trie {children = Map.empty, count = 0}
fromListTrie :: (Ord v, Num e) => [[v]] -> Trie v e
fromListTrie = foldr insertTrie emptyTrie
insertTrie :: (Ord v, Num e) => [v] -> Trie v e -> Trie v e
insertTrie [] trie = trie
insertTrie (x : xs) trie = trie {children = Map.alter f x (children trie)}
where
f Nothing = Just (insertTrie xs emptyTrie {count = 1})
f (Just subTrie@Trie {count}) = Just (insertTrie xs (subTrie {count = count + 1}))
searchTrie :: (Traversable t, Ord v, Num e) => Trie v e -> t v -> t (v, Maybe e)
searchTrie trie = snd . mapAccumL f trie
where
f Trie {children} c = do
case Map.lookup c children of
Nothing -> (emptyTrie, (c, Nothing))
Just subTrie -> (subTrie, (c, Just (count subTrie)))
main :: IO ()
main = do
n <- getInt
ss <- words <gt; getLine
print $ sum (nc2 <gt; fromListTrie ss)
```
## 感想など
C が想定以上に難しいとそこで躓き、後続の問題も総崩れになるというのがいつものパターンです。
今回もそれに近い状況になりました。
が、過去の反省から C に執着しすぎず損切りして D を通す、ということはできて多少ましな状況に戻すことはできました。
より実践を積んで、C で躓いたときの対処法を身体化したいところですね。
C 問題以外でも、B や D でもやや沼るなど精彩を欠くところもありました。
当日 TSKaigi に出ていたこともあり、ややバタバタしていてコンテスト前の有酸素運動もさぼってしまいました。
その辺が影響したかもしれないです。
こういうところをさぼらずルーチンでこなして、100% の力が発揮できるように持っていきたいところです。
1200 が見えてきていますが、ここからの勾配はなかなかきつそうです。コツコツやっていこうと思います。