ABC177 感想

競プロ

コンテストリンク

ABCDの4完。

A問題
よくある算数の問題。
ただ、簡単な問題は凡ミスしやすくて苦手。

B問題
s.size()-t.size()だけ全探索しようとしてs.size()==t.size()のケースでwaを出してしまった。

C問題
普通に計算すると O(N^2)のため紙に書いてみる。
そうすると、 1 \times (2 + 3 + 4) + 2 \times(3 + 4) + 3 \times (5)となっていることに気づく。
累積和を使ってAC。

D問題
幅優先探索して友好関係のある塊を用意して、それぞれの塊にいる人同士を最大になるように合わせていく。
解説を読んで、確かに一番大きい塊のメンバー数が答えだなとなった。

反省

C問題のきれいな解法を思いつけるようになりたい。

D問題を苦労して解いたのに茶diffで少しがっかりしたが、union-findというデータ構造を使うだけだそうな。
知らなかったぞ...

E問題はコンテスト後、解説を読みあっさりACできた。
頑張ればコンテスト中に通せたのではという思いがある。