ABC218参戦記 - ひたすらに雑記

自分の中で結果がよかったから初めて参戦記書いてる
あくまで日記で解説じゃなくてスマン

Dまでの4完で緑上位のパフォ
Eを通したかったが結果的に方針間違ってたっぽいので時間あっても4完

今回はdiffがC>E>DになったのでCにしては難しかったと思う. (個人的な体感E>C>=D)
やっぱり幾何のdiffは高めにでるなぁと. 多分これが私が本番で通したdiffの最高値更新になった. ありがとう幾何, 割と自分が幾何に強いということが分かってきて自信出てきた( ◠‿◠ )

Cの方針としては, グリッドの外側から図形が登場しない範囲を削除して比較することを行った.
(S,Tそれぞれで上下左右から '#' の登場しない行および列を削除したものを比較 )

外側からというのを見落として '#' の登場しない行および列を全部削除してしまって1WAしたけど割とすぐにWAの原因に気づいたので良かった.
あとコードが愚直すぎて汚くなった. 焦っていたのでしゃーない🤗

Pythonはnumpyを使えるので回転操作は愚直実装しなくてもndarray.rot90()でπ/4回転をしてくれる点は助かった.
(使わないと"for文2回回して1行目を後ろから1列目に"みたいな操作が必要だった)

これを通せたときに今回のレートの冷えがなくなったのでめっちゃ安心した.

Nの制約が小さかったので組み合わせ全探索っぽくO(N²)で通した. 解説曰くもっと高速化できるみたいなのでいつかやる.
本番中は方針がなかなか固まらなくて20分くらい座ってるだけの人になってた.
こういうの10分15分で解けるようになりたいね

key,value型のデータ構造は偉大だ

解説に記載の

なおこの問題は「Ciが大きな辺から順に、その辺を削除しても連結なままなら削除する」という貪欲法でも正しい答えを得ることができますが、辺を削除した際の連結性の判定を高速に行うには高度なアルゴリズムが必要となります。

貪欲をまさにやろうとして, 連結性の判定がうまくいかなかったみたいで解けなかった.

Union-Findなんもわからん

キーワードとして最小全域木, クラスカル法, Union-Findというものを見たので現在勉強中
いい加減Union-Findをちゃんと理解して使えるようになれ,はい.

これまでだったらCやDを割と諦めてたと思うが本番で通せて嬉しかった😊
あとDが一発書きで書ききれたので,実装力が上がってきているのを実感している.

E解けなかったのが悔しいのと, 1問にかかる時間長すぎというのはあるけど,
もう少しで入緑できそうでめちゃくちゃモチベーション上がってる.

茶から緑の人, ぜひお知らせください
Favってモチベにするので