キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）Eまで。
C DFS
D 部分和問題
E bitDP
F Fraction使ってイベントソートしたが上手くいかず。
G フローだと思って考えていたけどグラフが構築できなかった。

— titia (@titia_til) October 22, 2022

F - Fishing

　一応、自力AC。

　イベントソートという方針は合っていたが、同時に出入りがあったり、0秒ちょうどに出ていくものを忘れていたりしていた。

　また、PyPyで通すのは結構厳しく、FractionをソートしたりしてはTLEが取れない。出入りする時間にある程度大きな整数をかけて誤差を小さくし、tupleを一次元化してからソートしたら通った。

G - Security Camera 3

　解説放送を見てAC。

　コンテスト中、フローだと思ったし、「燃やす埋める」のスライドなどを見に行ったりしたがグラフを構築できなくて、うーん。

　ただ、この問題は、二部グラフの最小点被覆と見るのが分かりやすかったか。けんちょんさんのqiitaの内容はしっかり抑えたい。

　また、グラフ構築の際、

・何を頂点にし、何を辺にするか

　を考え、

・上手くいかなかったら逆（今まで頂点にしていたものを辺に、辺にしていたものを頂点に）も試してみる

　などをすれば解けた気もする。

　類題を解いておこうと思って、これを解いたが（一応、解説は見ないで解けたが）かなり苦戦した。フローのグラフ構築は難しい。