各問題
A - Favorite Sound
公式の解説どおり。
B - K-th Common Divisor
概ね公式の解説どおり。なのですが、min(A, B)
じゃなくて、何をとちくるったかmax(A, B)
としていました・・・。
YouTube解説では単に100とされていて、計算量に対した影響はないからまあいいか、というふうに言われていたので、まあいいか、って感じです。(いいのか?)
C - Unification
最終的に公式の解説どおり。
ですが、初めはまともに解こうとしてTLE連発してしまいました。
そこで我に返って冷静に考えてみて、これ消費されずに0と1が両方残ってしまうことはありえなくないか?ってことに気がついたのでした・・・。
C問題の解法がようやくわかってAC出たときの脱力感は異常#atcoder
— Toy (@mdstoy) 2019年3月3日
わし頭堅すぎるやろ・・・
AtCoder、そういうのもあるのか・・・。
D - Decayed Bridges
後ろから順に繋げていく、差分更新していく、という考えにはたどり着きました。 しかし、肝心の連結情報をどう作ってどう保存するのかがまったくわからなくてタイムアップ。
UnionFind木というのを使うんですねー。ほふー。
課題など
- 考え方一つで、恐ろしくシンプルに実装できるタイプの問題もAtCoderにはある
- データ構造
- 今回はUnionFind木
感想
C問題のダメージがあまりにも大きい。on_ 次は、次こそは茶色に到達するということでどうかひとつ。