4完。
各問題
A - First Grid
"#." ".#" と ".#" "#." だけがだめ。自分は日和ってもうちょっと丁寧なif文を書きました。
B - Hard Calculation
各桁ごとに足し算して、一つでも10を超える桁があれば繰り上がりありで、一つもなければ繰り上がりなしです。
公式解説の解法の方がかしこいと思います。自分は文字列で受け取ってひっくり返してどっちかの文字列がなくなるまでチェックする、としました。
C - Cheese
貪欲に1gあたりのおいしさが大きいチーズから乗せていけばいいです。
D - Longest X
Sの中の連続する部分列において'.'がK個以下ならその部分列について全てをXにすることが可能です。
事前に.の出現数の累積和を取っておくことで、候補の部分列一つ毎にO(1)で可能かどうかを求めることができて、Mの候補一つ毎にO(|S|)で求めることが可能です。
あとは、Mの候補を二分探索すればよいです。
ここまで16分ちょっとで解けて、今日は勝ったと思ったのですが・・・。
E - Graph Destruction
いかにもUnion-Findで解けそうな見た目をしていて、実際Union-Findを使ってNから逆順に繋いでいけば解けます。
しかし、連結成分の個数をUnion-Findで求めようとすると一回につきO(N)かかってしまうので間に合いません。 そこで、連結成分数は別に管理しておき、mergeが発生する毎に1減るとすればよいらしいです。
自分は最後までそこに思い至らず、4TLEで終わりました・・・。
まとめ
今週も精進不足がもろにたたったかたちになりました。
まあこれは仕方ないこととして受け入れるしかないですね。リアル優先なんでね。
