# ABC405 振り返り
- [AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY） - AtCoder](https://atcoder.jp/contests/abc405)
- ABCDE 5完 (1286) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc405)
![[スクリーンショット 2025-05-12 9.18.43.png]]
ABC405 でした。
A 〜 D まではスムーズに解けましたが、E が数学問題で苦戦。
- A (灰) ··· 場合分け
- B (灰) ··· 多重集合でシミュレーションしました
- C (灰) ··· 累積和
- D (茶) ··· E から BFS して各マスへの距離を求める。各マスから距離 $-1$ になってる四方を探して方向を確定する
- E (水) ··· 一個目のブドウを境界に、左と右に分けて考えて二項係数で計算。$C$ は全探索
なんとか 86 分に解くことができましたが、冷えました。この E を解いても冷える、という程度のレートまで来てしまいました。
## [A - Is it rated?](https://atcoder.jp/contests/abc405/tasks/abc405_a)
適切に場合分けをすれば良いです。Haskell ならパターンマッチと `inRange` を使うと楽です。
```haskell
solve 1 r = inRange (1600, 2999) r
solve 2 r = inRange (1200, 2399) r
main :: IO ()
main = do
[r, x] <- getInts
printYn $ solve x r
```
## [B - Not All](https://atcoder.jp/contests/abc405/tasks/abc405_b)
$N$ が高々 $100$ 程度と小さいのでナイーブに $O(N^3)$ とかの実装でも良かったのですが、最初に思いついたのが多重集合を使うものでした。
ので、それで殴ります。
多重集合 IntMultiSet に $A$ を入れて、$A$ の末尾の数字から順に削除していきます。集合の状態遷移過程は全て残しておきます。
集合に含まれる数の種類数は $O(1)$ で取得できるように実装しているので、集合の状態遷移過程をすべて数の種類数に写像します。
その上でサイズ $M$ を切る箇所がどこかを突きとめればよいでしょう。
```haskell
main :: IO ()
main = do
[_, m] <- getInts
as <- getInts
let ss = scanl' (flip deleteMS) (fromListMS as) (reverse as)
res = map distinctSizeMS ss
print $ (length . takeWhile (>= m)) res
```
## [C - Sum of Product](https://atcoder.jp/contests/abc405/tasks/abc405_c)
$A_1A_2 + A_1A_3+A_1A_4+ \cdots$ となるのを $A_1$ でくくると $A_1 (A_2 + A_3 + A_4 \cdots) + A_2 (A_3 + A_4 + A_5 + \cdots)$ となります。
括弧の中身は区間和になっているので、累積和の出番です。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let s = listArray @UArray (1, n + 1) $ scanl' (+) 0 as
res = [a * (s ! (n + 1) - s ! (i + 1)) | (i, a) <- indexed 1 as]
print $ sum res
```
係数と区間和は一つズレてるだけなのでよりエレガントに以下のように書けます。gksato さんの回答を参考にしました。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
let res = sum $ zipWith (*) as (scanl' (+) 0 as)
print res
```
## [D - Escape Route](https://atcoder.jp/contests/abc405/tasks/abc405_d)
BFS の匂いがします。
ただしスタート地点は任意のグリッドのマスですが、ゴールは `E` が置かれたマスに限定されています。
こういう場合はゴール側を開始点に BFS すると各マス、つまりスタート地点までのパスを明らかにすることができます。
それは良いとして、 E まで進むための方向をどう確定させるか。
E からの各マスへの距離を求めたのち、各マスから距離が $-1$ される方向に進んでいけば E に辿り着けることを利用します。
というわけで多始点 BFS で距離を求めたのち、各マスの四方を全探索して距離が自身から $-1$ されるマスが進むべき方向と確定させます。
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)]
main :: IO ()
main = do
[h, w] <- getInts
grid <- getCharGrid ((1, 1), (h, w))
let dist = bfs f (-1) (bounds grid) [(s, 0) | s <- findArrayIndices (== 'E') grid]
where
f v = [u | d <- lrud, let u = v + d, grid !? u == Just '.']
grid' = listArray @UArray (bounds grid) $ map (resolve dist) (indices grid)
printCharGrid grid'
resolve dist v
| dist ! v == 0 = 'E'
| dist ! v == -1 = '#'
| otherwise =
head
[ c
| (c, d) <- zip ['<', '>', '^', 'v'] lrud,
let u = v + d,
dist !? u == Just (dist ! v - 1)
]
```
BFS の実装の方に手を入れて、都度方向を記録するという実装もありそうです。
本番でそれをやろうとしましたが Haskell でそのあたりの実装を始めると沼りそうだという直感があり、どうしたもんかと少し考えたところ距離さえあれば方向が定められることに気がつき沼回避です。
## [E - Fruit Lineup](https://atcoder.jp/contests/abc405/tasks/abc405_e)
4つの果物に片側の順序制約がある問題です。構造を見抜くのに頭を使いますね。
まず入力例 $1$ のケースをすべて書き出して眺めてみます。
![[IMG_4051.jpeg|800]]
なんとなくわかることは
- A, B は比較的左より··· 前半に登場する
- D はだいたい右より··· 後ろに近い位置に登場する
- **D よりも後ろには C しか出てこない、裏返すと A と B は D より左にしか出てこない**
ということが見て取れます。特に最後が重要な発見です。
制約を改めてみてみると
A ◁ C
A ◁ D
B ◁ D
となっていて、A と B は片側制約の左側にしか出てこない。C と D は右にしかでてこない。
D を境界にすると、A と B は D よりも必ず左側にでてきて、C は唯一、左と右両方に出てくることができる。そしてこの観点では C がもっとも自由度が高い。
ということが分かります。この構造を使って、二項係数 $_nC_r$ の計算に持ち込むことを考えます。
先の発見から **$D$ 個あるブドウの1個目を確定し、その左と右に分けて考えると、左と右で考えることが減ってよさそうです。**
左側に置くバナナ $C$ の数を $x$ とします。すると左側には合計 $A + B + x$ 個の果物を並べることになりますが、ここで A ◁ C なので $A$ と $C$ の並べ方としては
```
[A A … A | C C … Cx]
```
となるところまでは確定します。あとはここに $B$ を挿入する場合の数を求めることになるので
$_{A + B + x}C_{B}$
で求められます。
一方、右側はブドウ一個は確定しているので $C - x$ 個のバナナと $D - 1$ 個のブドウの並べ方です。これは $C - x$ 個のバナナが並んでるところに $D - 1$ 個のブドウを差し込む場合の数なので
$_{C - x + D - 1}C_{D - 1}$
となります。
左側、右側をそれぞれ独立に考えましたがこの二つの場合の数は積で結合できます。
パラメータ $x$ がありますが、$0 \leq C \leq 10^6$ 程度なので、これは全探索してしまえばよいでしょう。
というわけで
$\sum_{x = 0}^{C}{_{A+B+x}C_B \times _{C-x+D-1}C_{D - 1}}$
となります。
なお $_nC_r$ このを求めるとき、$_nC_r$ の計算自体が $O(r)$ かかっていると間に合いません。二項係数を高速に計算する実装 (拙作は `combMod`) が必要です。
```haskell
main :: IO ()
main = do
[a, b, c, d] <- getInts
let res =
[ c1 * c2
| x <- [0 .. c],
let c1 = combMod (a + b + x) b
c2 = combMod (c - x + d - 1) (d - 1)
]
IntMod ans = sum res
print ans
```
はじめは DP で考察していましたが延々と考えても、良い感じの狭い状態空間が思いつかない。
DP でないとしたら $\bmod 998244353$ は何のサインだろうなあと考え $_nC_r$ の $\bmod 998244353$ だろうとメタ読みし、場合の数に切り替えて考察しました。