# ABC402 振り返り
- [東京海上日動プログラミングコンテスト2025（AtCoder Beginner Contest 402） - AtCoder](https://atcoder.jp/contests/abc402)
- ABCDE 5完 (1529) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc402)
![[スクリーンショット 2025-04-20 12.08.02.png]]
ABC402 でした。
- A (灰) ··· 大文字だけをフィルタする
- B (灰) ··· FIFO、待ち行列管理にキューを使う
- C (茶) ··· 料理 → {食材} の入力から 食材 → {料理} の転置インデックスを構築し、あとはシミュレーション
- D (緑) ··· 弦 $(A_i, B_i)$ の向きを一意に定める値として $A_i + B_i \mod N$ に写像する。それが同じ値になる組み合わせは平行。平行する組み合わせ数のの余事象が交差する組み合わせ数
- E (水) ··· bitDP + 期待値 DP、もらう DP で実装する。問題に再チャレンジできる、というところは `(+)` で繋ぎ、最適ルートは `max` で選択する
開始早々 Haskell の環境がうまく動かず A 問題の提出に遅れるなどアクシデントがありましたが、終わってみれば 5 完でパフォーマンス 1529 と良好でした。レート的には前回の負け分を取り戻すことができました。
E 問題が今回の山場でしたが、ここ最近、期待値 DP や後退解析の問題を集中的に解いて DP での計算の方向 (後ろから計算するとかそういう話) についての理解を深めていたため、盛大に沼ることもなく、比較的スムーズに解くことができました。
## [A - CBC](https://atcoder.jp/contests/abc402/tasks/abc402_a)
$S$ を大文字だけでフィルタして出力します
```haskell
main :: IO ()
main = do
s <- getLine
putStrLn [ c | c <- s, isUpper c ]
```
## [B - Restaurant Queue](https://atcoder.jp/contests/abc402/tasks/abc402_b)
求められている待ち行列の管理方法は FIFO です。キューを使います。
Haskell なら Data.Sequence を使えば良いです。
なお `pushBackSeq` や `popFrontSeq` は Data.Sequence の API が使いづらいのでラップした関数です
```haskell
main :: IO ()
main = do
q <- getInt
qs <- replicateM q getInts
foldForM_ Seq.empty qs $ \queue query -> do
case query of
[1, x] -> return $ pushBackSeq queue x
[2] -> do
let (x, queue') = fromJust $ popFrontSeq queue
print x
return queue'
_ -> error "!?"
```
素の API で書くと以下ですね
```haskell
main = do
q <- getInt
qs <- replicateM q getInts
foldForM_ Seq.empty qs $ \queue query -> do
case query of
[1, x] -> return $ queue |> x
[2] -> do
let (x :<| xs) = queue
print x
return xs
_ -> error "!?"
```
## [C - Dislike Foods](https://atcoder.jp/contests/abc402/tasks/abc402_c)
入力で与えられているのは (料理 => {食材}) の対応です。
一方、$B_1, B_2, \cdots B_N$ は食材を対象にしています。
入力のままの構造では食材から料理を見つけるのに適していません。
食材から料理を見つけやすい構造、つまり (食材 => {料理}) の対応にするデータ構造すなわち転置インデックスを作れば良いです。これがあれば、$B_i$ が進むたび、どの料理に対して影響があるかを効率的に見ていくことができるようになります。
あとは、各料理ごとに残っている苦手な食材の状態を管理し、$B_i$ を進めながら都度、転置インデックスを参照しながらその状態を更新していけば OK
本番では料理ごとの残り苦手食材数を整数で管理していましたが、以下は敢えて集合で管理しています。
こちらの方がよりシミュレーションに近い動きなので、実装の認知負荷がやや低いかなと思いました。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
ass <- replicateM m $ do
(_ : as) <- getInts
return as
bs <- getInts
dishes <- newListArray @IOArray (1, m) [IS.fromList as | as <- ass]
acc <- newIORef Set.empty
let g = graph (1, n) [(a, i) | (i, as) <- indexed 1 ass, a <- as]
for_ bs $ \b -> do
for_ (g ! b) $ \i -> do
modifyArray dishes i (IS.delete b)
s <- readArray dishes i
when (IS.null s)
$ modifyIORef acc (Set.insert i)
print =<< Set.size <
gt; readIORef acc
```
## [D - Line Crossing](https://atcoder.jp/contests/abc402/tasks/abc402_d)
$N$ 本の直線のうち、交差しているものの組み合わせ数を考えます。
平行なものの組み合わせがわかれば、余事象から交差しているものの組み合わせ数も得られます。
点 $A$ と点 $B$ を通る弦 $AB$ の傾きは、$AB$ の中点から円の中心に向かって引かれた直線に必ず垂直になります。
従って各 $AB$ の傾きは、中点 $AB$ の位置によって特徴付けられます。
この問題では各点の座標は分かっていませんが点は等間隔に並んでいるので $\frac{A_i + B_i}{2}$ で求めることができそう、さらに円環になっていることからその $\bmod N$ を取れば良いことがわかります。加えて比較にあたっては $2$ で割っていることは無視できるので、結論
$f(A_i, B_i) = A_i + A_b \mod N$
と写像することで、各直線 $(A_i, B_i)$ の特徴量が得られます。
あとは同じ特徴量の値になる値の出現頻度の $_nC_2$ を取ることで、2つ選んだときに平行になる組み合わせ数 $x$ が分かります。
そして $M$ 本から2つ選んだときの組み合わせ数 $_MC_2$ からこの $x$ を引くことで、余事象である交差する組み合わせ数が得られます。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
vs <- replicateM m getTuple
let bucket = toBucket (0, n - 1) [k | (a, b) <- vs, let k = (a + b) `mod` n]
x = sum . elems $ amap nc2 bucket
print $ nc2 m - x
```
なお考察の思考プロセスとしては
- 直線の交差を考える問題は、傾きがポイントになることが多い。直線を傾きもしくは傾きと一意に対応する値に写像できないか考える
- 特にこの問題は $1 \leq N \leq 10^6$ あるので、同じ傾きになるものをまとめ上げられると突破口が見えそう
というところが起点になっています。つまり、たくさんあるデータを特徴量に写像することでまとめ上げるという典型考察です。[ABC248 E - K-colinear Line](https://atcoder.jp/contests/abc248/tasks/abc248_e) なども同様の考え方で解けます。
Haskell は基本的に map / fold でデータを操作するよう体系が確立されているので、同様に思考も写像と集約で考えるように鍛えられていきます。
こういう問題をみると、まずは何かに写像するという 🧠 になります。
## [E - Payment Required](https://atcoder.jp/contests/abc402/tasks/abc402_e)
期待値 + bit DP の問題です。
DP の状態を考えること自体はさほど難しくないのですが、この問題はおそらく「配る DP」ではうまく解けない、というのが厄介なところ。「もらう DP」で実装する必要がありました。
まず、期待値を求める、制約が中途半端に小さい、$1 \leq N \leq 8$ あたりの制約から bit DP であることに当てにいっても問題ないでしょう。DP で管理すべき状態になりそうなのは「正解した問題の集合」と「その時点での残高」あたりでしょうか。
期待値 DP の考え方として、まず期待値が $0$ になる状態を探すのを起点にすると良いです。
期待値が $0$ になるのは「全ての問題を解いた」か「所持金的にもう解く問題が残っていない」状態です。
その状態からは解ける問題が残っていないので、その期待値を $0$ にし、真逆の状態...つまり「一つも問題を解いていなくて所持金 $X$ 持っている」状態の期待値を求める方向で考えます。
つまり $dp(S_{empty}, X)$ が求めたい状態。
さて、具体例として $5$ 問問題があったとして、そのうち $\{1, 3\}$ の問題に正解した状態を考えてみます。
ここから、次に $4$ 問目を狙うとします。
- 狙った $4$ 問目を解けなかったケース ··· $a =\{1, 3\} を解いていて、残高が \space C_4 \space 減った状態の期待値$
- 狙った $4$ 問目を解けたケース ··· $b = \{1, 3, 4\} を解いていて、残高が \space C_4 \space 減った状態の期待値$
となります。
図にすると以下の状態遷移です。
![[IMG_3661.jpeg|600]]
というわけで配るDP で上記の遷移を実装すれば答えは求められる、と思いたいところですがそうは問屋が卸さず。
**この問題では解けなかった問題には再チャレンジすることができます。**
ある状態から、どの問題を選択するかのルートの最適化は、同じ状態に到達してきたルートの max を取ることで可能なのは従来の DP 通りです。
しかしこの問題ではある状態から「解ける場合」「解けない場合」に二方向に遷移し、 **「解けない場合」は、同じ状態を何度も訪問し (残高だけは減ります) その期待値を累積しなければなりません。こちらの結合は max ではなく (+) での結合になります。**
つまり
- 配る DP（前向きに遷移を「流し込んでいく」手法）では、ある状態に来る異なる遷移ルート同士を必ず一種類の結合演算（`max` か `+` か）でまとめる
- しかしこの問題では同じルート内での「成功 × 確率」と「失敗 × 確率」は足し合わせ（`+`）が必要
- 一方で、どの問題を選ぶかという最適ルートの決定には比較（`max`）が必要
と、ルート内の「和」とルート間の「最大値」を混在させる必要があります。この二つの結合演算を配る DP で扱うことは難しいです。
現在の状態に至る複数のルートどう集約 (結合) するかをマニュアル制御する実装は「もらうDP」なら可能です。
というわけで先の図の遷移とは逆向きに考えます。
```haskell
main :: IO ()
main = do
[n, x] <- getInts
xs <- replicateM n $ do
(s, c, p) <- getTuple3
return (fromIntegral s, c, fromIntegral p / 100)
let dp = array @Array ((emptyBS, 0), (fullBS n, x)) [((s, v), f (s, v)) | s <- [emptyBS .. fullBS n], v <- [0 .. x]]
where
f (bs, v) =
maximumDef
0
[ p * (s + a) + (1 - p) * b
| (i, (s, c, p)) <- indexed 1 xs,
notMemberBS i bs, -- まだ解いてない問題で、
c <= v, -- 残高 v で OK な問題なら挑戦できる
let a = dp ! (insertBS i bs, v - c) -- 問題 i が解けた
b = dp ! (bs, v - c) -- 問題 i が解けなかった
]
print $ dp ! (emptyBS, x)
```
一つ前の状態からの遷移を累積和で取得する問題など、配る DP では解けない構造の DP がときどきあります。
ある状態に至るルートを一つ一つ独立に処理するのではなく、それらルートをすべて取得してから集約する必要があるタイプの問題がそれにあたると思います。この問題ではルートの結合に `(+)` と `max` の二つを使い分ける必要があることから、もらう DP での実装がおそらく必須になる、と考察しました。
とはいえ、期待値が $0$ になるのが $dp(S_{full}, 0)$ などでそこから $dp(S_{empty}, X)$ に向かっていく計算をするという考え方なら、計算の方向も逆向きとなり、こちらの方針からも「もらう DP」で実装するのが自然ではあります。