ferinの競プロ帳

競プロについてのメモ

2018-10-15から1日間の記事一覧

AGC028 C - Min Cost Cycle

問題ページ サンプル2眺めてたらA,Bまとめて小さい方からN個取れるとうれしい気持ちになって他のサンプルもそれであったのでそれで考えた。大体合ってたけどB問題で時間溶かしたら詰めきれなかった。 解法 A,Bまとめて小さい方からN個取ったときにハミルトン…

AGC028 B - Removing Blocks

問題ページ i番目がカウントされる回数= sum_{j=1}^N (j番目を取り除く時にi番目と連結なパターン数) までは考察できたけど連結なパターン数を求めるパートで無限に詰まって終了した。数え上げで全通りの数え上げは実質期待値と同じなので確率っぽい考え方が…