AtCoder Beginner Contest 352

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 352 Eまで。
A X<Z<Y or Y<Z<X
B 尺取り
C B-aが一番大きいものを最後に。
D SortedSetをお借りしました。
E Cの小さい順に。
F 2-SATで解けそう！　と実装し始めたが上手くいかず終了。あれ、2-SATで解けないの？

— titia (@titia_til) May 4, 2024

 F - Estimate Order

　解説AC。

　重み付きUnion-findで連結成分ごとにまとめた後、bit DPする。bit DP部分をDFSっぽくやって高速化した。

　コンテスト中もまずbit DPできないか考えたはずなのだが上手くいかない気がし、2-SATでいけると勘違いして突き進んでしまった。「どれか一つが真」って条件は2-SATで表せないですね。

　色々ひどかったけど、2-SATの復習は多少できたかもしれない。

G - Socks 3

　解説AC。

・前半の、期待値を場合の数に置き換えるパート

・後半の、場合の数を多項式の積で表し、形式的べき級数で計算するパート

　どちらも典型なのだが、身に着いていない。

　どちらかというと、後者は問題演習を積めば身に着く気がするので、前者の方がより身に着けたい内容か。期待値を、「i回以上である確率P_i」の和で表すという方法は覚えておきたい。