AtCoder Regular Contest 177

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 177 Cまで。
A 値段の高い硬貨を優先して使う。
B 右端から処理
C 赤・青両方に得ということはないので、二回BFSして和を取ればOK。
D 全く解けていない。連結成分ごとに分けて考えて良いと気付いたのが終了五分前くらいだった。全然ダメ。

— titia (@titia_til) May 12, 2024

D - Earthquakes

　連結成分ごとに分けて考えて良いということを元に考察し直してAC。

　「連結成分ごとに分けて考えて良い」ことさえつかめていれば、後のステップは「その柱が倒れたとき、その連結成分に含まれる柱が全て倒れる確率」を求めるという方針で良く、結構シンプルだった。

　ただ、実装は大変で、答えが0になるときの処理をどうするかでかなり困った。どちらかというと考察より実装にウェイトのある問題だったと思うので、考察で詰まったのは良くない。