# ABC401 振り返り
- [AtCoder Beginner Contest 401 - AtCoder](https://atcoder.jp/contests/abc401)
- ABCE 4完 (1280) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc401)
![[スクリーンショット 2025-04-13 13.22.43.png]]
ABC401 でした。
- A (灰) ··· `inRange (200, 299) s` で判定すれば良い
- B (灰) ··· ログイン状態を Boolean で状態管理して、仕様通りに実装する
- C (灰 or 茶) ··· セグメント木 or BIT で殴ると簡単
- D (緑 or 水) ··· 難しい。文字が確定するところを先に確定しておいて、残った `?` を場合分けで処理する
- E (水) ··· 主客転倒していもす法。ある頂点 $v$ は自身に隣接する頂点 $u$ のうち $u < v$ なる頂点に対してお荷物になっている。これをいもす法で表現して、操作回数の寄与を $u$ に配る。
※ 難易度は推定
D 問題が難しく、結果解けず。少し考察してみたものの埒が明かない。その時点で順位表をみたところ、D を飛ばして E を解いている人がそこそこいたので、自分も D 飛ばしで E を解きました。E もそこそこ難しく時間がかかりましたが、D のような嫌な難しさではなかったです。
改めて D に戻って 30分かけましたが、良い解法には至らずでした。
パフォーマンスは 1280 で、レートは -8 です。
D を飛ばしましたが結果は水色パフォーマンスで、軽傷で済みました。
1280 出してもレートが下がるというのは、半年前に比較するとだいぶハードルが高くなったものです。
## [A - Status Code](https://atcoder.jp/contests/abc401/tasks/abc401_a)
Haskell なら $200$ 以上 $299$ 以下、は `inRange` 関数を使うとその通りに実装できます。
```haskell
solve s
| inRange (200, 299) s = "Success"
| otherwise = "Failure"
main :: IO ()
main = do
s <- getInt
putStrLn $ solve s
```
## [B - Unauthorized](https://atcoder.jp/contests/abc401/tasks/abc401_b)
ログイン状態を True / False の Boolean で管理しながら、仕様通りに実装。
パターンマッチを使うと楽に実装できます。
```haskell
main :: IO ()
main = do
n <- getInt
ss <- replicateM n getLine
let (_, res) = mapAccumL f False ss
where
f True "logout" = (False, 0 :: Int)
f True _ = (True, 0)
f False "private" = (False, 1)
f False "login" = (True, 0)
f False _ = (False, 0)
print $ sum' res
```
## [C - K-bonacci](https://atcoder.jp/contests/abc401/tasks/abc401_c)
$A_i$ の値が $K$ 個前の $A_{i - K}$ から一つ前 $A_{i - 1}$ までの区間和で決まる、という計算。
本番ではメモ化再帰で一つ前までの累積和をキャッシュしながら計算する実装をしましたが、セグメント木や Binary Indexed Tree を使うほうが簡単だと思いました。いわゆるセグ木で殴る案件。
セグ木 or BIT なら、ほぼ問題文の通りシミュレーションするだけで解けます。
なお $10^9$ で答えを割れ、というのはいわゆる modint を使えば良いです。
```haskell
main :: IO ()
main = do
[n, k] <- getInts
seg <- newST @IOArray (+) (0 :: IntMod) (1, n)
for_ [0 .. n] $ \i -> do
if i < k
then updateST seg i (const 1)
else do
acc <- rangeQueryST seg (i - k) i
updateST seg i (const acc)
(IntMod x) <- readST seg n
print x
```
## [D - Logical Filling](https://atcoder.jp/contests/abc401/tasks/abc401_d) (upsolve)
これは難しかったです。とりあえず公式解説通りに upsolve
「Logical Filling」というタイトルは、場合分けを示唆していたんですかね。
DP や fold のような状態計算でなんとかするのか? という方針に執着してしまって、場合分けするという方針に思い至らず。
先に確定できる文字を確定してしまう、というところまでは分かったのですが、そこから貪欲に `o` を最大化したときの `o` の個数 $M$ と $K$ を比較するという点が、全然思いつかなかったです。
こういう問題は苦手です 😅
```haskell
main :: IO ()
main = do
[n, k] <- getInts
s <- getLine
-- 左右から見て確定できる文字は確定する。確定しない箇所は ? にする
let s1 = scanl' f '_' s
where
f _ '.' = '.'
f _ 'o' = 'o'
f 'o' '?' = '.'
f _ '?' = '?'
s2 = reverse $ scanl' f '_' (reverse s)
where
f _ '.' = '.'
f _ 'o' = 'o'
f 'o' '?' = '.'
f _ '?' = '?'
s' = zipWith f (tail s1) (init s2)
where
f '?' '?' = '?'
f '?' b = b
f a '?' = a
f a b
| a == b = a
| otherwise = '?'
-- s' の ? を可能な限り貪欲に o にしたら最大で o が何個になるか数える
let s'' = scanl' f '_' s'
where
f _ 'o' = 'o'
f _ '.' = '.'
f 'o' '?' = '.'
f _ '?' = 'o'
m = countBy (== 'o') s''
-- 場合分け
let res =
if
| countBy (== 'o') s' == k -> map (\c -> if c == '?' then '.' else c) s'
| m > k -> s'
| m == k ->
concat
[ vs
| (c, l) <- rle s',
let vs
| c == '?' && odd l = take l (cycle "o.")
| otherwise = replicate l c
]
| m < k -> error "Invalid"
putStrLn res
```
## [E - Reachable Set](https://atcoder.jp/contests/abc401/tasks/abc401_e)
いろいろな解き方がありそうですが、主客転倒 + いもす法で解きました。
過去問の傾向から、この手のグラフの問題··· 各頂点が離れた広範囲の別の頂点に影響する構造の問題は、主客転倒という直感があります。
もとい、まずサンプル 1 のグラフで考えてみます。
例えば $k = 1$ のときは頂点 $1$ を残し、削除操作する頂点は $(2, 5)$ の 2 つですが、いずれも頂点 $1$ に隣接しています。
頂点 $2$ は、隣接頂点である頂点 $1$ に対して操作回数 $+1$ だけ寄与する、と考えることができます。
頂点 $5$ も同じく、隣接頂点である頂点 $1$ に対して操作回数 $+1$ だけ寄与する、と考えることができます。
頂点 $1$ には、この $2$ と $5$ からの寄与が集まって来て、結果 $k = 1$ のときの操作回数は 2 と結論付けられます。
次に $k = 2$ の場合も同様に考えると頂点 $2$ の隣接頂点 $(3, 4, 5)$ からの寄与によって操作回数 3 となります。
どうやら各頂点が隣接頂点に対して寄与する··· という構造になっていそうです。
![[IMG_3537.jpeg|600]]
これだけなら単純ですが $k = 3$ のケースを考えると、少し異なる傾向が見えます。
頂点 $3$ に対して寄与するのは $4, 5, 6$ の 3頂点ですが、このうち $5$ と $6$ は $3$ に隣接していないにも関わらず、$3$ に対して奇与しています。この寄与の構造を見抜く必要があります。
![[IMG_3539.jpeg | 600]]
サンプル 1 はグラフとして単純すぎるのでもう少し異なる形のグラフをみてみます。
以下のグラフで、頂点 $6$ がどこに寄与するかを考えてみます。頂点 $3$ に寄与するのは明らかですが、$4$ や $5$ にも寄与しそうです。
![[IMG_3538.jpeg | 600]]
$k = 1$ のときは $2$ が削除されれば OK で、$6$ は直接は削除されない
$k = 2$ のときは $3$ が削除されれば OK で、$6$ は直接削除されない
$k = 3$ のとき $6$ は削除される
$k = 4$ のとき $6$ は隣接していないが、$3$ を残しつつ $6$ を削除する必要がある
$k = 5$ のとき $6$ は隣接していないが、$3$ を残しつつ $6$ を削除する必要がある
$k = 6$ のとき $6$ は削除しない
$k = 7$ のとき $6$ は削除しない
となり、結果 $k = 3, 4, 5$ のとき $6$ は削除対象となる、つまり $6$ は頂点 $3, 4, 5$ に対して奇与することがわかります。
もう少しこれを言語化してみると「頂点 $6$ は自分よりも若い番号の頂点である $3$ を残したいとき、お荷物になっている」と言えます。
$3$ からみると、$6$ は当然削除対象です
$4$ からみると隣接はしておらず一見関係なさそうに見えるが、$3$ と繋がっていて、その $3$ は残す必要がある。よって $k = 4$ のときに $6$ は削除対象
$5$ からみると隣接はしておらず一見関係なさそうに見えるが、$3$ と繋がっていて、その $3$ は残す必要がある。よって $k = 5$ のときに $6$ は削除対象
となります。
このあたりから構造を一般化することができます。
「頂点 $v$ は、自身に隣接する頂点 $u$ のうち、$u < v$ なる頂点 $u$ から $v - 1$ までの頂点に対して $1$ ずつ操作回数を寄与する。言い換えると、$u$ の中の一番小さな頂点 $u_{min}$ から $v - 1$ まで、$1$ ずつ操作回数を寄与する」と言えます。
頂点 $v$ は自身に隣接する頂点 $u$ の中で、自分より小さいものに対してお荷物の存在になっていてるわけです。
このグラフの例でいくと頂点 $6$ には $(3, 7)$ が隣接しており、結果 $6$ は $3 \cdots 5$ に対して 1 ずつ寄与します。
これは区間 $[3, 6)$ に対する寄与と考えることができます。
区間に対する寄与の実装は典型で、いもす法や遅延評価セグメント木で表現すると計算量的に効率よく実装できます。
というわけで
- グラフの隣接リストを作る
- 各頂点 $v$ ごとに、隣接する頂点 $u$ のうち $u < v$ な $u$ の最小 $u_{min}$ を見つける
- $[u_{min}, v)$ の区間に 1 寄与する
として、いもす法を行うことで各頂点 $v$ に集まる寄与数 ... 各 $k$ に対する答えが求められます。
ここまでで問題の大半は解けていますが、もう一つ考慮することがあります。
入力例 2 が分かりやすいのですが、例えば $k = 2$ で頂点 $(1, 2)$ を残したとき、必ずしも $1$ と $2$ が連結になっていないことがあります。この場合、問題文の条件「 頂点 $1$ から辺をたどって到達できる頂点の集合が、頂点 $1$ 頂点 $2, \ldots,$ 頂点 $k$ のちょうど $k$ 個からなる。」を満たさないので答えは $-1$ になります。
ここの判定は簡単で、Union-Find を用いて $k = 1 \cdots N$ まで固定しながら頂点 $v = k$ に対して隣接する頂点を Union-Find に加えていき、その頂点 $1$ が含まれるグループの連結成分数 $size$ を調べれば良いです。結果、$size = k$ なら先のいもす法で求めた寄与数が答えになるし、連結していなければ答えは $-1$ です。
```haskell
imos :: (Int, Int) -> [(Int, Int)] -> [Int]
imos (s, e) events = scanl1 (+) . elems $ accumArray @UArray (+) 0 (s, e) events
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getTuple
-- (1) いもす法で各頂点 v からの寄与数を計算する
let g = graph2 (1, n) uvs
s =
imos (1, n)
$ concat
[ if null us then [] else [(minimum us, 1 :: Int), (v, -1)]
| v <- [1 .. n],
let us = [u | u <- g ! v, u < v]
]
uf <- newUF @IOUArray (1, n) (-1)
-- (2) 頂点 1 との連結性を調べながら、連結している場合は (1) で求めた寄与数が答えとする
res <-
mapM
( \(k, cost) -> do
for_ [u | u <- g ! k, u < k] $ \u ->
unite uf k u
size <- getSizeUF uf 1
return $ if size == k then cost else (-1)
)
(indexed 1 s)
for_ res print
```