メモ

自分に向けて書いたメモを取り扱っています.

ABC 067

abc067.contest.atcoder.jp

久しぶりに参加した.

順位は 21th で早解きが苦手になっていると感じた.

残念なことにレーティングの更新対象ではないレーティングを持っているということすら忘れていた.

所感

A問題

A, B, A+Bに対してmod 3取ってやれば良い.

B問題

ソートする.

C問題

累積和.

D問題

与えられているグラフが木なので,フェネックとすぬけくんを結ぶパスは一つだけ存在する.

最適な行動とは書いているが,塗る頂点を最大化するように各自行動するので,フェネックとすぬけくんの間のパスに関してどれだけ多く塗ることができるかを考えれば良い.

これは幅優先探索フェネックとすぬけくん交互に塗ることができるマスを広げていけば良い.

この問題で,一般グラフが与えられた時はどうすればいいんだろうかと思った.

橋となるような辺を潰していくようにすれば,連結成分の頂点を得ることができるが,その連結成分への橋がいくつあるかにもよるし一意に定まらない気がする.